[Lewo]

Podrzuci ktoś prosty i w miarę wydajnym algorytm dzielenia dwóch liczb naturalnych ( bez reszty ), żeby dało się przyjemnie zaimplementować na asembler/maszynę rejestrową ( czyli dobrze będzie dzielić / mnożyć przez 2 ( SHR / SHL ) lub in(de)krementować daną liczbę o 1)?
Modulo potem też mam do zrobienia, więc jeśli będzie dało się zmodyfikować chętnie zobaczę jak
#informatyka #programowanie

[Kaczus2B]

@Lewo: tu masz pierwiastkowanie - znajdowanie metoda polowienia http://teleinfo.pb.edu.pl/krashan/articles/pierwiastkowanie/

[pikej100]

@Lewo: A co jest nie tak ze standardowym algorytmem odejmowania, że szukasz czegoś bardziej wyrafinowanego?

[Lewo]

@pikej100: szukam dzielenia, mam coś takiego http://stackoverflow.com/questions/2390354/where-can-i-find-soft-multiply-and-divide-algorithms
tylko nie rozumiem kroku 4
"Subtract divisor register from dividend register and change the bit to 1 in the result register at the bit that corresponds with the total number of shifts done to the divisor register."
ten subtract po co? żeby wyliczyć resztę?

[pikej100]

@Lewo: Nie wiem czy tak ten algorytm się nazywa (być może nie ma w ogóle nazwy), ale chodzi o dzielenie przez odejmowanie. Tak jak mnożenie to wielokrotne dodawanie to dzielenie to wielokrotne odejmowanie.

Od dzielnej odejmujesz dzielnik dopóki dzielna >= dzielnik. Liczba odejmowań to wynik dzielenia, jeśli na końcu nie dostaniesz 0 to wartość, która zostaje to reszta z dzielenia. Chyba nie da się już bardziej uprościć ( ͡° ʖ

[Lewo]

@pikej100: myślałem, że to jest to samo co http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
bo wtedy by to nie był dobry alogrytm ( ten z stacka ) na procka ( operacja odejmowania więcej kosztuje niz przesunięcie bitowe i jeszcze wymaga ustawienia drugiego argumentu w odpowiednim rejestrze )
a ten z tego linku ma koszt(złożoność): a/b * koszt_przesuniecia

[pikej100]

@Lewo: A to nie pomogę w takim razie

[Lewo]

@pikej100: jakbys był ciekawy, to mnożenie można zrobić przez dodawanie ( mało wydajnie ) lub też przez przesunięcia bitowe ( metoda rosyjskich chłopów ). Jak będziesz ciekawy to przetestuj ( powinno dać się odczuć różnicę mimo, że kompilator może metode przez dodawanie zoptymalizować )