Hi
ich habe sehr wohl verstanden was du meinst, und sehe auch das du wie ich und viele andere am gleichen "Denk" Problem verhacken
Nämlich wie representiere und speichere ich die großen Zahlen im Speicher !?
Es hängt ganz einfach von der willkürlichen Definition ab was du als bestest empfindest. Dies ist die einzigst richtige Antwort.
D.h. egal ob in Strings, array of Double, array of Word oder array of Cardinal, egal ob in Little Endian, also kleinste Einheit im kleinsten Array Index oder in Big Endian, größtes Element an Array index 0, man kann mit allem so rechnen als meinte man eine sehr große Zahl.
Entscheidend bei der Wahl ist es nur was das effizientes auf der jeweiligen Rechnerarchitektur ist, und ob in der jeweiligen Programmiersprache alle nötigen Operationen verfügbar sind.
Nun in deinem Falle empfehle ich dir
Delphi-Quellcode:
type
TDigit = Cardinal; // 0..10^4-1;
TNumber = array of TDigit;
D.h. in TNumber wird in Little Endian jeweils zur Basis 10^4 die einzelnen Digits gespeichert.
10^4 weil der Datentyp Cardinal bis 10^9 nicht überlaufen kann.
Wir bezeichnen also ein Element aus dem TNumber Array als Digit oder Ziffer, wobei es aber 10^4 verschiedene Ziffern pro Digit gibt. Also statt 10 wie im Dezimalsystem, oder 16 im Hexdezimalsystem oder 2 im Binärsystem, arbeiten wir im 10^5 - System !.
Der Vorteil besteht darin das deine Berechnungen alle in PASCAL programmierbar sind, ohne Assembler, und das bei jedem Schritt du die Zahl sofort ablesen kannst.
TNumber = [1234, 567, 89] ist nämlich -> 01234, 00567, 00089 -> 89.00567.01234
Wie du siehst enthielte
TNumber[0] den Rest der Zahl X mod 10.000
TNumber[1] den Rest der Zahl X div 10.000 mod 10.0000
TNumber[2] den Rest der Zahl X div 10.000*10.0000 mod 10.0000
Also im array Element 0, dem kleinsten Element steht, der kleinste am wenigsten Wertentscheidene Anteil der gesamten Zahl.
Wenn sich die Zahl vergrößert und mehr speicher benötigt so würde einfach TNumber[3] <> 0 werden.
Um es noch einfacher für dich zu machen könntest du aber TNumber als festes Array[0..x] definieren und von Rechts nach Links arbeiten. Obige Zahl sähe gespeichert dann so aus:
TNumber = [0,0,0,0,0,0,0,0, 89, 567, 1234] -> 89.00567.01234
Allerdings verhinderst du damit die einfache Erweiterbarkeit im Darstellungsbereich.
Nun eine solche Zahl in einen Dezimalen String umzuwandeln ist einfach:
Delphi-Quellcode:
function NumberToString(const Number: TNumber): String;
var
I: Integer;
begin
for I := 0 to High(Number) do
Result := Format('%s%0.5d', [Result, Number[I]]);
end;
Soweit so gut. Wenn wir statt 10^5 die Basis auf 2^16 ändern dann kann man ohne Gefahr zwei TDigit multiplizieren auf 2^32 ohne das der Zahlenbereich überläuft. Statt 0 bis 10.000 -1 wärem im TDigit nun 0 bis 65.535 -1 gespeichert, also ca 6,5 mal zuviel an Information. Wir benötigen also weniger Speicher. Der zweite Vorteil ist das alle Operationen wir Multiplikation * 2^x oder Divisionen durch 2^x oder die Boolschen Operatoren AND,XOR,OR direkt auf das TNumber array angewendet werden können. D.h. zur Basis 10^5 haben wir ohne Konvertierungen sofort eine "lesbare" Dezimale Zahl in TNumber, bei der Basis 2^16 aber nicht. Dafür ist die Basis 2^16 einfacher umzusetzen und besser zu verstehen und schneller.
Bis hier hin haben wir über die Darstellung von Natürlichen Zahlen gesprochen, also Zahlen die immer positiv und nicht gebrochen sind. Wird benötigen für RSA Zahlen die Ganzzahlen sind, also Natürliche Zahlen die ein Vorzeichen besitzen können.
Es ist sinnvoll TNumber zu erweitern auf:
Delphi-Quellcode:
type
TNumber = record
Negative: Boolean;
Digits: array of TDigit;
end;
Das Feld Negative bestimmt also ob TNumber negativ oder positiv ist.
Digits ist das immer die absolute Representation der Zahl, was nun sehr viele Operationen stark vereinfacht. Z.b. sollen zwei TNumbers A und B addiert werden so schaut man nach ob beide Nummer gleiches Vorueichen besitzen, also A.Negative = B.Negative. Sollte dies der Fall sein su müssen wir A.Digits + B.Digits ausrechnen. Sollte A.Negative <> B.Negative sein so müssen wir A.Digits - B.Digits rechnen. Die Logiken vereinfachen sich also.
Wie könnte eine Addition nun aussehen ?
Delphi-Quellcode:
procedure Add(var R: TNumber; const A,B: TNumber);
// R = A + B
var
I,J: Integer;
Carry: Cardinal;
begin
if A.Negative = B.Negative then
begin // hier addition von .digits
I := Length(A.Digits);
J := Length(B.Digits);
if I < J then
begin // A > B
R.Negative := A.Negative;
end else
begin // B >= A
R.Negative := B.Negative;
J := I;
end;
SetLength(R.Digits, J);
Carry := 0;
for I := 0 to J -1 do
begin
Carry := Carry + A.Digits[I] + B.Digits[I];
R.Digits[I] := Carry and $FFFF; // mod 2^16
Carry := Carry shr 16; // div 2^16
end;
if Carry <> 0 then
begin
SetLength(R.Digits, J +1);
R.Digits[J] := Carry;
end;
end else
begin // hier subtraktion von .digits
end;
end;
type
TBase = 2..16;
function NumberToStr(const A: TNumber; Base: TBase = 10): String;
// wir haben
// A[i] = ai*2^16^i
// und konvertieren die Zahl in A in einen String der diese Zahl zur Basis Base darstellt.
const
Chars: array[0..15] of Char = '0123456789abcdef';
var
R: Cardinal;
T: TNumber;
begin
T := A;
while not IsZero(T) do
begin
R := DivMod(T, Base); // R := T mod Base und T := T div Base
Result := Chars[R] + Result;
end;
if Result = '' then Result := '0' else
if A.Negative then Result := '-' + Result;
end;
Es ist also recht simpel. Als Vergleich zu NumberToStr() hier mal mit In64 Zahlen.
Delphi-Quellcode:
function NumberToStr(const A: Int64; Base: TBase = 10): String;
const
Chars: array[0..15] of Char = '0123456789abcdef';
var
T: Int64;
R: Byte;
begin
T := A;
while T <> 0 do
begin
R := T mod Base;
T := T div Base;
Result := Chars[R] + Result;
end;
if Result = '' then Result := '0' else
if A < 0 then Result := '-' + Result;
end;
Natürlich ist obiger Code eine Demonstration und nur suboptimal, mit ineffizientem String Handling und ineffizienter Modularer Reduktion.
Gruß Hagen