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

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

@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

Don Quijote

Da ist ja einiges zusammengekommen, danke.

Auch für die Diskussion, die hat mir geholfen.

Dennoch denke ich, dass mein Geschwindigkeitsverlust nicht nur an diesem Algorithmus liegt, sondern an meinem Code generell, sprich Strings als Behälter der Ziffern oder andere Funktionen von mir.

Kann mir jmd nen Profiler nennen und vlt. nen tutorial im internet(ich find da nix passendes), da ich keine ahnung habe, wie ich solche anwende.

Danke schonmal

drakon

Kann mir jmd nen Profiler nennen und vlt. nen tutorial im internet(ich find da nix passendes), da ich keine ahnung habe, wie ich solche anwende.

ADM Code Analyst. Eine Einführung gibts irgendwo auf der Seite des Programmes.

EDIT:
Download:
http://developer.amd.com/cpu/CodeAnalyst/codeanalystwindows/Pages/default.aspx

Einführung:
http://developer.amd.com/documentation/articles/pages/1212200690.aspx

Don Quijote

Danke für die schnelle Antwort drakon

drakon

Don Quijote schrieb:

Danke für die schnelle Antwort drakon

Und weils Heute schönes Wetter war, gibts sogar noch editierte Links.

Don Quijote

Ist der nur Für AMD Prozessoren oder kann man den auch bei Intel Prozessoren verwenden?

drakon

Don Quijote schrieb:

Ist der nur Für AMD Prozessoren oder kann man den auch bei Intel Prozessoren verwenden?

Geht auch für Intel.

Don Quijote

Danke, falls ich probleme bekommen sollte, dann melde ich mich .

mfg

Don Quijote