Witam, przerabiam książkę Algorytmy struktury danych i technik programowania - Wróblewskiego i
mam taki problem z jednym aspektem tej książki, tzn. z szybkim mnożeniem.
N jest to liczba bitów
i tu mam pytanie, jeżeli dla przykładowych danych X=Y=20 to ile będzie wynosić A i B?
Jeśli dobrze rozumiem zadanie (nie za dużo kontekstu podałeś, ale rozumiem że więcej nie masz).
Tak czy inaczej, chodzi chyba o to że liczba X składa się w swojej reprezentacji z 2 połówek - prawdopodobnie dlatego że nie mieści się w zwykłym int (ale naprawdę, to ty a nie ja wiesz czego dokładnie dotyczy tego algorytm). Załóżmy (dla uproszczenia) że każda połówka ma 8 bitów (żeby to miało sens, powinna mieć co najmniej 32 bity, ale to tylko taki przykład)
/ A \ / B \
X = [x x x x x x x x] [x x x x x x x x]
Teraz zakładając na przykład że X = 20, dziesiętnie będzie to wyglądało
X = (0) (20)
Czyli A = 0 i B = 20.
A dla x = 258 (max dla 8 bitów to wartość 255)
A = 1 i B = 3
(A * 255 + 3 = 258)
To mi wygląda na algorytm Karatsuby. Na necie jest pełno wyjaśnień tego algorytmu.
zdaje się, że tak i sposób rozwiązania tego metodą "dziel i zwyciężaj"
kurcze nie moge ;/
caly dzien sie z tym mecze i nic...
we wprowadzeniu do algorytmów nic nie mam na ten temat nie mogę znaleźć,
w necie jest algorytm na system 10 a ja bym wolał pod 2 podobny jak mój + "dziel i zwyciężaj" (system 10 tylko mi zagmatwa sprawę w książce)
Kiedyś popełniłem algorytm do szybkiego liczenia liczb Fibonacciego: http://www.ideone.com/EbJET
Na wejściu jest numer liczby, na wyjściu kolejno: przybliżona długość liczby w systemie dziesiętnym oraz sama liczba (tyle, że wykomentowałem to bo bardzo długo się wykonuje toString na takim dużym BigIntegerze).
Algorytm korzysta z algorytmu Karatsuby.
nie znam javy, ale spróbuje to przetłumaczyć na C++
No nie wiem czy dobrze działa. Nie twierdzę, że źle, ale po prostu nic za "return xy" nie jest wykonywane. Dla intów N wyjdzie zawsze < 32, więc zawsze od razu wykona się return xy. BigIntegery spokojnie mogą osiągać długość wielu tysięcy bitów, ale zwykłe inty mają stały, niewielki rozmiar.
Poza tym log() i pow() są wolne i przeznaczone przede wszystkim dla doubli. Skorzystaj z: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn do liczenia logartmu o podstawie 2, oraz wiedz, że zapis 1 << N w C++ wygeneruje ci liczbę 2 do potęgi N.
a * pow(2, N) = a * (1 << N) = (a << N)
Edit:
OK, widzę że usunąłeś kod.
Masz gotowca: http://www.ideone.com/FjHPM
PS: Moja wersja (tzn wzorki, a w ogóle to nie moja bo znalezione na necie) jest trochę inna. Lekka przeróbka załatwi sprawę. Złożoność jest identyczna za to.
Poza tym w tych wzorkach wydaje mi się, że jest błąd - powinno być AC2N, a nie AC2</sup>(N/2).