[Algorytmy] Wydajny algorytm dzielenia liczb

apnk
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 17 maja 2012, o 21:35
Płeć: Mężczyzna
Lokalizacja: Wrocław

[Algorytmy] Wydajny algorytm dzielenia liczb

Post autor: apnk »

Witam,
mam wielki problem. Jestem w trakcie pisania kompilatora i potrzebuję jakiegoś szybkiego algorytmu dzielenia. Dzielone będą liczby naturalne, wynikiem też ma być liczba naturalna. Dzielenie przez zero daje zero (ale to raczej nie ważne). Problem jest taki że mam ograniczoną ilość instrukcji, do dyspozycji max 4 zmienne na raz (4 rejestry ale im mniej tym lepiej) i algorytm powinien wykonywać się w czasie logarytmicznym. Dostępne jest dodawanie, odejmowanie, dzielenie przez 2, sprawdzanie czy liczba = 0, sprawdzanie czy liczba > 0 oraz czy liczba jest nie parzysta.
Do mnożenia znalazłem algorytm rosyjskich chłopów i chodziło by mi o coś w tym stylu ale dla dzielenia. Taki algorytm musi istnieć bo algorytm rosyjskich chłopów wykorzystuje dokładnie te instrukcje które są dostępne, a wykładowca raczej nie dawał by algorytmu który jest nie możliwy do wykonania.
Jeżeli ktoś zna jakiś taki magiczny sposób to będę bardzo wdzięczny (oczywiście nie mówię żeby ktoś wymyślił za mnie ten algorytm, po prostu pytam czy ktoś zna takowy).
Ostatnio zmieniony 21 maja 2012, o 11:58 przez Afish, łącznie zmieniany 1 raz.
Powód: Brak tagów w nazwie tematu.
olekp
Użytkownik
Użytkownik
Posty: 31
Rejestracja: 8 maja 2012, o 09:14
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy
Pomógł: 2 razy

[Algorytmy] Wydajny algorytm dzielenia liczb

Post autor: olekp »

Ja bym spróbował coś podobnego do tego .
apnk
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 17 maja 2012, o 21:35
Płeć: Mężczyzna
Lokalizacja: Wrocław

[Algorytmy] Wydajny algorytm dzielenia liczb

Post autor: apnk »

niestety nie mam dostępu do konkretnych bitów liczby.
Fibik
Użytkownik
Użytkownik
Posty: 953
Rejestracja: 27 wrz 2005, o 22:56
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 11 razy
Pomógł: 74 razy

[Algorytmy] Wydajny algorytm dzielenia liczb

Post autor: Fibik »

Może z Newtona: \(\displaystyle{ x = \frac{m}{n}}\), zatem obliczamy \(\displaystyle{ \frac{1}{n}}\) i mnożymy przez \(\displaystyle{ m}\).

\(\displaystyle{ f \left( x \right) = \frac{1}{x} - n}\); i szukamy zero \(\displaystyle{ f \left( x \right)}\):

\(\displaystyle{ x = x - \frac{f \left( x \right) }{f' \left( x \right)} = x + \left( \frac{1}{x} - n \right) x^2 = x \left( 2 - nx \right)}\)

Można od razu obliczać, ale na rzeczywistych.

A na całkowitych chyba też jakoś można.
Po prostu traktujemy te liczby jako ułamki binarne,
np. liczba \(\displaystyle{ 7 = 111}\) binarnie, będzie wtedy taka: \(\displaystyle{ \frac{7}{2^b} = 0.0 \ldots 0111}\), gdzie: \(\displaystyle{ b}\) - długości słowa.

Startujemy chyba z \(\displaystyle{ x = 2-n}\); ale traktujemy to jak liczbę bez znaku.

szybciej będzie tak:
\(\displaystyle{ \frac{1}{1-q} = 1 + q + q^2 + ... = \left( 1+q \right) \left( 1+q^2 \right) \left( 1+q^4 \right) \left( 1+q^8 \right) ...}\)

\(\displaystyle{ n = 1-q}\), czyli wsadzamy: \(\displaystyle{ q = 1-n}\); i oczywiście \(\displaystyle{ n < 1}\)
(sama mantysa, czyli jakby dzielone przez \(\displaystyle{ 2^b}\), czyli przecinek przesunięty o \(\displaystyle{ b}\) pozycji w lewo).

To ma potężną zbieżność i jest stosowane obecnie w nowoczesnych procesorach.-- 23 maja 2012, 00:46 --Nie pajacuj z tymi upomnieniami odnośnie kodowania.
To jest sprawa czytelności zapisu vs czas pisania.

W prostych wzorach nie używamy w ogóle latexa, np.: 17;
koniec przykładu.

Oj, te dzieciak, daj takiemu patyk, a ten zaraz znajdzie sobie... ofiarę, hehe!
Ostatnio zmieniony 22 maja 2012, o 09:57 przez Afish, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
ODPOWIEDZ