Dzielenie bignumów

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?

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.

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

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

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

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. ;]

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