Exakte Addition langer Zahlen

[jfheins]

Zitat:

Zitat von quendolineDD

Und wenn man einfach das ganze Binär ausrechnet? Also richtige binäre Addidition. Und die Ausgabe dann als String machen. Das wäre glaube ich doch bestimmt schneller ...

Glaube ich nicht. Dann müsstest du ja erstmal die ganze Zahl in eine Binärzahl umwandeln und danach wieder zurück.

Was allerdings das ganze beschleunigen könnte wäre soetwas:

Result[i] := Chr((Ord(zahl1[i]) and $F + Ord(zahl2[i]) and $F + Carry) mod 10) or $30)

also ohne inttostr und strtoint zu benutzen.

Aber mal im Ernst: Bei Zahlen <1000 Stellen sollte das nicht ins Gewicht fallen ;)

[mr_emre_d]

Also für 100.000 Stellen braucht mein Algo im Schnitt ~40 MSek.

MfG

[Mithrandir]

Zitat:

Zitat von mr_emre_d

Also für 100.000 Stellen braucht mein Algo im Schnitt ~40 MSek.

MfG

40 MegaSekunden? Bisschen viel, meinste nicht? ;)

[mr_emre_d]

Lol .. Ja :(

[nahpets]

Hallo ginimausi,

für Integerzahlen könnte das Ganze auch so aussehen:

Delphi-Quellcode:

program langzahl;
Const
       MaxZahlenLaenge = 200; // Das soll für's Erste genug sein :-)
Var
       sZahl1         : String;  // unsere 1. Zahl als Zeichenfolge
       sZahl2         : String;  // unsere 1. Zahl als Zeichenfolge
       sZahl3         : String;  // das wird die Summe
       i              : Integer; // ein Zähler für die Schleife
       iZahl1         : Integer; // eine Ziffer aus Zahl 1
       iZahl2         : Integer; // eine Ziffer aus Zahl 2
       iZahl3         : Integer; // iZahl1 + iZahl2
       iZahlUeberlauf : Integer; // 1, wenn iZahl3 >= 10, sonst 0
begin
  sZahl1 := '123456987456312125447899511212332114565';  // eine Zahl
  sZahl2 := '987987987987545462311323216545564987454665445654654654'; // und noch eine Zahl
  sZahl3 := ''; // noch nix
  // alles links mit 0 auf die maximale Länge auffüllen
  while Length(sZahl1) < MaxZahlenLaenge do sZahl1 := '0' + sZahl1;
  while Length(sZahl2) < MaxZahlenLaenge do sZahl2 := '0' + sZahl2;
  while Length(sZahl3) < MaxZahlenLaenge do sZahl3 := '0' + sZahl3;
  // da ist noch nix drin, wir fangen ja gerade erst an
  iZahlUeberlauf := 0;
  // wir arbeiten von rechts nach links
  for i := MaxZahlenLaenge DownTo 1 Do begin
    iZahl1 := StrToInt(sZahl1[i]);  // eine Ziffer holen
    iZahl2 := StrToInt(sZahl2[i]);  // noch eine Ziffer holen
    // die beiden Ziffern addieren und den Überlauf der vorherigen Addition dazurechnen.
    iZahl3 := iZahl1 + iZahl2 + iZahlUeberlauf;
    // ist das Ergebnis >= 10, so haben wir einen Überlauf.
    if iZahl3 >= 10 then begin
      iZahlUeberlauf := 1; // weil Überlauf
      // 10 abziehen, damit wir nur die letzte Ziffer bekommen.
      iZahl3         := iZahl3 - 10;
      // die Ziffer in die Ergebniszahl übernehmen.
      sZahl3[i]      := IntToStr(iZahl3)[1];
    end else begin
      iZahlUeberlauf := 0; // kein überlauf
      // die Ziffer in die Ergebniszahl übernehmen.
      sZahl3[i]      := IntToStr(iZahl3)[1];
    end;
  end;
  // Ergebnis ausgeben.
  WriteLn('  Zahl1: ' + sZahl1);
  WriteLn('+ Zahl2: ' + sZahl2);
  WriteLn('  Summe: ' + sZahl3);
end.

Bei Dezimalzahlen müsste man auf die gleiche Zahl von Vorkommastellen und die gleiche Zahl Nachkommastellen auffüllen, könnte dann aber genauso von rechts nach links über die String laufen und müsste nur beim Komma einen kleinen "Hüpfer" machen.

[mr_emre_d]

:(

Postet gefälligst keine Lösungmöglichkeiten :twisted:

( Denn davon hat sie nichts :P )

Edit:
Gini - komm mal ins Chat.

MfG :roll:

[blink182]

Zitat:

Zitat von mr_emre_d

Also für 100.000 Stellen braucht mein Algo im Schnitt ~40 MSek.

MfG

was haste denn da gebastelt? :D

[mr_emre_d]

OK. Ich poste es auch ... Sie hats ganz bestimmt schon von den vorigen Posts Copy&Pasted...

Delphi-Quellcode:

function StrAddition( var Str1, Str2: String ): String;
const
  VN: set of char = [ '0'..'9' ];
var
  i, Carry: Integer;
  function ValidNumbers: Boolean;
  var
    i: Integer;
  begin
    Result := False;
    for i := 1 to Length( Str1 ) do
      if not ( Str1[i] in VN ) then
        Exit;
    for i := 1 to Length( Str2 ) do
      if not ( Str2[i] in VN ) then
        Exit;
    Result := not Result;
  end;
  procedure EquateStrLengths;  // macht aus 1234 v 12 -> 1234 v 0012
  var
    L, S: PString;
    B: String;
  begin
    if Length( Str1 ) = Length( Str2 ) then
      Exit;
    L := @Str1;
    S := @Str2;
    if Length(Str1) < Length(Str2) then
    begin
      L := @Str2;
      S := @Str1;
    end;
    SetLength( B, Length( L^ ) - Length( S^ ) );
    FillChar( B[1], Length( L^ ) - Length( S^ ), '0' );
    S^ := B + S^;
  end;
begin
  Result := 'Error';
  if not ValidNumbers then
    Exit;
  EquateStrLengths;
  SetLength( Result, Length( Str1 ) );
  Carry := 0;
  for i := Length(Str1) downto 1 do
  begin
    Result[i] := IntToStr( ( StrToInt( Str1[i] ) + StrToInt( Str2[i] ) + Carry ) mod 10 )[1];
    Carry     :=           ( StrToInt( Str1[i] ) + StrToInt( Str2[i] ) + Carry ) div 10;
  end;
  if Carry > 0 then
    Result := IntToStr(Carry) + Result;
end;

Demo Dino im Anhang :)

MfG

[blink182]

läuft doch flüssig und schnell :)

[jfheins]

Das rechnen schafft mein Programm in 12 Millisekunden, nur das anzeigen dauert ein paar Sekunden :stupid:

(12 ms wenn beide Zahlen 200000 Ziffern haben)

Code:

 var start = DateTime.Now;

            var zahl1 = '0' + textBox1.Text;
            var zahl2 = '0' + textBox2.Text;

            while (zahl1.Length < zahl2.Length)
            {
                zahl1 = '0' + zahl1;
            }

            while (zahl2.Length < zahl1.Length)
            {
                zahl2 = '0' + zahl2;
            }

            char[] Result = new char[zahl1.Length];

            int temp = 0;
            int carry = 0;

            for (int i = zahl1.Length - 1; i >= 0; i--)
            {
                temp = ((byte)zahl1[i] & 15) + ((byte)zahl2[i] & 15) + carry;

                Result[i] = (char)(temp % 10 | 48);
                carry = temp / 10;
            }

            var res = new String(Result);

            var ende = DateTime.Now;

            label1.Text = (ende - start).TotalMilliseconds.ToString();
            label1.Refresh();

            textBox3.Text = res;