Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Karatsuba Multiplikation bei verschieden langen Zahlen
Gehe zu Seite 1, 2, 3  Weiter
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: 17 Okt 2005 - 10:47:26    Titel: Karatsuba Multiplikation bei verschieden langen Zahlen

Hallo,

Ich möchte die Karatsubamultipikation programmieren. Dazu hab ich mir folgenden kurzen Artikel durchgelesen:
http://en.wikipedia.org/wiki/Multiplication_algorithm#Karatsuba_multiplication


Ich kann die Methode aber nur bei gleich langen Zahlen nachvollziehen, und wenn die Länge der Zahlen ungerade ist, gehts auch nicht.

Wie wende ich also dieses Verfahren an bei z.B. 123*3245 oder 789*456? Dort steht zwar:
Zitat:
if n is odd instead, or the numbers are not of the same length, this can be corrected by adding zeros at the left end of x and/or y


Aber ich kann damit nichts anfangen, denn 0123 ist rechnerisch ja genau das gleiche wie 123.

Ich hoffe jemand kann mir helfen.

Grüsse, Marko
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 17 Okt 2005 - 10:50:53    Titel: Re: Karatsuba Multiplikation bei verschieden langen Zahlen

Zitat:
if n is odd instead, or the numbers are not of the same length, this can be corrected by adding zeros at the left end of x and/or y



Dort steht, wenn n ungerade oder die Zahlen nicht gleich lang sind, dann muss man an den Zahlen die entsprechende Anzahl Nullen davor setzen.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 17 Okt 2005 - 11:18:06    Titel: Re: Karatsuba Multiplikation bei verschieden langen Zahlen

Gauss hat folgendes geschrieben:

Dort steht, wenn n ungerade oder die Zahlen nicht gleich lang sind, dann muss man an den Zahlen die entsprechende Anzahl Nullen davor setzen.


Ich weiss was dort steht Wink Deswegen auch der Satz der gleich danach kommt:
Zitat:

Aber ich kann damit nichts anfangen, denn 0123 ist rechnerisch ja genau das gleiche wie 123.


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


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 17 Okt 2005 - 11:53:14    Titel: Re: Karatsuba Multiplikation bei verschieden langen Zahlen

fas hat folgendes geschrieben:
Wie wende ich also dieses Verfahren an bei z.B. 123*3245 oder 789*456? Dort steht zwar:


Ich würde das dann so machen 123*3245=0123*3245 und 789*456=0789*0456.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 17 Okt 2005 - 12:42:28    Titel:

Ja, so hab ich das ja gemacht, und ich gesagt, dass es so nicht geklappt hat. Denn: Bei 0123 ist x1=01 (und y1=23) und wenn man damit rechnet ist das Ergebnis am Ende falsch.
daysleeper
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 08.09.2005
Beiträge: 899
Wohnort: ESSEN

BeitragVerfasst am: 17 Okt 2005 - 14:28:22    Titel:

ich verstehe das system nicht mal
zerlege mir bitte mal die zahlen x= 4682 und x=2468
nach dem schema : x = x1 W^m + x2
sobald ich das verstanden habe, kann ich dir evtl. helfen.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 17 Okt 2005 - 16:31:56    Titel:

Mach ich doch glatt:

x1=46
W^m=10^2=100
x2=82

bei 2368 sind x1 und x2 demnach 23 und 68, einfach in der Mitte teilen.

Gruss
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 17 Okt 2005 - 18:48:54    Titel:

Ich denke mal es wird jede Ziffer in einen extra Speicher gespeichert, dann musst du auch die Null in einen extra Speicher setzen.
Entschuldigung wenn ich schon wieder Falsch liege, denn ich habe mir das Programm nicht angeguckt.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 18 Okt 2005 - 13:51:42    Titel:

Sag mal. Wie lange braucht dein CAS um 10000! zu berechnen? Sollte so im Bereich einer Sekunde samt Ausgabe in die Konsole laufen Smile
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 20 Okt 2005 - 03:25:24    Titel:

algebrafreak hat folgendes geschrieben:
Sag mal. Wie lange braucht dein CAS um 10000! zu berechnen? Sollte so im Bereich einer Sekunde samt Ausgabe in die Konsole laufen Smile


Ich glaube du siehst nicht mehr ganz klar Very Happy 10000! schafft nicht mal Mupad (und Mupad ist schnelllll) innerhalb meiner Geduldsfrist.
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 1, 2, 3  Weiter
Seite 1 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