Entwickler-Ecke :: Thema anzeigen - Mit großen Zahlen rechnen

Marco D. - Fr 20.10.06 17:58
Titel: Mit großen Zahlen rechnen

Ich möchte mit großen Zahlen rechnen. D.h. es handelt sich um ganze Zahlen, die mehrere Millionen Stellen haben. Dafür möchte ich eine eigene Klasse schreiben. Diese würde intern einen String verwenden. Aber das scheint mir zu ineffizient. Ich dachte auch an eine verkettete Liste mit Pointern.
Wie soll ich verfahren?

Martok - Fr 20.10.06 18:17
Titel: Re: Mit großen Zahlen rechnen

Marco D. hat folgendes geschrieben:

Looool, warum schreiben auf einmal alle sowas? (Mein Versuch, nur bin ich zu doof für sowas: http://www.delphi-forum.de/viewtopic.php?t=65760)
Wenn du ne fertige Unit brauchst, Such mal nach Suche in: Delphi-Forum

BIGNUM2

Sonst der Hinweis: nimm lieber ein Array mit den Zahlen, und eine Möglichst große Basis. Spart Speicher und ist schneller.

Martok

Martok - Fr 20.10.06 18:23

Also meine Grundlagen hab ich aus dem Infounterricht, "Zahlsysteme".
Mit Basis meine ich so wie bei Hex-werten 16 die Basis ist, bei Oktal 8, Bei Dezimal 10 und bei Binär 2.
Ich rechne im Moment mit der Basis 255, d.h. mit einer Stelle kann ich 255 Werte darstellen. Dies ist jedoch immer nur die interne Darstellung der Zahlen. Ausgeben tust du trotzdem als String. Da dran bin ich dann gescheitert.
Allerdings ist auch das Rechnen mit großen Basen schwieriger, das kann man nich so schön Debuggen. Aber wenn mans dann hat, isses schneller, mit großen Basen zu rechnen. Siehe Horst_H's Posts in den verlinkten Threads.

PS: ist so ein versteckter Hinweis eigentlich ein indirektes Schiebeposting?

Martok - Fr 20.10.06 18:39

Klar ist das Möglich. Haben ja schon mehrere gemacht. Bei Pearl z.b. gehört Bignum standardmäßig dazu, einige andere Sprachen haben sowas auch.
Wenn du es nicht ganz so schnell brauchst, kannst du auch kanz gewöhnlich mit 0-9 rechnen. Ist im Prinzip das gleiche. Dann hast du die Ziffern so, wie du sie "auf Papier" schreiben würdest.
Und genauso rechnet man dann auch damit. 5+8=0,Übertrag 3 usw.

Allesquarks - Fr 20.10.06 19:51

Also ne große Basis bringt nur marginal etwas. Wenn man es wirklich selber macht und schnell machen will

dann nutzt man die hardwarebeschleunigung und macht nicht aus einer addition vier indem man bytes benutzt, sondern eben 32 Bit Zahlen bei 32 Bit-Architektur oder eben 64 Bit bei 64 Prozessor, kenne nur nicht die Opcodes für 64 Bit.

Wenn man den Übertrag meiner Meinung nach nicht andauernd speichern möchte kommt man um assembler oder nicht Delphi meiner Meiunung nach nicht drumherum, da mir keine Möglichkeit bekannt ist, das in diesem Zusammenhang essentielle Carry-Flag mit Sicherheit zu bewahren.

Wenn man das aber mit Hochsprache ergänzt ist das dennoch ziemlich einfach:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

function addbig(zahl1,zahl2:array of longword):array of longword;
asm
   push ebx;
   mov ebx,eax;//Zahl1
   mov ecx,laenge;
@@loop:
   mov eax,[ebx+4*ecx];
   adc eax,[edx+4*ecx];
   mov [result+4*ecx];
   dec ecx;
   jz @@loop;//jump if zero
end;

so ungefähr!! dieses einfache Beispiel geht nur für gleich große Zahlen.

Ich habe die Funktionen fertig gecoded aber nicht debuggt, falls dennoch Interesse besteht Bescheid sagen.

Delete - So 11.02.07 18:18

Und für alle, die sich doch eine solche Klasse selber schreiben wollen (bin grad am vollenden einer für C#):
wer Basis 255 nimmt ist ... ungeschickt, unbedingt 2er Potzenen verwenden, z.B. 256 (also einfach eine Array, etc. of Byte).
Und dann wird man sehr schnell draufkommen, dass das nicht das gelbe vom Ei ist, sondern man besser eine echt GROSSE Basis nimmt (also ein Array of uint, ulong, uint32, uint64, also optimalerweise 2^64).

Und wenn dann einer eine schöne, AUSKOMMENTIERTE, Lösung fürs Dividieren hat, dann möge er sie bitte posten; meine läuft, aber mehr schlecht als recht ;)

MfG
etaMat!c

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!