qwertz543221 kleine String-Math-Lib

[himitsu]

kleines Beispiel:

Delphi-Quellcode:

function TMathe.summe(a, b: AnsiString): AnsiString;
var
  i, i2, ueberlauf, x: Integer;

begin
  normalisieren(a);
  normalisieren(b);
  if (a[1] = '-') <> (b[1] = '-') then
  begin
    negieren(b);
    Result := differenz(a, b);
    Exit;
  end;
  i2 := Max(Length(a), Length(b)) + 2; // +2 für Überlauf und Vorzeichen
  formatieren(a, False, True, i2);
  formatieren(b, False, True, i2);
  formatieren(Result, False, True, i2);
  ueberlauf := 0;
  for i := i2 downto 2 do
  begin
    x := (Ord(a[i]) - Ord('0')) + (Ord(b[i]) - Ord('0')) + ueberlauf;
    Result[i] := Chr(x mod 10 + Ord('0'));
    ueberlauf := x div 10;
  end;
  Result[1] := a[1];  // Vorzeichen
  normalisieren(Result);
end;

Hab mal das ganze ORD, CHR und sonstiges Umgerechne einfach durch diese Konstanten ersetzt.

Delphi-Quellcode:

const
  ZeichenZuZahl: Array['0'..'9'] of Byte = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
  ZahlZuZeichen: Array[0..9] of AnsiChar = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');

Und nun sieht man, daß man mit einer etwas durchdachten und aufgeräumten Klassenstruktur sehr schön übersichtliche Codes entstehen lassen kann

Delphi-Quellcode:

function TMathe.summe(a, b: AnsiString): AnsiString;
var
  i, i2, ueberlauf, x: Integer;

begin
  normalisieren(a);
  normalisieren(b);
  if istNegativ(a[1]) <> istNegativ(b[1]) then
  begin
    negieren(b);
    Result := differenz(a, b);
    Exit;
  end;
  i2 := Max(Length(a), Length(b)) + 2; // +2 für Überlauf und Vorzeichen
  formatieren(a, False, True, i2);
  formatieren(b, False, True, i2);
  formatieren(Result, False, True, i2);
  ueberlauf := 0;
  for i := i2 downto 2 do
  begin
    x := ZeichenZuZahl[a[i]] + ZeichenZuZahl[b[i]] + ueberlauf;
    Result[i] := ZahlZuZeichen[x mod 10];
    ueberlauf := x div 10;
  end;
  Result[1] := a[1];  // Vorzeichen
  normalisieren(Result);
end;

[qwertz543221]

vielen dank für die anmerkungen - ich werde es, sobald ich dazu komme, umsetzen.

=>bisher hat für mich nur gezählt, dass es die richtigen ergebnisse erzeugt.(Optimierungen sollten später kommen, sobald alles läuft) Da ich das ganze für RSA brauche, habe ich die Negation vernachlässigt.


Wie könnte ich denn die division darstellen, vlt schriftlich??, ohne durchprobieren zu müssen?

[himitsu]

Zitat von qwertz543221:

Wie könnte ich denn die division darstellen, vlt schriftlich??, ohne durchprobieren zu müssen?

na "fast" genauso, wie du es schriftlich auch machst


z.B.

456789 div 123

Zitat:

erstmal den Divisor auf die Stellenanzahl des Dividenden bringen
und gleichzeitig die Stellen zu merken

also

456789
123000
=3 verschobeneStellen

den Quotient mit 0 initialisieren

Schleife:

* * dann so oft wie möglich den neuen Divisor vom Dividend abziehen
* * * * (ohne mit dem Dividend in den negativen Bereich zu kommen)
* * * * parallel dazu das den Quotient um 10^verschobeneStellen erhöhen (dazuaddieren)

* * nun Dividend durch 10 (eine Stelle wieder entfernen)
* * verschobeneStellen minus 1

wenn verschobeneStellen größer 0, dann wiederhole die Schleife


Wenn die Zahlen noch Vorzeichen haben, dann diese am Anfang entferen
und wenn beide Zahlen unterschiedliche Vorzeichen hatten, dann das Ergebnis negieren.

Aber für "aufwändigere" cryptografische Dinge ist soeine Lib dann nicht unbedingt gut geeignet,
da sie halt "recht" langsam arbeitet.

Wenn du dir mal die andere Lib vom Dipl. Ernst Winter ansiehst, dann arbeitet diese bei jedem internem Rechenschritt 6 Dezimalstellen gleichzeitig ab und hier ist es jeweils nur Eine.
Bei meiner Lib sind es noch ein paar mehr, da ich direkt binär rechne und jedes Bit ausnutze
(siehe TBigInt)

Wenn du wirklich stark in Richtung Cryptography arbeiten willst, dann empfehle ich dir das DEC, denn diese Lib ist speziell für soetwas entwickelt wurden.


Was soeine String-Lib aber aus macht:
- sie ist sehr gut zu debuggen und vorallem von "Laien" dürfte verstanden werden, was da intern abläuft
- nja und die Zahlenlänge ist nahezu unbegrenzt ... eine "normale" Win32-Anwendung bekommt man locker eine Zahl mit einer Milliade Stellen
(ok, die verbraucht dann zwar auch fast 1 GB an Arbeitsspeicher, aber es paßt rein)

[qwertz543221]

Danke für deine erläuterungen. ich werde das gleich mal testen.

die einfachheit ist gut, denn zu hochtrabend sollte das ganze ja nicht sein. das DEC schaue ich mir trotzdem einmal an, vlt finde ich dort etwas, das ich gebrauchen kann ( - und verstehe, was notwendig ist, um es auch ordnungsgemäß einzubinden)

[qwertz543221]

noch eine frage:
was meintest du hiermit

"parallel dazu das den Quotient um 10^verschobeneStellen erhöhen (dazuaddieren) "

[qwertz543221]

meintest du das so??:

Delphi-Quellcode:

function tform1.quotient(a,b:ansistring):ansistring;
var 
    stellen:longint;
begin
    result := '0';
    stellen:=0;
    while length(b)<length(a) do
    begin
        b:=b+'0';
        stellen:=stellen+1;
    end;

    while (vergleich(a,b)=0)and(stellen>0)do //divident >divisor
    begin
        result:=summe(result,floattostr(trunc(power(10,stellen))));
        a:=differenz(a,b);
    end;
    delete(a,length(a)-1,length(a));
    stellen:=stellen-1;
end;

[edit=mkinzler]Delphi-Tag eingefügt; Code eingerückt Mfg, mkinzler[/edit]

[himitsu]

die innere Schleife etwas anders geordnet:

Zitat:

erstmal den Divisor auf die Stellenanzahl des Dividenden bringen
und gleichzeitig die Stellen zu merken

also

456789
123000
=3 verschobeneStellen

den Quotient mit 0 initialisieren

Schleife:

* * wenn neuer Divisor größer-gleich Dividend dann wiederhole Schleife2
* * * * (ohne mit dem Dividend in den negativen Bereich zu kommen)
* * * * den Quotient um 10^verschobeneStellen erhöhen (dazuaddieren)
* * ende Schleife2

* * nun Dividend durch 10 (eine Stelle wieder entfernen)
* * verschobeneStellen minus 1

wenn verschobeneStellen größer 0, dann wiederhole die Schleife

also im Prinzip das
Quotient := summe(Quotient, potenz(10, verschobeneStellen));

[qwertz543221]

ich hab das einmal als qt erstellt, aber ich denke, ich habe deine anweisungen misverstanden. (ergo: es funktioniert nicht)

Delphi-Quellcode:

function tform1.quotient(a,b:ansistring):ansistring;
var stellen:longint;

begin
  result := '0';
  stellen:=0;

  while length(b)<length(a) do
  begin
    b:=b+'0';
    stellen:=stellen+1;
  end;

  while stellen>0 do
  begin
    while vergleich(b,a)=0 do  //b>a?
    result:=result+floattostr(trunc(power(10,stellen)));
    delete(a,length(a)-1,1);
    stellen:=stellen-1;
  end;

end;

[edit=mkinzler]Delphi-Tag eingefügt. Das nächste Mal bitte selber machen! Mfg, mkinzler[/edit]

[himitsu]

Zitat von qwertz543221:

result:=result+floattostr(trunc(power(10,stellen)));

keine String-Operation (das +), sondern deiner summe-Funktion

Delphi-Quellcode:

// c = Stellen

function tform1.Quotient(a, b: AnsiString): AnsiString;
var
  c: Int64;
begin
  if b = '0' then System.Error(reDivByZero);
  Result := '0';
  c      := 0;
  while Length(b) < Length(a) do
  begin
    c := c + 1; 
    b := b + '0';  // b := produkt(b, '10');
  end;
  while c >= 0 do
  begin
    while vergleich(b, a) <= 0 do
    begin
      Result := summe(Result, inttostr(trunc(power(10, c))));
      a := differenz(a, b);
    end;
    c := c div 10;            // a := quotient(a, '10');
    Delete(b, Length(b), 1);  // b := quotient(b, '10');
  end;
end;

Aber durch deine wiederholte Vermischung mit Extended begrenzt du die maximale Rechengröße auf 19 Stellen.
In diesem Fall ist es zum Glück nur die Differenz zwischen Stellen von a und b,
aber über die ganze Lib gesehen, wird somit der die maximale Zahlengröße in (abgesehn von der Addition und Subtraktion) auf 19 Dezimalstellen begrenzt und man könnte genausogut mit direkt Int64 arbeiten.

Extended hat zwar einen sehr großen Wertebereich, aber nur 19-20 signifikante Stellen.
heißt: es sind nur die erst 19 bis 20 Stellen gepspeichert und alle nachfolgenden Stellen snd Aufgrund der internen Struktur undefiniert und von Rundungsfehlern überschattet.


Darum mußt du aufpassen, daß du wärend der Berechnungen bei deinem Zahlentyp bleibst und keine der "kleinen" Standardtypen verwendest:

Delphi-Quellcode:

// c = 10^Stellen

function tform1.Quotient(a, b: AnsiString): AnsiString;
var
  c: AnsiString;
begin
  if b = '0' then System.Error(reDivByZero);
  Result := '0';
  c      := '1';
  while Length(b) < Length(a) do
  begin
    c := c + '0';  // c := produkt(c, '10');
    b := b + '0';  // b := produkt(b, '10');
  end;
  while c <> '' do
  begin
    while vergleich(b, a) <= 0 do
    begin
      Result := summe(Result, c);
      a := differenz(a, b);
    end;
    Delete(c, Length(c), 1);  // a := quotient(a, '10');
    Delete(b, Length(b), 1);  // b := quotient(b, '10');
  end;
end;

[qwertz543221]

ich habe deinen vorschlag ausprobiert. anscheinend sind meine anderen funktionen nicht dafür geeignet. - das ergebnis stimmt fast nie.

ich gebe mal die weiteren fkts mit, vlt versteckt sich dort ein fehler ( ich konnte keinen finden, da die fkts an sich ihren dienst ordnungsgemäß erfüllen)

-----------------------------------------------------------------------------------------------------

Delphi-Quellcode:

function summe(a,b:ansistring):ansistring;

var i,l:longint;
u:longint;

begin
//mit Nullen auffüllen:

l:=length(a);
while l<length(b) do
begin
a:='0'+a;
l:=l+1;
end;

l:=length(b);
if length(a)>length(b)
  then
while length(a)>length(b) do
begin
b:='0'+b;
l:=l+1;
end
 else
  if length(b)>length(a)
   then
   while length(b)>length(a) do
   begin
   a:='0'+a;
   l:=l+1;
   end;
u:=0;
//Maximallänge festlegen
if length(a)>=length(b)
  then i:=length(a)
    else i:=length(b);

while i>=1 do
begin
//addition a+b+u
result:=inttostr((strtoint(a[i])+strtoint(b[i])+u)mod 10)+result;
//berechnung u
u:=(u+strtoint(a[i])+strtoint(b[i]) )div 10;
i:=i-1;
end;

i:=1;
result:=inttostr(u)+result;
a:=result;
//führende '0' löschen
while a[1]='0' do
delete(a,1,1);
result:=a;
end;

function differenz(a,b:ansistring):ansistring;
var u,i,j,la,lb:longint;
c:ansistring;
  begin
  //zwei gleiche Zahlen:
  if a=b
  then result:='0'
  else
  //a>b?
if (vergleich(a,b)<>0 )and(a<>b)
  then
  begin
 showmessage('Subtraktion nicht möglich.');
  exit;
  end
    else
    begin
    //initialisieren
    result:='';
    la:=length(a);
    lb:=length(b);
    //anfangsübertrag setzen
    u:=0;
    j:=1;
    //mit nullen füllen
    if la<lb
      then
      while la<lb do
      begin
      a:='0'+a;
      la:=la+1;
      end
        else if lb<la
              then
              while length(a)>length(b) do
              begin
              b:='0'+b;
              lb:=lb+1;
              end;

//subtraktion beginnen - vgl. schriftliches rechnen
i:=length(b);
//von vorne nach hinten
while i>=1 do
begin
//übertrag?
if u=0
  then
  begin
  //neuen übertrag setzen
  if strtoint(a[i])<strtoint(b[i])
    then   u:=10
      else u:=0;
  // nächste stelle des ergebnisses berechnen
  result:=inttostr((strtoint(a[i])+u-strtoint(b[i]))mod 10)+result;
  end
    else
    begin
    //wenn übertrag vorhanden:
    if strtoint(a[i])<strtoint(b[i])+1
      then   u:=10
        else u:=0;
      //bei der nächten stelle eines subtrahieren,da übertrag; einerstelle zum ergebnis
      //hinzufügen
    result:=inttostr((strtoint(a[i])+u-1-strtoint(b[i])mod 10))+result
    end;
  i:=i-1;
  end;
//führende nullen löschen
c:=result;
while c[1]='0' do
delete(c,1,1);
result:=c
end;
end;

[edit=mkinzler]Delphi-Tag eingefügt Mfg, mkinzler[/edit]