Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

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


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

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

Das hört sich wirklich intelligent an, aber da müsste ich alle Algorithmen neuschreiben *schreck*. Ausserdem müsste man doch bei jeder Operation vorher die Operaden auf die neue Basis umrechnen und nacher wieder auf 10 zurück, oder? Denn wenn ich eine symbolische Ausgabe habe mit einzelnen Zahlen drin, siehts schlecht aus wenn die alle die Basis 180 haben Wink Kostet das nicht auch viel Rechenzeit, die ständige Umwandlung?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 15:06:35    Titel:

Also ich habe das einfach so gewählt, dass ich immer die kleinste 10-er Potenz als Basis nehme, die gerade noch geht. Dann ist die Darstellung von

123456789

intern als Liste bezüglich der Basis 10000 z.B.

{6789,2345,1}

Und ich brauche nur die Zahlen ausschreiben, wenn ich die ausgeben möchte. Also keine aufwendige Transformation.

Zur Komplexität der "Umstellung": Ich habe ca. 30 Minuten damals gebraucht, weil das Ausrechnen ja nur an zwei Stellen überhaupt betroffen wird: In den Konstruktoren: "string" -> list<int> und an der Stelle, wo der Übertrag berechnet wird.

Beachte, dass die Ausgabe eine "exotische" Operation darstellt die nur in so 1-5% der Fälle ausgeführt wird und "unwichtig" ist.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 15:17:23    Titel:

algebrafreak hat folgendes geschrieben:

{6789,2345,1}

Und ich brauche nur die Zahlen ausschreiben, wenn ich die ausgeben möchte. Also keine aufwendige Transformation.

Beachte, dass die Ausgabe eine "exotische" Operation darstellt die nur in so 1-5% der Fälle ausgeführt wird und "unwichtig" ist.


Das würde ich nich sagen. Sehr häufig werden Taschenrechner gebraucht, um nur arithmetische Operationen durchzuführen. Wenn also jemand 23482890*1290348+53245 eingibt, sollte ne Zahl in der Basis 10 zurückommen, und nicht deine Zahlenliste aus der höchstmöglichen Basis.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 15:26:26    Titel:

Zitat:
Das würde ich nich sagen. Sehr häufig werden Taschenrechner gebraucht, um nur arithmetische Operationen durchzuführen. Wenn also jemand 23482890*1290348+53245 eingibt, sollte ne Zahl in der Basis 10 zurückommen, und nicht deine Zahlenliste aus der höchstmöglichen Basis.


Da haben wir uns falsch verstanden. Intern halte ich die Zahlen, so wie Du vermutlich auch, als listen von Ints. Nach außen gebe ich natürlich das ganze als Dezimalzahl aus. Was ich mit obigem sagen wollte ist, dass man in O(n) (n ist die Anzahl der listenelemente) die Darstellungen ineinander umrechnen kann. Z.B.

100230823

ist als Liste zu Basis 10000

{823,23,1}

Und um die Auszugeben laufe ich durch die Liste und konkateniere einfach die Strings:

s = "";

while (liste nicht leer) {

nimm das erste Element;
konvertiere es in einen String q;
ergänze vorne noch ein paar 0-Einträge, sodass der String die Länge 4 hat;
s = q + s;

}

D.h.

823 -> "0823"
23 -> "0023"
1 -> "1", weil letzte Zahl.

Alles in O(1).

Was die "Zweckentfremdung" eines CAS als Taschenrechner anbetrifft, so sind die Zahlen, die man da rechnet aus so klein, dass jeder, aber echt jeder auch noch so beschissene Ausgabealgorithmus damit klarkommt.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 15:30:57    Titel:

Ok, danke Very Happy

Nicht aber wenn jemanden interessiert, wie 10000! so aussieht als eine Zahl.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 20 Okt 2005 - 15:40:02    Titel:

Zitat:
Nicht aber wenn jemanden interessiert, wie 10000! so aussieht als eine Zahl.


Das geht bei mir nicht wesentlich langsamer als bei REDUCE oder MuPAD. Ich merke da keinen Unterschied. Ich sollte auch mal einen Timer einbauen.

Ansonsten siehe oben, mein Vorschlag als Speicherung. Nicht als Liste, sondern als balancierten Suchbaum von Multiplikationsfaktoren (Addieren kann man durchaus direkt oder auch nicht. Das ist "kostenlos").

Z.B. 1230000 als

Code:

        *
       / \
     /     \
 {123}   {0,1}


Das ganze ist natürlich nicht reif, weil ich das gerade beim Schreiben erfinde. Da muß man noch paar nächte und flaschen Wodka reinstecken, bis das Konzept "ok" ist.

Der Witz ist, dass bei der Darstellung die Multiplikation in O(1) bzw. O(log n) - wenn man sortiert - geht. Das Problem ist das Addieren solcher Zahlen Sad Aber wenn man auch das nicht direkt macht, dann muss man nur bei Verzweigungen und Ausgaben "rechnen".
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

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

Ich habe es mir angeschaut. Dein ursprüngliches Problem ist, dass Du glaubst, dass Du die Darstellung, von der der Beweis ausgeht, tatsächlich "realisieren" müsstest, indem Du 0-ern vorne addierst. Dem ist nicht so. Denke Dir die 0-Einträge einfach dazu, als ob die da wären.

Z.B. für y = 1 und x = 1234 für m = 2 ist halt

x = 12 * 10^2 + 34
y = 0 * 10^2 + 1

Hier habe ich mit y = 1 als y = 0001 vorgestellt. Und damit ist die Sache gegessen. Es ist bewundernswert, dass nach dem Master-Theorem so ein guter Wert rauskommt. Ist ja fast linear Smile Ich gehe intuitiv schwer davon aus, dass in Praxis die FFT (weiter unten) besser laufen wird.

Man sollte die Basis aber trotzdem so hoch wählen, dass die Integer-Arithmetik gerade noch ohne Überlauf funktioniert. D.h. Du brichst deine Rekursion schon bei Zahlen < 100000 oder so und rechnest die Produkte per Prozessor.

Wenn Du Fragen hast bin ich noch ne Zeitlang im ICQ
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
Seite 3 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