Exakte Addition langer Zahlen

[ginimausi]

Hallo ihr da draussen!
Ich habe folgendes Problem.
Im Rahmen einer Projektarbeit is es meibne Aufgabe,
ein Programm in Delphi zu schreiben, welches zwei
natürliche Zahlen die man eingibt adddiert.
So weit so einfach, das schwierige dabei ist,
dass beide Zahlen eine Länge von 200
Stellen haben dürfen.
Der Rechner soll die exakte (addierte)
Zahl dann ausgeben.

Delphi-Quellcode:

procedure TForm4.Button1Click(Sender: TObject);
var x, y,z: real;
begin
x:=StrToFloat(Edit1.text);
y:=StrToFloat(Edit2.Text);
z:=x+y;
Listbox1.Items.Add(FloatToStr(z));


end;

Soweit hab ich das Programm jetzt,
es läuft auch bloß ab (10) Stellen addiert es die Zahlen nicht mehr genau,
es kommt eine Zahl 1,55457847E22 oder so heraus
(als Beispiel)

Meine Frage ist deshalb: Wie schreibe ich das Programm das die Zahlen 200 Stellen haben können?
Und dann der exakte Wert ausgegeben wird?

Vielen Dank im Voraus für eure Hilfe ;-)

[edit=mkinzler]Tag gefixt Mfg, mkinzler[/edit]

[mkinzler]

Du brauchst einen Implementierung für große Zahlen. Such mal nach BigInt (z.B. aus DEC)

[mr_emre_d]

mkinzler:
Ich dachte mir, das Ziel sei, es selbst zu machen ? :gruebel:

Ein (sehr blöder) Ansatz meinerseits wäre die Strings manuell aufzuaddieren :P

MfG

[Billa]

So blöd ist die Idee von mr_emre_d doch gar nicht:

die beiden Zahlen "von Hand", also Stelle für Stelle von hinten addieren, den resultierenden "Einer" wegschreiben und mit dem "Überlauf" und der nächsten Stelle links fortfahren, bis Deine Ausgangszahlen keine Stellen mehr übrig haben. Selbst wenn es Datentypen gibt, der 200-stellige Ganzzahlen enthält, könnte der Aufgabensteller (Lehrer??) auf die Idee kommen, 500-stellige Zahlen haben zu wollen.....

[ginimausi]

Würde es theoretisch so gehen(mit dem addieren per Hand),
dass ich die Zahlen in ein Array schreibe?
also jede Stelle der Zahl kommt in ein einzelnes Array-Teilfach?

[Billa]

Kann man machen, aber Zeichenketten reichen eigentlich, da ja auch im String einzelne Zeichen mit einem Index angesprochen werden. Kleiner Tipp, um sich das Leben etwas leichter zu machen: Erstmal beide Zahlen auf die gleiche Länge bringen (vorangestellte "0"), dann spart man sich jede Menge Sonderfälle ...

[mr_emre_d]

OK. Ich habe "meine Idee" ausprogrammiert und muss sagen, es funzt super :)

Gini: Versuchs mal, so zu machen, wie ich vorgeschlagen habe.

MfG

[jfheins]

Du kannst auf die Ziffern bereits Array-mäßig zugreifen ;)=

Also ungefähr so:

Delphi-Quellcode:

zahl1 := Edit1.Text;
zahl2 := Edit2.Text;

while (zahl1.length < zahl2.length)
  zahl1 := '0' + zahl1;

while (zahl2.length < zahl1.length)
  zahl2 := '0' + zahl2;

setlength(Result, zahl1.length);
temp := 0;
carry := 0;


for i := zahl1.length downto 1 do
begin
  temp := strtoint(zahl1[i]) + strtoint(zahl2[i]) + carry;
  Result[i] := temp mod 10;
  carry := temp div 10;
end;

if carry > 0 then
  Result := inttostr(carry) + Result;

Edit: Diverse Verbesssungen :oops:

[ginimausi]

Ich versteh nicht so ganz was "manuell aufaddieren "
heist?^^
Wenn ich weiß was es heißt werde ich das ausprobieren
=)
Sry, bin blond;-)

[Billa]

...ohne es auszuprobieren: könnte RESULT nicht eine Stelle mehr enthalten? Überlauf?

SORRY! hatte nicht richtig gelesen: da steht ja schon " + 1"!!!!

[ginimausi]

Danke schonmal für die vielen Antworten :-)

[mr_emre_d]

Billa: Am Ende einfach Carry überprüfen -> Falls > 0 Dann -> Result := IntToStr(Carry) + Result

[jfheins]

Zitat:

Zitat von Billa

...ohne es auszuprobieren: könnte RESULT nicht eine Stelle mehr enthalten? Überlauf?

SORRY! hatte nicht richtig gelesen: da steht ja schon " + 1"!!!!

*g* Ich hatte das erstmal hingeschriben und dann nochmal durchgedacht und verbessert ;)

[Billa]

Ehrlich währt am Längsten, gelle? :)

[Mithrandir]

Zitat:

Zitat von ginimausi

Ich versteh nicht so ganz was "manuell aufaddieren "
heist?^^

Schriftliches addieren... ;)

[Frankfurtoder]

Zitat:

Zitat von ginimausi

Ich versteh nicht so ganz was "manuell aufaddieren "
heist?^^
Wenn ich weiß was es heißt werde ich das ausprobieren
=)
Sry, bin blond;-)

Zahl 1: 123
Zahl 2: 458

3+8 = 11
1+2+5 = 8
1+4 = 5

Ergebnis 581

[mr_emre_d]

Zitat:

Zitat von Billa

...ohne es auszuprobieren: könnte RESULT nicht eine Stelle mehr enthalten? Überlauf?

SORRY! hatte nicht richtig gelesen: da steht ja schon " + 1"!!!!

xD

Manuell aufaddieren heißt es per Hand zu machen:

100000
000050
------

Folgendes so lange wiederholen, bis du bei '1' von 100000 bist
0. Carry = 0 setzen
1. 0 + 0 + Carry = 0 -> Carry = 0
2. Eine Stelle nach links
3. 0 + 5 = 5 -> Carry = 0

EDIT:
Lol .. Heit sanma alle leicht a wengal "hüba aktiv"

MfG :mrgreen:

[Billa]

Es hilft ungemein, wenn man sich erinnert, wie einem das Addieren in der Grundschule beigebracht wurde... das ist ja schon der perfekte Algorithmus ...

[himitsu]

Zitat:

Zitat von mr_emre_d

Manuell aufaddieren heißt es per Hand zu machen:

praktisch so, wie man es mal in der Schule gelernt haben sollte :angel2:

[Billa]

Hier gibts heute ein seltsames Echo ... ;)

[Frankfurtoder]

Zitat:

Zitat von mr_emre_d

Manuell aufaddieren heißt es per Hand zu machen

Boah. Ich habe gerade doch wirklich gelesen "Manuell aufaddieren heißt es sich per Hand zu machen"

:lol:

[mkinzler]

Zitat:

Zitat von Frankfurtoder

Zitat:

Zitat von mr_emre_d

Manuell aufaddieren heißt es per Hand zu machen

Boah. Ich habe gerade doch wirklich gelesen "Manuell aufaddieren heißt es sich per Hand zu machen"

:lol:

Dann fühlt er sich vielleicht besser. Sein Problem ist dann aber immer noch nicht gelöst :mrgreen:

[mr_emre_d]

Ich lach mich tot :tongue:

Gini: Wie schauts denn aus?

MfG

[DP-Maintenance]

Dieses Thema wurde von "Matze" von "Programmieren allgemein" nach "Sonstige Fragen zu Delphi" verschoben.
Delphi-Frage

[ginimausi]

Bei dem array-mäßigen zugriff
- von welchen typ müssen da die variablen sein?
weil das mit .lenght funktioniert bei mir nicht
=(

[ginimausi]

iwie komm ich gar nicht zurecht^^ :-D
mir fehlt gerade ein geistesblitz, um das mit dem pc manuell aufaddieren zu können^^

@mkinzler: er fühlt sich dann nicht besser^^
ich bin eine sie :-P

[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 ...

[blink182]

ich hab ne lösung, aber dir die jetzt zu schicken ist ja auch was doof :P denn du sollst das ja auch verstehen

erst mal die beiden strings auf eine länge bringen

und dann jeweils die die einzelnen zeichen addieren (vom der lange der strings bis runter zu 1)

zwischen -> zahl[i] + zahl2[i]+uebertrag

dann den wert des übertrages ermitteln für den nächsten additionsschritt (zahl[i-1]+zahl[i-2]+uebertrag)

wenn zwischen jetzt 2 stellig ist dann einfach
nur die 2. stelle zum ergebnis speichern
result -> zwischen[2]+result
wenn nicht
uebertrag -> 0
result-> zwischen+result

wenn am ende also bei der addition von zahl[1]+zahl[1]+uebertrag nochmal ein übertrag entsteht den auch einfach nochmal zum ergebnis hinzufügen

mhm sollte jetzt eigentlich ohne weiteres möglich sein einen algo zu schreiben, der steht ja da schon fast^^

[xewo]

Hallo, wenn ich den Threadstarter richtig verstanden habe, dann meint er sowas:

Delphi-Quellcode:

procedure TForm1.BtnBerechnenClick(Sender: TObject);
  var
  Zahl1,Zahl2,Ergebnis,TempUE : String;
  UEbertrag, Temp1, Temp2, TempE, Laenge, i : Integer;
begin
  Zahl1 := EdZahl1.Text;
  Zahl2 := EdZahl2.Text;
  UEbertrag := 0;

  if length(Zahl1) > length (Zahl2) then
    Laenge := length(Zahl1)
  else
  if length(Zahl2) > length (Zahl1) then
    Laenge := length(Zahl2)
  else
  if length(Zahl2) = length (Zahl1) then
    Laenge := length(Zahl1);

  for i := 0 to Laenge-1 do
    begin
      if length(Zahl1) -i < 0 then
        begin
          Temp2 := StrToInt(Zahl2[length(Zahl2) - i]);
          Temp1 := 0;
          UEbertrag := 0;
        end
      else
      if length(Zahl2) -i < 0 then
        begin
          Temp1 := StrToInt(Zahl1[length(Zahl1) - i]);
          Temp2 := 0;
          UEbertrag := 0;
        end
      else
      begin
        Temp1 := StrToInt(Zahl1[length(Zahl1) - i]);
        Temp2 := StrToInt(Zahl2[length(Zahl2) - i]);
      end;

      if Temp1+Temp2+UEbertrag >= 10 then
        begin
          TempUE := IntToStr(Temp1 + Temp2 + UEbertrag);
          Ergebnis := TempUE[2] + Ergebnis;
          UEbertrag := StrToInt(TempUE[1]);
        end
      else
        begin
          Ergebnis := IntToStr(Temp1 + Temp2 + UEbertrag)[1] + Ergebnis;
          UEbertrag := 0;
        end;
    end;
    EdErgebnis.Text := Ergebnis;
end;

mfg xewo

[mr_emre_d]

Dieser Vorgang wurde schon X. Mal erklärt :P

MfG

[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;