Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Karatsuba Multiplikation bei verschieden langen Zahlen
Gehe zu Seite Zurück  1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Karatsuba Multiplikation bei verschieden langen Zahlen
 
Autor Nachricht
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 10:50:09    Titel:

Ach was.

Code:

REDUCE 3.8, 15-Apr-2004, patched to 30-May-2005 ...

1: on time;

Time: 0 ms

2: factorial(10000)$

Time: 110 ms


Oder auch so, damit wir uns sicher sind, er speichert nicht eine Liste von den ersten 10000 Fakultätwerten Smile

Code:

REDUCE 3.8, 15-Apr-2004, patched to 30-May-2005 ...

1: on time;

Time: 0 ms

2: p := 1; for i := 1 : 10000 do p := p * i;

p := 1

Time: 0 ms


Time: 720 ms  plus GC time: 90 ms
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 11:31:40    Titel:

Wie zur Hö**e funktioniert das so schnell :S
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 11:53:17    Titel:

REDUCE ist dafür bekannt, dass die IntMult schnell ist. Wie gesagt: Ich habe die Sourcen. Wenn Du die IntMult von REDUCE sehen willst, so musst Du es mir nur sagen.

Ich habe irgendwie den Verdacht, dass man das durch lazy Evaluation erreichen kann. Indem man statt z.B. bei 1000 * 999! das Zeug auszurechnen einfach "1000 * 999 * 998 ... * 2" abspeichert. Ich meine das wäre auch aus der Sicht vom Benutzer sinnig, denn die meisten Mutiplikationen werde im nächsten Schritt wieder auseinanderdividiert. Demnach verschiebt man die Multiplikationszeit auf ein Speicherproblem.

Mir schwebt da so eine Heap-Datenstruktur für "Int" im Kopf, in der einfach die Faktoren in der Liste stehen. Und wenn man z.B. 10000 * 100 hat, dann kann man das Neubalancieren durch 1000 * 1000. oder 100 * 100 * 100, was den Vorteil hat, dass man immer mit kleineren Zahlen zu tun hat. Oder z.B. die Teilbarkeitshalbordnung abspeichern. Wäre ein eine Idee.

Ich sage aber nicht, dass dem so ist in REDUCE.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 12:02:20    Titel:

Den Source würde ich wohl kaum verstehen, aber kannst Du vielleicht schnell die Merkmale davon erklären?

Basiert dein Algo darauf, wie bei der Schulmethode, alles mit allem zu multiplizieren und am Ende die Resultate zu addieren?
So mach ich das jedenfalls bis jetzt, und versuche das zu kombinieren mit Karatsuba.

Was ist es, was Reduce so unglaublich schnell macht (abgesehen von der Lowlevel-Programmiersprache)?

Gruss
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 12:29:02    Titel:

Damit wir uns nicht falsch verstehen: REDUCE ist ein bekanntes CAS, eines der ältesten überhaupt (glaube sogar älter als Maple). Und ich habe das nicht programmiert. Ich wollte nur mit den obigen Beispielen zeigen, dass es schneller geht. Mein IntMult Algorithmus braucht deutlich länger als das von Reduce, weil ich eine nicht effiziente Ablaufverwaltung habe. Und ich weiß auch nicht wirklich, wie Reduce geht. Schaue aber bald nach.

Was ich mit Sicherheit sagen kann: Mit Schulmethode wird man nicht weit kommen, da die Anzahl der Operationen quadratisch in der Anzahl der Stellen ist. Das ist Käse, man will auf jeden Fall ne Stufe runter. Z.B. Divide&Conquer.

Worauf ich aber oben hinaus wollte ist die Frage: Wann braucht man einen Wert zur Berechnung in CAS?

Und die Antwort ist: Im Wesentlichen bei Vergleichen, wenn der Kontrollfluß gesteuert werden soll! D.h. davor muß man das Zeug nicht ausrechnen!

Und darauf kann man sich eine schöne Theorie basteln:

Wenn man a := 1000! als eingabe bekommt, dann schreibt man einfach (a,!(1000)) in den Speicher rein => 0 ms Zeit. Nur dann, wenn es heißt if (a < 10) b := 1; else b := 2;

Dann prüft man ob der Wert 1000! das erfüllt oder nicht.

Ich glaube REDUCE macht vieles so.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 12:44:26    Titel:

Hallo,

Ich weiss, dass die Schulmethode eine quadratische Zeitkomplexität hat, aber deswegen möchte ich ja Karatsuba anwenden, um auf O(~1.53) zu kommen.

Das mit dem Vergleichen ist ja ne schöne Idee, aber wenn jemand in die Eingabe 1000! tippt, erwartert er ne Zahl, und nicht seine Eingabe zurück. Da du jetzt Zeit zu haben scheinst: Möchtest du nicht nen Augenblick auf Karatsuba werfen? Wink Ist nicht schwer, abgesehen von meinem Problemchen Wink

Die Idee mit dem Vergleichen finde ich sogar so schön, dass ich mir überlege, Operanden einer booleschen Operation vorerst unberechnet sein zu lassen!

Gruss, Marko
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 12:51:06    Titel:

Zitat:
Da du jetzt Zeit zu haben scheinst:


Das ist ein Irrtum. Ich habe gerade gekocht und anschließend gegessen. Während dessen habe ich die paar Antworten geschrieben. Und jetzt geht es wieder an REX, NL und DSPACE. Ich werde mich sofort nach meinen Diplomprüfungen in zwei Wochen darum kümmern. Kleinere Fragen kann ich hingegen auch so beantworten.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 13:02:01    Titel:

Zitat:
aber wenn jemand in die Eingabe 1000! tippt, erwartert er ne Zahl, und nicht seine Eingabe zurück


Hast Du schon mal 10000! gebraucht? Ich hoffe nicht. Man sollte da in ein wenig größeren Ausmaßen denken. Es ist auch klar, dass bei der Ausgabe man alles ausrechnen muss. Was ist aber mit den 9999 zwischenergebnissen, die dabei entstehen? Muss man die ausrechnen? Ich würde sagen nein. Das Beispiel mit 10000! ist ja extra so gewählt, weil man da wenig im Ablauf optimieren kann. Wenn man aber z.B. die Teilbarkeitsrelation sich anschaut von 10000!, so sieht man, dass da mindestens 10^10 enthalten ist. Analoges gilt für die anderen Primfaktoren. Die Multiplikation von 10^10 ist aber geschenkt. Vergleiche aber die Multiplikation von

123000 * 456000

mit der von 123*456 und Shift um 6 Stellen nach links. Das erste kann man mit der ALU vom Rechner machen, kostet 2-3 Prozessortakte. Das andere geht bei geschickter Speicherung in O(1), denn man braucht nur die Potenz zu setzen. Mit der Schulmethode hast Du aber 6 Additionen!

Was anderes: In welcher Basis rechnest Du intern?
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 13:51:04    Titel:

algebrafreak hat folgendes geschrieben:
Kleinere Fragen kann ich hingegen auch so beantworten.


Das ist eine kleine Frage Embarassed

Zitat:

Was anderes: In welcher Basis rechnest Du intern?


10 natürlich Very Happy
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 14:11:45    Titel:

Zitat:
10 natürlich


Viel Spaß damit. Willkommen im Club der nicht effizienten Programmierer! Spaß bei Seite: Du solltest bei der Schulmethode mit einer solchen Basis rechnen, bei der (b-1)^2 gerade noch im int-Bereich deiner Maschine liegt. Also

int_max > (b-1)^2 <=>
sqrt(int_max) > b-1 <=>
b < sqrt(int_max) + 1.

Also bei short int mit int_max = 32768 mit einer Basis von etwa 180.

Warum? Denn beim Multiplizieren der Stellen hast Du eine Multiplikation aller Stellen plus Übertrag + modulo Operation. Und die sollte man vom Prozessor rechnen lassen.

Ich benutze eine einstellbare Basis. Zurzeit rechne ich zur Basis 10000
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Karatsuba Multiplikation bei verschieden langen Zahlen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3  Weiter
Seite 2 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum