Dzielenie bignumów

Odpowiedz Nowy wątek
2007-06-27 19:53
mmpk
0

Witam!

Czy ktoś zna jakiś algorytm dzielenia dużych liczb (nie mieszczących się w zakresach std. typów danych? O ile implementacja gdy dzielna jest bignumem, a dzielnik intem jest łatwa, o tyle gdy obie zmienne są bignumami nie jest już tak łatwo. Czy ktoś zna jakiś prosty (i wydajny) algorytm dzielenia dwóch dużych liczb?

Pozostało 580 znaków

2007-06-27 22:50
piotrek86
0

Prosty, aczkolwiek skuteczny sposób polega na "przyspieszonym" odejmowaniu i zliczaniu. Zalozmy ze dzielisz a / b. Wtedy za pierwszym razem odejmujesz b, potem 2b, 4b itd. Gdy a < 0 cofasz ostatnio odjety skladnik i odejmujesz od nowa b, 2b, 4b itd. Oczywiscie caly czas odpowiednio aktualizujesz licznik. Gdy a = 0 to algorytm sie konczy.

Pozostało 580 znaków

2007-06-27 23:09
0

bardzo fajna metoda (podoba mi się idea, ale podkreślam że to tylko moja opinia) polega na wyszukiwaniu binarnym po wyniku :-)

http://main.niedasie.mimuw.edu.pl/user.phtml?op=lesson&n=32
http://main.niedasie.mimuw.edu.pl/user.phtml?op=lesson&n=33


Pozostało 580 znaków

2007-06-28 09:41
0

Jeszcze inny pomysł to zrobienie tego algorytmem dzielenia "pod kreskę". Ilość obrotów pętli która to liczy będzie proporcjonalna do ilości cyfr w dzielniku. Inna spraw to wydajność samego dopasowania i wyliczania reszt no ale coś za coś.

Pozostało 580 znaków

2007-06-28 10:14
0

Mi się podoba taki algorytm z przesuwaniem i odejmowaniem np.
8641982 / 6542
przyrównujemy i odejmujemy

8641982
6542
_______
2099982
6542

Widać że dalej odejmować nie można liczymy odejmowania i dodajemy do odpowiedzi, czyli zapisujemy odp=1

2099982
.6542
_______
1445782
.6542
_______
.791582
.6542
_______
.137382
.6542

3 odejmowania, odp = odp*10 + 3, czyli 13

.137382
..6542
_______
..71962
..6542
_______
...6542
..6542

2 odejmowania odp: 132

...6542
...6542
_______
      0

Odp: 1321 :P

Mam nadzieje, ze załapałes : PP

Pozostało 580 znaków

2007-06-28 15:32
0

http://en.wikipedia.org/wiki/Division_(digital)
Tam masz całkiem niezły spis algorytmów dzielenia. Ogólnie, zwykłe powolne dzielenie (np. takie, jakie powyżej opisał Spykaj, na dodatek chyba najprostsze w implementacji) jest całkiem niezłe, te szybsze algorytmy wyprzedzają je dopiero przy dość znacznych rozmiarach danych (rzędu kilkuset do tysiąca bitów).
Pisałem kiedyś w FPC BigNumy i algorytm Karatsuby mnożenia jakoś strawiłem i udało mi się zakodować, ale szybkie dzielenie w analogiczny sposób (tj. algorytm Goldschmidta) przerosło moją cierpliwość, zdolność pojmowania i termin oddania pracy. ;]

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