Mit großen Zahlen rechnen

Marco D. · Verfasst: Fr 20.10.06 17:58

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?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Martok · Verfasst: Fr 20.10.06 18:17

Marco D. hat folgendes geschrieben:

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?

Looool, warum schreiben auf einmal alle sowas? (Mein Versuch, nur bin ich zu doof für sowas: 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

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Marco D. · Verfasst: Fr 20.10.06 18:19

Das wäre dann ein Array of ??? Wie meinst du das, mit der Basis? Kann man sich irgendwo über dieses Thema Wissen aneignen?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Martok · Verfasst: 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?

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Marco D. · Verfasst: Fr 20.10.06 18:34

Ist es denn theoretisch möglich, so eine Klasse mit Basis 255 zu schreiben und damit Ganzzahlen mit mehreren Millionen Stellen zu verwalten? Wo bekommt man Informationen über dieses Thema?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Martok · Verfasst: 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.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Marco D. · Verfasst: Fr 20.10.06 18:40

Wo bekomme ich denn BigNum für Delphi? Bei Google habe ich sie nicht gefunden. :nixweiss:

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Martok · Verfasst: Fr 20.10.06 18:41

Martok hat folgendes geschrieben:

Wenn du ne fertige Unit brauchst, Such mal nach Suche in: Delphi-Forum

BIGNUM2

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Horst_H · Verfasst: Fr 20.10.06 19:33

Hallo,

da gibt mehrere und umfangreichere zu Beispiel.
home.netsurf.de/wolf...hrhardt/misc_de.html mpint mit Karatsuba Multiplikation etc.
auf der Seite sind auch paar interessante Zufallszahlengeneratoren.

Gruss Horst

Allesquarks · Beiträge: 510 Win XP Prof Delphi 7 E

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:

markieren

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.

BenBE · Verfasst: Fr 20.10.06 20:28

Man nutze einfach die Suchfunktion ... BigNum, BigInt, ... Einfach mal im Forum suchen ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ehemaliges Mitglied Erhaltene Danke: 1

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

BenBE · Verfasst: Mi 14.02.07 15:40

Ich hab in einem Langzahlrechner zuhause mal eine Langzahl-Division geschrieben gehabt ... funktioniert auch soweit gut ... Hab nur den Source grad nicht zur Hand... Sprech mich einfach mal drauf an ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme