Ansatz für eine Klasse, die sehr große Gleitkommazahlen darstellen kann

[Don Quijote]

Wie der Titel schon aussagt, habe ich Probleme einen Ansatz für die Erstellung einer Klasse, die mit großen Zahlen rechnen kann, zu finden.

Ich habe angefangen, die Zahl in einem String zu speichern. Bisher ist das programmieren auch kein problem, aber als ich heute die Multiplikation abgeschlossen habe und 2 50stellige Kommazahlen miteinander multipliziert habe, dauerte die Berechnung des Ergebnisses zwischen 10 und 20 Sekunden.

Vor längerer Zeit habe ich mal was von der GMP Lib gelesen und diese im Internet rechnen lassen. Die Geschwindigkeit dieser Lib. ist um ein vielfaches schneller als mein Code.

Ich sehe keine andere Möglichkeit, als die Zahl über einen String zu verwalten.

Ich möchte keine Klasse aus dem Internet oder dergleichen, sondern möchte durch diese Aufgabe C++ besser kennen lernen, da ich erst seid ca. 6 Monaten dabei bin es zu lernen.

Kennt jemand einen anderen Ansatz?

[Skym0sh0]

du kannst zum beispiel dir eine bibliothek für grosse integer werte schreiben(oder saugen;) ) und dann auf dieser basis mit kommazahlen arbeiten

sprich indem du das komma durch potenzen verschiebst

0.2 = 2 * 10^-1
0.02 = 2 * 10^-2

0.32523583265932 = 32523583265932 * 10^-14
die erste zahl kann man gut addieren/subtrahieren und die zweite musst du per potenzgesetze umformen...

achte auf klammern und co

0.32523583265932 + 0.32523583265932 != (32523583265932+32523583265932) * 10^-14...

[Jester]

Du hast die Multiplikation vermutlich so implementiert, wie man das in der Schule lernt, oder? Es gibt schnellere Methoden die Multiplikation zu berechnen, zum Beispiel den Karazuba-Algorithmus. Das hier finde ich eine ganz schöne Beschreibung: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo16.php

[Don Quijote]

Danke euch beiden schonmal für die tipps

@Skym0sh0: ich möchte mir alles selbst schreiben und nichts downloaden, aber sonst ist dein Rat mit den Potenzen gar nicht so dumm, danke

@Jester: jo so hab ichs gemacht. Ich wusste nicht, dass es auch ne schnellere Methode gibt, werd ich mir gleich mal durchlesen.

Edit: Habs mir mal durchgelesen. Ist ganz interessant, aber wird bei mir nur einen geringen Performanceschub bringen. Trotzdem versuch ichs mal.

Sind größere Datantypen wirklich nur über Zeichenketten zu realisieren?

[drakon]

Sind größere Datantypen wirklich nur über Zeichenketten zu realisieren?

Nein. Aber irgenwie mit einer Art Container wirst du immer arbeiten müssen.

[Jester]

Don Quijote schrieb:

Edit: Habs mir mal durchgelesen. Ist ganz interessant, aber wird bei mir nur einen geringen Performanceschub bringen. Trotzdem versuch ichs mal.

Bist Du sicher? Ich finde O(n^1.58) ist schon *deutlich* netter als O(n^2).

[Don Quijote]

Klar ist das um einiges besser aber trotzdem ist mein Code zu langsam.

Ich muss mal schaun, ob ich da noch was optimieren kann. Falls es probleme gibt, meld ich mich.

Vielen dank schonmal für die Antworten.

[Der freundliche Helfer]

Wie speicherst du die Ziffern denn? Ich schätze mal du speicherst in deinem String die Zahl zur Basis 10 oder?
Das ist natürlich "dumm" (nicht böse gemeint), besser wäre es wenn du das Byte voll ausnutzt, d.h. bei einem Octett (Byte mit 8Bit - bei den Standardnazis hier muss man sich immer sehr präzise ausdrücken) würde sich die 256 als Basis anbieten.

[Nexus]

Don Quijote schrieb:

Klar ist das um einiges besser aber trotzdem ist mein Code zu langsam.

Mit professionellen Bibliotheken wie GMP wirst du so schnell nicht mithalten können. Inwiefern ist dein Code zu langsam? Hast du Zeit gemessen? Bist du überhaupt sicher, wo Zeit verschwendet wird? Falls nicht, benutz doch einen Profiler.

Und Zeichenkette als Speicher ist natürlich kaum optimal. Eventuell könntest du einen eigenen kleinen Container schreiben (für Speicherersparnis mit Bitfeldern ;)).

[Don Quijote]

Das ist mir schon klar, aber 10-20 sekunden für die multiplikation von 2 50stelligen Zahlen ist etwas extrem langsam, wie ich finde.

Ich würd gerne einen Profiler benutzen, habe aber keine Ahnung wie wo man einen solcher herbekommt und wie man ihn benutzt. Gibts da vlt. Anleitungen im i-nethab nämlich noch keine gefunden.

Mit Containern hab ich mich noch nicht befasst, kennst du ein gutes Tutorial, dass die Grundlagen vermittelt?

[unskilled]

Jester schrieb:

Es gibt schnellere Methoden die Multiplikation zu berechnen, zum Beispiel den Karazuba-Algorithmus. Das hier finde ich eine ganz schöne Beschreibung: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo16.php

[...]

Ich finde O(n^1.58) ist schon *deutlich* netter als O(n^2).

Also zunächst einmal fehlt bei dieser Statistik leider die Häufigkeit von Addition und vor allem Subtraktion im Vergleich...

Subtraktion: Schulmethode = 0; Karazuba = viele ^^
Addition: von Gefühl her würd ich sagen: Schulmethode << Karazuba

Also wird aus dem
n^1,58 : n^2

fast schon ein Gleichstand würde ich sagen, aber nat. kann ich das nicht genau mit 100%iger Sicherheit sagen, weil ich mir den Algo dazu hätte intensiver angucken sollen ^^
also es wird sich erst bei (sehr) großen (langen) zahlen lohnen... glaube ich. (und bei mir gilt glauben < denken < wissen ^^)

Zu guter Letzt habe ich auch noch gelesen, dass die Karazuba-Methode nur für 2^n - lange Zahlen gilt... Deshalb würde ich mal stark bezweifeln, dass es sich für eine 2^n - 1 stellige Zahl lohnen wird (diese Aussage ist nat. auf große n zu beziehen)... Wenn man nur die Multiplikationen sieht dann schon aber eine Subtraktion ist ja auch nicht ganz kostenlos ^^

bb

PS: Sicherlich müsste man sich den Algo genauer angucken um sagen zu können, dass er doof ist - wenn es mir sehr auf Geschwindigkeit ankommen würde, würde ich aber auf jedem Fall nach einem besseren suchen und erst, wenn ich keinen finde, den von K. (ich mag den Namen nich ^^) nehmen - und vll noch vergleichen, aber langsamer sollte er nicht sein, es sei denn, bei der Subtraktion läuft iwas grundsätzlich falsch ^^

[Hä??]

Wie lautet deine Rechnung für die asymptotische Notation denn?
Im Artikel wurde das berechnet was kostet und das sind die Multiplikationen.

Addition fällt da nicht ins gewicht, so lang die Anzahl sich maximal um ein konstantes Vielfaches von der Anzahl der Multiplikationen unterscheidet.
Dass dies bei der Schuldmethode der Fall ist sieht man ja sehr leicht.
Bei Karazuba ebenfalls mit etwas nachdenken.

[Jester]

unskilled schrieb:

Jester schrieb:

Es gibt schnellere Methoden die Multiplikation zu berechnen, zum Beispiel den Karazuba-Algorithmus. Das hier finde ich eine ganz schöne Beschreibung: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo16.php

[...]

Ich finde O(n^1.58) ist schon *deutlich* netter als O(n^2).

Also zunächst einmal fehlt bei dieser Statistik leider die Häufigkeit von Addition und vor allem Subtraktion im Vergleich...

Subtraktion: Schulmethode = 0; Karazuba = viele ^^
Addition: von Gefühl her würd ich sagen: Schulmethode << Karazuba

Also wird aus dem
n^1,58 : n^2

fast schon ein Gleichstand würde ich sagen, aber nat. kann ich das nicht genau mit 100%iger Sicherheit sagen, weil ich mir den Algo dazu hätte intensiver angucken sollen ^^

???

Wo wird hier was nicht gezählt? Die O(n^1.58) sind hier tatsächlich schon der gesamte Aufwand. Die Schulmethode benötigt n Additionen -> O(n^2). Eine Subtraktion ist genauso aufwendig wie eine Addition. Karazuba benötigt von Additionen und Subtraktionen insgesamt deutlich weniger als die Schulmethode.

Schau's Dir wirklich nochmal in Ruhe an und mach die Analyse dazu.

Zu guter Letzt habe ich auch noch gelesen, dass die Karazuba-Methode nur für 2^n - lange Zahlen gilt... Deshalb würde ich mal stark bezweifeln, dass es sich für eine 2^n - 1 stellige Zahl lohnen wird (diese Aussage ist nat. auf große n zu beziehen)... Wenn man nur die Multiplikationen sieht dann schon aber eine Subtraktion ist ja auch nicht ganz kostenlos ^^

ahja, 2^n geht und 2^n-1 geht nicht... für welches n? Richtig ist: Die Zahl braucht eine 2er-Potenz an Stellen. Das erreicht man aber einfach, indem man die fehlenden Stellen (implizit) mit Nullen auffüllt.

PS: Sicherlich müsste man sich den Algo genauer angucken um sagen zu können, dass er doof ist

Ja, würde ich an Deiner Stelle mal machen, oder hier zumindest keinen Quatsch erzählen. Ist ja nicht schlimm, wenn man das nicht versteht, aber dann sollte man hier nicht so tun als sei das ein ganz großer Mist.

[unskilled]

Jester schrieb:

Wo wird hier was nicht gezählt? Die O(n^1.58) sind hier tatsächlich schon der gesamte Aufwand.

Wie soll das denn gehen? In dem man davor genau sagt, wie lange im Vergleich zu einer Multiplikation eine Subtraktion dauert? Oo Es ist nur der Aufwand an Multiplikationen... Richtig ist nat., dass:
O(Addition) < O(Subtraktion) < O(Multiplikation) < O(Division)
gilt - und die Subtraktionen deshalb lange nicht so schwer ins Gewicht fallen wie die Multiplikationen. Aber wenn du sie bei der Berechnung gleich weglassen willst... Das kannst du immer nur, wenn

Hä?? schrieb:

Addition fällt da nicht ins Gewicht, so lang die Anzahl sich maximal um ein konstantes Vielfaches von der Anzahl der Multiplikationen unterscheidet.

Gilt nat. auch für Subtraktionen - nur eben, dass dieses Vielfache dann kleiner ist...

Jester schrieb:

Die Schulmethode benötigt n Additionen -> O(n^2).

Nein, n Multiplikationen

Jester schrieb:

Eine Subtraktion ist genauso aufwendig wie eine Addition.

Nein?

Jester schrieb:

Karazuba benötigt von Additionen und Subtraktionen insgesamt deutlich weniger als die Schulmethode.

Wie oft subtrahierst du in der Schulmethode denn? Oo

Jester schrieb:

ahja, 2^n geht und 2^n-1 geht nicht... für welches n? Richtig ist: Die Zahl braucht eine 2er-Potenz an Stellen. Das erreicht man aber einfach, indem man die fehlenden Stellen (implizit) mit Nullen auffüllt.

Ja - und damit einen Mehraufwand gegenüber der Schulmethode hat...

Jester schrieb:

Ja, würde ich an Deiner Stelle mal machen, oder hier zumindest keinen Quatsch erzählen. Ist ja nicht schlimm, wenn man das nicht versteht, aber dann sollte man hier nicht so tun als sei das ein ganz großer Mist.

lol... Wenn ich mir hier noch mal all das durchlese, was du geschrieben hast, dann frag ich mich, wer hier weniger Ahnung hat... Der, der Addition nicht von Multiplikation unterscheiden kann und sagt, dass eine Addition genau die selbe Rechenzeit braucht wie eine Subtraktion? Sry, aber das is mir zu doof...

Außerdem habe ich extra am Ende noch mal ausdrücklich geschrieben, dass ich damit nicht sagen will, dass die Methode von K. doof ist oder gar langsamer als die Schulmethode

unskilled schrieb:

aber langsamer sollte er nicht sein, es sei denn, bei der Subtraktion läuft iwas grundsätzlich falsch ^^

Ich wollte damit nur sagen, dass ich den Performance-Gewinn "im Hobby-Bereich" nicht als sooo unendlich viel ansehe... Das ist nat. was komplett anderes, wenn du gerade versuchst, eine neue größte Primzahl zu suchen oder so... Und wenn ich das machen wöllte würde ich davor trotzdem noch eine effektivere Methode suchen (http://de.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen-Algorithmus) - womit ich jz nicht sagen wollte, dass ich ihn angeguckt hätte, aber wenn ich etwas total schnelles brauche und nichts fertiges nehmen will, dann muss ich halt au ma in den sauren Apfel beißen und mir so was so lang angucken, bis ichs verstehe...

bb

[Konstant]

Addition und Subtraktion haben eine kostante Laufzeit, sprich O(1). Beide!

[You are truly...]

@unskilled, wenn man keine Ahnung hat...du kennst den Spruch sicher.

O(Addition)=O(Subtraktion), oder anders gesagt Subtraktionen brauchen nicht getrennt beachtet zu werden, denn a-b=a+(-b). Unäres Minus bedeutet, dass das Vorzeichen gedreht wird, also sicher in konstanter Zeit möglich und somit ist der Aufwand von beiden gleich.
Übrigens gibt es kein < oder > für Mengen, zumindest müsstest du vorher definieren was du damit meinst. Ich schätze mal das Enthaltensein, dafür gibts bereits Symbole, aber da Latex ja derzeit nicht geht kann ich sie dir nicht zeigen. Kannst aber selber Suchen nach "Teilmenge" und "Obermenge".

Jester als ahnungslos zu beschimpfen ist an für sich ja schon eine Frecheit, aber darum gehts jetzt erstmal nicht.

Das Problem ist, dass du nicht einmal erkennst, dass bei der Schulmethode O(n²) Multiplikationen vorkommen und O(n) Additionen (genaugenommen n Additionen).

Aber das spielt alles keine Rolle, da die Anzahl der Additionen in O(n) liegt und für die Anzahl der Multiplikationen gilt ω(n), das heißt die Anzahl der Multiplikationen wächst bei beiden Methoden echt schneller als linear und damit zählt einzig und allein der Aufwand für die Multiplikationen in Abhängigkeit von der Anzahl der Stellen n (wobei n die Anzahl der Stellen der größeren der beiden Zahlen ist).

[Jester]

danke.

btw hat sogar wikipedia die Analyse, samt Additionen und Subtraktionen: http://de.wikipedia.org/wiki/Karatsuba-Algorithmus#Laufzeitanalyse

[unskilled]

Joar - sry... Hatte ich dann auch gelesen - davor hatte ich immer nur von vergleichen á la laufzeit(add) < laufzeit(sub) gelesen... allerdings waren das nie algorithmen sondern immer eher relativ (sehr ^^) alten maschinen, für die das galt...

an die tatsache, dass die laufzeit bei beidem linear ist, hab ich im eifer des gefächts nicht gedacht...

sry

[Jester]

Wobei man sagen muß, dass der Schönhage-Strassen-Algorithmus, den Du verlinkt hast, schon nochmal deutlich effizienter ist. Der Nachteil gegenüber der Methode von Karazuba ist, dass er viel komplizierter ist. Die Korrektheit von Karazuba kann man mit Schulmathematik und ein bißchen nachdenken einsehen. Was aber die Fourier-Trafo im Schönhage-Strassen-Algorithmus zu suchen hat, ist ohne tieferes mathematisches Verständnis nicht so ohne weiteres einzusehen.

Wenn es also um pure Effizienz geht, dann den. Wenn es aber drum geht ein bißchen besser zu sein als die Schulmethode und gleichzeitig noch genau zu verstehen was da abgeht, dann scheint mir Karazuba die einfacher Wahl zu sein.

[life]

Btw. hier mal nen Bild dazu (geklaut von Zahlentheorie Prof):
http://math-www.uni-paderborn.de/~k-heinz/de/forschung/m.gif