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).
[Algorytmy] Wydajny algorytm dzielenia liczb
[Algorytmy] Wydajny algorytm dzielenia liczb
Ostatnio zmieniony 21 maja 2012, o 11:58 przez Afish, łącznie zmieniany 1 raz.
Powód: Brak tagów w nazwie tematu.
Powód: Brak tagów w nazwie tematu.
-
- 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
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!
\(\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 .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .