Integer Uitbreiding
Dit artikel bevat één van de vele mogelijkheden om een BigInteger-klasse te programmeren, inclusief algoritmen om operaties mogelijk te maken. Een Integer is een geheel getal. Aangezien dit type in veel programmeertalen maar een getal kan zijn van − 216 tot 216, kan het handig zijn om zelf een Big Integer-klasse te bouwen: een geheel getal, dat tot 2,1 miljard cijfers kan tellen. Hiermee kunt u al heel wat meer wiskundige operaties mogelijk maken.
Vergis u niet, operaties met lange getallen zijn mogelijk, maar daarom niet snel! Een van de toepassingen die hiermee gerelateerd zijn is het zoeken naar grote priemgetallen.
Inhoud |
[bewerk] BInt Klasse
Stel BInt als naam voor de klasse. Om de cijfers op te slaan maak je best een array-variabele van Integers, omdat array's indices hebben die tot 2,1 miljard gaan.
| BInt |
|---|
| - digits : int[] - sign : int |
| + BInt(sign : int, digits : int[]) + Length() : int + ToIntArray() : int[] + Sign() : int |
[bewerk] Algoritmen
[bewerk] Basis
elk natuurlijk getal kan men in de volgende som schrijven:
x = x0 * 100 + x1 * 101 + ... + xn * 101
Zij Vx dan de notatie voor de verzameling van alle xi van hierboven, met 
.
Vx = x0,x1,...,xn met #Vx = n + 1
Zij nu de bewerking ◊ op 2 getallen a en b, dan is ◊(a,b) = c of a ◊ b = c en kan je uit a, b en c opnieuw de volgende verzamelingen afleiden:
Va = a0,a1,...,am
Vb = b0,b1,...,bo
Vc = c0,c1,...,cp
stel nu n = max(m,o) + 1 en pas de verzamelingen aan door lege ai, bi en ci gelijk te stellen aan 0, zodat #A = #B = #C. We krijgen dan:
Va = a0,a1,...,an
Vb = b0,b1,...,bn
Vc = c0,c1,...,cn
De algoritmen zullen van deze 3 verzamelingen gebruik maken.
[bewerk] Logische (Booleaanse) operatoren
De eenvoudigste operatoren zijn deze vergelijkingsoperatoren:
| C# | VB | Omschrijving |
|---|---|---|
| > | > | strikt groter dan |
| >= | >= | groter dan of gelijk aan |
| < | < | strikt kleiner dan |
| <= | <= | kleiner dan of gelijk aan |
| == | = | gelijk aan |
| != | <> | verschillend van |
[bewerk] Strikt groter dan
?
a > b
Algoritme:
1. Als a strikt positief is en b is strikt negatief, dan is a > b (WAAR). In andere gevallen ga naar stap 2. 2. Als a strikt negatief is en b is strikt positief, dan is a < b (NIET WAAR). In andere gevallen ga naar stap 3. 3. Als #Va > #Vb, dan is a > b (WAAR). In andere gevallen ga naar stap 4. 4. Als #Va < #Vb, dan is a < b (NIET WAAR). In andere gevallen ga naar stap 5. 5. Zij i een natuurlijk getal = 0, ga naar stap 6 6. Zij n = #Va = #Vb. Neem nu a_{i} en b_{i} vast en vergelijk ze met elkaar: a. Indien a_{i} > b_{i}, dan zal a > b (WAAR). b. Indien a_{i} < b_{i}, dan zal a < b (NIET WAAR). c. Indien a_{1} = b_{i}: neem i = i + 1 en herhaal stap 6, zolang i < n. Als i = n, dan ga je naar stap 7. 7. a = b (NIET WAAR)
[bewerk] Groter dan of gelijk aan
?
a >= b
Algoritme: Analoog als het algoritme van Strikt groter dan, op stap 7 na:
7. a = b (WAAR)
[bewerk] Strikt kleiner dan
Triviaal
[bewerk] Kleiner dan of gelijk aan
Triviaal
[bewerk] Gelijk aan
?
a = b
Algoritme:
1. Als #Va != #Vb, dan is a != b (NIET WAAR). In andere gevallen ga naar stap 2. 2. Zij i een natuurlijk getal = 0 3. Zij n = #Va = #Vb. Neem nu a_{i} en b_{i} vast en vergelijk ze met elkaar: a. Indien a_{i} > b_{i}, dan zal a > b (NIET WAAR). b. Indien a_{i} < b_{i}, dan zal a < b (NIET WAAR). c. Indien a_{1} = b_{i}: neem i = i + 1 en herhaal stap 3, zolang i < n. Als i = n, dan ga je naar stap 4. 4. a = b (WAAR)
[bewerk] Verschillend van
Triviaal
[bewerk] Som en verschil
Er geldt voor ◊ = + of - dat:
met:
en
q − 1 = 0
(zie: geheeltallige deling)
Algoritme:
Zij t, een geheel getal: Als a < b en ◊ = -, dan t = -1, in alle andere gevallen t = 1. Neem q = 0 en Vc = ø. voor i = 0 naar n, doe: { voegtoe (achter)aan Vc
}
C# Voorbeeld
public enum operation {add = 1, subtract = -1}
// Geeft de absolute waarde van een getal
private static BInt Abs(BInt a)
{
return new BInt(1, a.ToIntArray());
}
// Voegt een getal toe aan een getallenlijst
private static int[] addToArray(int[] array, int digit)
{
int length = array.Length,
int[] newArray = new int[length + 1];
array.CopyTo(newArray, 0);
newArray.SetValue(digit, length);
return newArray;
}
// Voert het algoritme uit
private static BInt Operate(int[] a, int[] b, operation op)
{
int t;
int q = 0;
int n = System.Math.Max(a.Length, b.Length) + 1;
int[] c = { };
if ((int)op == 1 && a.Length < b.Length ||
(a.Length == b.Length && a[a.Length - 1] < b[b.Length - 1]))
t = -1;
else
t = 1;
while (a.Length < n)
{
a = addToArray(a, 0);
}
while (b.Length < n)
{
b = addToArray(b, 0);
}
for (int i = 0; i < n; i++)
{
c = addToArray(c, System.Math.Abs((a[i] + (int)op * b[i] + q + 10) % 10));
q = (a[i] + (int)op * b[i] + q + 10) / 10 - 1;
}
return new BInt(t, c);
}
public static BInt operator +(BInt a, BInt b)
{
BInt value = null;
A = Abs(a);
B = Abs(b);
if (a.Sign == 1 && b.Sign == 1)
value = Operate(a.ToIntArray(), b.ToIntArray(), operation.add);
if (a.Sign == -1 && b.Sign == 1 && A > B)
{
value = Operate(a.ToIntArray(), b.ToIntArray(), operation.subtract);
value.sign *= -1;
}
if (a.Sign == -1 && b.Sign == 1 && A <= B)
{
value = Operate(b.ToIntArray(), a.ToIntArray(), operation.subtract);
}
if (a.Sign == 1 && b.Sign == -1 && A <= B)
{
value = Operate(b.ToIntArray(), a.ToIntArray(), operation.subtract);
value.sign *= -1;
}
if (a.Sign == 1 && b.Sign == -1 && A > B)
value = Operate(a.ToIntArray(), b.ToIntArray(), operation.subtract);
if (a.Sign == -1 && b.Sign == -1)
{
value = Operate(b.ToIntArray(), a.ToIntArray(), operation.add);
value.Sign *= -1;
}
return value;
}
