W matematyce wedyjskiej występuje szczególny przypadek dzielenia przez liczby np. 29, 39. Wykonuje się to dzieląc przez najbliższą dziesiątkę oraz dodanie poprawki.
Spróbowałem, czy sztuka taka uda się w ogólności. I udaje się.
Przedstawmy dzielnik w zapisie binarnym, oraz sprawdźmy, ile ma fragmentów złożonych z samych jedynek 1...1. Jeżeli tych jedynek jest więcej niż jedna, wykonamy dwa działania, na pozycji zera poprzedzającego oraz ostatniej jedynki. Gdy jedna, operacje wykonamy tylko dla tej pozycji. Potrzebujemy zmienną pomocniczą, z której liczymy kolejne poprawki, oraz je odejmujemy (przed, na jedynej) grupą jedynek, Poprawki dodajemy nad jedynką konczącą fragment. Zmienna ta przybliża się do ilorazu.
A jakie działania? Zamiast dzielnika rozważamy jego kolejne aproksymacje, i dzielimy zmienną pomocniczą właśnie przez te aproksymacje po odcięciu potęg dwójki. Uzyskamy wartość, o którą należy zmodyfikować zmienną pomocniczą. Należy jeszcze sprawdzić, gdyż trafiamy bardzo blisko wartości z dzielenia, ale czasem za daleko.
Zobaczmy na przykładach.
n/23 = 8934053 / 23
23 = 1 0111b, jedynka na pozycji 0x10, fragment trzech jedynek od pozycji ósemek do jedności, trzy obliczenia.
Dzielimy 8934053 = 558378 * 16 + 5
Zmienną roboczą jest 558378.
Fragment, początek, aproksymacja dzielnika to 3*8, obliczenie
558378 / 3 = 186126, które odejmujemy od zmiennej roboczej
558378 - 186126 = 372252
Sprawdzamy mnożąc 372252*3*8, blisko n, zostawiamy
koniec fragmentu ..111, tu już dzielimy przez cały dzielnik 23:
372252 / 23 = 16184
reszty z dzielania możemy ignorować, dodajemy
372252+16184 = 388436
Chybiamy z resztą, właściwy, poprawny iloraz jest tuż obok:
8934053 = 388437 * 23 + 2
8934053 / 27
27 = 1 1011b, dwa fragmenty
8934053 = 279189 * 32 + 5
zmienna robocza 279189 / 3 = 93063, bo aproksymacja to 3*8
279189 + 93063 = 372252
następny fragment zaczyna się dla aproksymacji 7*4:
372252 / 7 = 53178
oraz 372252 - 53178 = 319074
319074 / 27 = 11817
oraz 319074 + 11817 = 330891
Sprawdzamy i korygujemy: 8934053 = 330890*27+23
8934053 / 341
341 = 1 0101 0101b, najdłuższy obliczeniowo przypadek, bo nie ma dłuższych fragmentów. Zaczynamy od aproksymacji dzielnika 1*256
8934053 = 34898*256
i działania:
34898 - (34898 / 5) = 34898 - 6979 = 27919 poprawka na 27918*5*64+293
27918 - (27918 / 21) = 27918 - 1329 = 26589
26589 - (26589 / 85) = 26589 - 312 = 26277 poprawka
26276 - (26276 / 341) = 26276 - 77) = 26199
i finalnie 8934053 = 26199*341+194
Zamiast dzielić bądź odejmować, dzielimy przez coraz to większe kawałki dzielnika. Dzielenia początkowe można wykonać przesunięciami binarnymi. Staramy się, by uzyskać wartości iloczynów ze zmienną roboczą na początku fragmentu bliskie n, na końcu nieco mniejsze niż n.
Brak komentarzy:
Prześlij komentarz