hugeInt * und /

*D*

Hallo,
ich habe jetzt meine Klasse hugeInt fertig gestellt, mit allen Operatoren, die
man benötigt. Jetzt habe ich aber bemerkt, dass mein Algorithmus für das
Multiplizieren und Dividieren (und damit auch Modulo) rechnen ziemlich langsam
ist. Meine Klasse verwaltet die Zahl intern mit einem Vector der einzelnen
Stellen (dabei ist [0] die letzte Stelle). Weiß jemand, wie ich einen schnellen
Algorithmus schreiben könnte???

*D*

Hab gerade gemerkt, dass mein *-Operator gar nicht mal so langsam ist, aber der
/!!! Wie könnte ich das denn machen? In der Art, wie man in der Schule es
gelernt hat???

*D*

Weiß denn niemand, wie ich das machen soll? Ich habe jetzt schon ein etwas
anderes Verfahren benutzt, aber das ist immer noch so langsam!

Blue-Tiger

wenn du uns nicht verraetst, welches Verfahren du zur Zeit verwendest, koennen wir ja nicht wissen ob's ein besseres gibt

BTW passt der Thread besser in RudP als nach C++.

Fake oder Echt

Abgesehen davon finde ich es...naja...dreist, dass du innerhalb von einer Stunde bei einer doch recht speziellen Frage bei der noch nichtmal wirklich nötige Informationen gegeben sind, so sehr drängelst und wahrscheinlich noch eine richtige Antwort erwartest. Das einzige was man dir zurzeit sagen kann, ist das, was Blue-Tiger bereits erwähnt hat.

*D*

In welches Forum hätte ich das stellen sollen?

Mein momentaner Algorithmus zählt einfach wie oft man eine Zahl abziehen kann.
(Ich weiß, noch primitiver geht's gar nicht! Aber ich wusste einfach nicht, wie
ich es anders machen sollte!)

Fake oder Echt

RudP = Rund um die Programmierung

Ben04

Ich hatte auch mal eine BigInt Klasse geschrieben.

Intern habe ich die Zahl zur Basis 2^32 gespeichert. Das lässt sich sehr einfach als unsigned Array speichern und nutzt den Speicher optimal aus.

Im folgenden ist n die Länge des Arrays dar.

Als erstes habe ich die Shifftoperatoren auf die recht offensichtliche Art implementiert. Diese haben eine Laufzeit von O(n).

Anschließend die Vergleichsoperatoren. == läuft auf ein Bitvergleich hinaus und < auf einen lexicongraphischen Vergleich. Beides läuft in O(n)

Anschließend habe ich die Additionsoperatorn implementiert. Hier habe den üblichen Überlauf Algo. Die Eigenschaft, dass der Überlauf bei einer einfachen Addition immer 1 oder 0 beträgt gilt für jede Basis. Dieser Algo hat eine Laufzeit von O(n).

Bei der Multiplikation habe ich anschließend das Schnelle Potenzieren und die Addition benutzt. Wenn man den Algo auf die Addition anstatt der Multiplikation anwendet so erhält man keinen Algo zum potenzieren sondern zum multiplizieren. Formal angeschrieben:

a*b := (a+a)*(b/2) wenn b gerade
a*b := a+a*(b-1) wenn b ungerade
a*0 := 0

Da man für /2 auch den Shifftoperator einsetzen kann braucht dieser Algo keine Division. Dieser Algo besitzt eine Laufzeit von O(n^2)

Bei der Division habe ich ausgenutzt, dass f(x) = x*b strikt wachsend ist und g(x) = x/b die Umkehrfunktion von f ist. Da ich f berechnen kann, kann ich x/b mit einer binären Such approximieren.

Setze I = [0, a]
Solange Länge I > 1
    Setze m = Median I 
    wenn m*b <= a
        Setze I = [min I, m]
    sonst
        Setze I = [m, max I]
Gebe min I aus

Den Median eines Intervalls [a, b] kannst mit (a+b)/2 bestimmen. Dieser Algo hat eine Laufzeit von O(n^3).

Ganz ähnlich kannst du in O(n^3) potenzieren und in O(n^4) Wurzel und Logarithmen approximieren.

C++ Forumbot

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

rüdiger

http://dl.fefe.de/bignum.pdf
http://cr.yp.to/papers/m3.pdf http://www.c-plusplus.net/forum/viewtopic-var-t-is-206490.html