problem z szybkim mnożeniem

Odpowiedz Nowy wątek
2011-08-18 19:19
0

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.

user image

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?

edytowany 2x, ostatnio: shadoq, 2011-08-18 19:25

Pozostało 580 znaków

2011-08-18 21:03
msm
0

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)

Pozostało 580 znaków

2011-08-18 21:19
0

To mi wygląda na algorytm Karatsuby. Na necie jest pełno wyjaśnień tego algorytmu.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-19 11:11
0

zdaje się, że tak i sposób rozwiązania tego metodą "dziel i zwyciężaj"

Pozostało 580 znaków

2011-08-19 14:29
0

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)

Pozostało 580 znaków

2011-08-19 15:21
0

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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
BigInteger ssie. Zarówno mnożenie jak i toString. - Krolik 2011-08-26 21:56
To zacommituj patcha do OpenJDK :P - Wibowit 2011-08-26 22:06
Nota bene: BigInteger z C# jest niby lepszy? - Wibowit 2011-08-26 22:17
Patcha? Proszę bardzo: http://futureboy.us/temp/BigInteger.java Patch jest dostępny od kilku lat, problem w tym, że ani Sun, ani Oracle nie mają jaj aby go wdrożyć, bo boją się, że się coś zepsuje, mimo że gościu dostarczył im spory zestaw własnych testów regresji (swoją drogą okazało się, że Sun takowych testów dla BigIntegera nie ma). Link do dyskusji: http://mail.openjdk.java.net/[...]ibs-dev/2009-June/001761.html - Krolik 2011-08-27 09:38

Pozostało 580 znaków

2011-08-19 17:47
0

nie znam javy, ale spróbuje to przetłumaczyć na C++

edytowany 1x, ostatnio: shadoq, 2011-08-19 17:55

Pozostało 580 znaków

2011-08-19 18:07
0

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/[...]hacks.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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-08-19 18:09

Pozostało 580 znaków

2011-08-19 18:23
0

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).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-08-19 20:09

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0