Swego czasu opublikowałem dzielenie przez zmianę podstaw. Przypomnę przebieg na przykładzie
N = 8934053 : 8, 10-8=2, iloraz d[] z resztą r, val oznacza wyliczoną wartość
d_5 = n_6 = 8;
d_{n-1} = 2*val a_{n+1} + a_n, n=5..0,
d_{-1} = 2*d_0+a_0 = 8*k+r
d_0 = d_0+k
czyli
8 9 3 4 0 5 3
8 25 53 110 220 445 893 = 8*111+5
Wynik uzyskujemy przez dziesiętne dodawanie ww wartości i przesunięcie o jedną pozycję, czyli
cyfra jedności (445+111)%10 = 556%10 = 6
cyfra dziesiątek (220+55)%10 = 275%10 = 5 itd.
cyfra 'najbardziej znacząca' (8+3)%10 = 11%10, pojawiła się dodatkowa cyfra.
Duże wartości, wydaje się, że dzielenie pisemne jest prostsze, gdyż 8:8=1, podobnie 9.
Liczbę N można rozbić na dwie: 8832048 + 102005, oraz porachować osobno: 1104006 + 102005:8. Użyjemy tego pomysłu do mixu, dla kolejnych cyfr.
Mix dzieleń polega na połączeniu obu metod przy przebiegu. Dzielimy w cyfrze przez 8, dopiero resztę mnożoną przez 2 dodajemy do cyfry mniej znaczącej. Cyfry są przesunięte o jedną pozycję. Poprawkę stanowią współczynniki przy 8.
A oto dokładny przebieg:
d_6 = 8 = 1*8+0 => 0
d_5 = (2*0+9) = 1*8+1 => 0
d_4 = (2*1+3) = 5 = 0*8+5 => 1
d_3 = (2*5+4) = 14 = 1*8+6 => 5
d_2 = (2*6+0) = 12 = 1*8+4 => 6
d_1 = (2*4+5) = 13 = 1*8+5 => 4
d_0 = (2*5+3) = 13 = 1*8+5 => 5
odczytujemy wynik
0 0 1 5 6 4 5 , 5 cyfry i reszta
1 1 0 1 1 1 1 poprawki
sumujemy poprawki
1 1 1 6 7 5 6, reszta 5
Pamiętając o poszczególnych cyfrach i poprawkach, uzyskujemy bardzo małe wartości jak przy dzieleniu pisemnym, zachowując prostotę obliczeń dzielenia przez zmianę systemów.
Dla większych dzielników możemy zastosować dzielenie chłopów rosyjskich, dzięki czemu wartości obrabiane nie będą nigdy większe niż kwadrat dzielnika.
Brak komentarzy:
Prześlij komentarz