Mnożenie metodą Karatsuba

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
atch7
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 1 cze 2011, o 13:55
Płeć: Mężczyzna
Lokalizacja: Irlandia

Mnożenie metodą Karatsuba

Post autor: atch7 »

Czy mógłby mi ktoś wytłumaczyć (pokazać krok po kroku na przykładzie) jak dokonać mnożenia za pomocą metody Karatsuba?
Główny problem jaki napotkałem to nie zrozumienia jak to działa ale jak to wykorzystać kiedy masz do dyspozycji typ (resultat) zdolny do przechowywania tylko 5 miejsc (liczby z zakresu -99999 do 99999).
Ja zacząłem to robić tak (2839745624 * 8769342123):
Podziel pierwszą i drugą liczbę na dwie części:
a_h 28397 a_l 45624 Liczba 1: 2839745624
b_h 87693 b_l 42123 Liczba 2: 8769342123
Produkt z tych liczb jeszcze za duży więc konieczny jest dalszy podział:
a_h 28 a_l 397 Liczba 3: 28397
b_h 45 b_l 624 Liczba 4: 45624

a_h 87 a_l 693 Liczba 5: 87639
b_h 42 b_l 123 Liczba 6: 42123

Kolejny podział:
a_h 2 a_l 8
b_h 39 b_l 7
a_h 4 a_l 5
b_h 62 b_l 4
a_h 8 a_l 7
b_h 69 b_l 3
a_h 4 a_l 2
b_h 12 b_l 3

Teraz kiedy mamy już liczby których produkt zmieści się w nasz typ możemy dokonać mnożenia:

a = a_h + a_l
b = b_h + b_l
A = a_h * b_h
B = a_l * b_l
C = a * b
K = C - A - B
R = A*10^2+K*10+B

28*397= 11116
45*624= 28080
87*693= 60291
42*123= 5166

I teraz nie wiem co z tym zrobić. Jak z tych czterech produktów uzyskać:
2.49027E+19 = 2839745624 * 8769342123
Dziekuje za kazda pomoc
ODPOWIEDZ