pytanie dotyczące mnożenia karatsuba:

Question

Chcę zaimplementować Karatsuba's 2-split multiplication w języku Python. Jednak zapisywanie liczb w postaci

A=c*x+d 

gdzie x to moc podstawy (let x = b^m) zbliżona do sqrt (A).

Jak mam znaleźć x, jeśli nie mogę nawet używać podziału i mnożenia? Czy powinienem policzyć liczbę cyfr i przesunąć A w lewo o połowę liczby cyfr?

Dzięki.

Answer 1

Prawie. Nie zmieniasz A o połowę liczby cyfr; zmieniasz 1. Oczywiście, jest to efektywne tylko wtedy, gdy podstawa jest potęgą 2, ponieważ "przesunięcie" w podstawie 10 (na przykład) musi zostać wykonane przy pomocy multiplikacji. (Edycja:. Dobrze, ok, może pomnożyć ze zmianami i uzupełnieniami Ale to jest zawsze tak dużo prostsze o mocy 2.)

Jeśli używasz Pythona 3.1 lub nowszy, licząc bity jest łatwe, ponieważ 3.1 wprowadził metodę int.bit_length(). W przypadku innych wersji Pythona, możesz policzyć bity, kopiując A i przesuwając je w prawo, aż do 0. Można to zrobić w czasie O (log N) (N = liczba cyfr) z rodzajem metody wyszukiwania binarnego - przesunięcie o wiele bitów, jeśli jest 0 to, że było zbyt wielu, itp

Answer 2

już akceptowane odpowiedź odkąd zacząłem pisać, ale:

Co Tom powiedział: w Pythonie 3.x można dostać n = int .bit_length() bezpośrednio. W Pythonie 2.x uzyskasz n w czasie O (log2 (A)) przez binarne wyszukiwanie, jak poniżej.

Oto kod (2.x), który oblicza oba. Niech wykładnik bazowy 2 x równy n, tj. X = 2 ** n.

Najpierw otrzymujemy n przez wyszukiwanie binarne przez przesunięcie. (Naprawdę potrzebowaliśmy tylko n/2, więc to jedna niepotrzebna ostatnia iteracja). wtedy, gdy wiemy, n, coraz X, C, d jest łatwe (jeszcze nie stosując podział)

def karatsuba_form(A,n=32): 
    """Binary-search for Karatsuba form using binary shifts""" 
    # First search for n ~ log2(A) 
    step = n >> 1 
    while step>0: 
     c = A >> n 
     print 'n=%2d step=%2d -> c=%d' % (n,step,c) 
     if c: 
      n += step 
     else: 
      n -= step 
     # More concisely, could say: n = (n+step) if c else (n-step) 
     step >>= 1 
    # Then take x = 2^(n/2) ˜ sqrt(A) 
    ndiv2 = n/2 
    # Find Karatsuba form 
    c = (A >> ndiv2) 
    x = (1 << ndiv2) 
    d = A - (c << ndiv2) 
    return (x,c,d) 

Answer 3

Twoje pytanie jest już odpowiedź w artykule, do której mowa: „Podstawowym krokiem Karatsuba za prace dla każdego bazowego B i każdy m, ale rekurencyjny algorytm jest najbardziej wydajny, gdy m jest równe n/2, zaokrągloną w górę”... n oznacza liczbę cyfr, i 0 < = value_of_digit < B.

Niektóre perspektywicznym, który może pomóc :

Jesteś dozwolone (i wymagane!), Aby użyć elementarne operacje takie jak number_of_digits // 2 i divmod(digit_x * digit_x, B) ... w szkolnej arytmetyki, gdzie B to 10, jesteś wymagany (na przykład), aby wiedzieć, że divmod(9 * 8, 10) produkuje (7, 2).

Podczas implementowania arytmetyki dużej liczby na komputerze, zwykle B jest największą potęgą 2, która będzie wygodnie obsługiwać elementarną operację mnożenia. Na przykład w implementacji CPython na maszynie 32-bitowej wybrano, że B wynosi 2 ** 15 (to jest 32768), ponieważ wtedy product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; działa bez przepełnienia i bez obaw o bit znaku.

Nie jestem pewien, co próbujesz osiągnąć za pomocą implementacji w Pythonie, która używa B == 2, z liczbami reprezentowanymi przez int Pythona, którego implementacja w C już używa algorytmu Karatsuba do mnożenia liczb, które są wystarczająco duże aby było warto. To nie może być szybkość.

Jako ćwiczenie do nauki, możesz spróbować reprezentować liczbę jako listę cyfr, przy czym podstawa B jest parametrem wejściowym.