24 września 2015

Wyrażenia arytmetyczne - dzielenie

Przemyślałem 4 sposoby dzielenia w wyrażeniach arytmetycznych: przed, 2 podczas oraz jedno po obliczeniu wyrażenia. Wszystkie jednak mają problemy.

Dzielenie po obliczeniu wyrażenia:
plusy: podejście najbardziej standardowe, można zastosować klasyczne algorytmy
minusy: duże wartości

Dzielenie w czasie, wymuszane:
polega na odejmowaniu w każdej iteracji dzielnika, oraz zapisaniu w dodatkowej binarnej wartości 1 na kolejnych pozycjach. Ten iloraz jest równy zmniejszonej o 1 potędze 2, zatem po zatrzymaniu wartością ujemną dla cyfr najbardziej znaczących, należy wystartować jeszcze raz
plusy: małe wartości
minusy: trzeba szacować wartość połowioną, by była cały czas dodatnia; algorytm trzeba ponawiać, iloraz jest sumą szeregu liczb binarnych postaci 2^k-1.

Dzielenie w czasie, zwykłe:
należy najpierw wyznaczyć cyfrę, jeśli jest nią 0, cyfra ilorazu jest 0, jeśli 1, cyfra ilorazu jest 1 oraz odejmujemy dzielnik od wyrażenia. Często zostaje jakaś duża liczba reszty, będąca wielokrotnością potęgi 2. Należy ją później podzielić przez dzielną w inny sposób - ten się zapętla.
plusy: małe wartości
minusy: zapętlanie, wymóg znalezienia cyfry ignorując dzielenie

Dzielenie przed:
Wyłączamy części zawierające dzielenie oraz te, w których wartości się skróciły na dwa klastry, obliczenia w klastrach przebiegają oddzielnie. Dzielenie traktowane jest jako operacja, którą należy ignorować, podobnie jak zmienną wielomianów.
plusy: mniejsze wartości
minusy: często wymagane ponowne wywołanie, gdy reszta przekroczy wartość dzielnika

Czyli żaden ze sposobów nie jest dobry. Najefektywniej jest przekształcać wyrażenie do systemu o podstawie dzielnika. Ale wtedy są kłopoty z wyznaczaniem reszt.
Ostatni sposób sugeruje działania analogiczne jak ułamki egipskie.

17 września 2015

Wyrażenia arytmetyczne w programowaniu

Standardowo do obliczeń wyrażeń arytmetycznych stosuje się drzewo. W korzeniu jest ostatnia operacja, wartości są w liściach.

Aktualny mój pomysł polega na równoczesnym obliczaniu całego wyrażenia arytmetycznego. Ze wstępnych obliczeń wynika, że jest to możliwe. Uzyskuje się wartość binarną wyniku.
Wartości i operatory trzymamy na liście, do operatora przypisana jest krotność jego argumentów, których może być wiele! Oznacza to, że dodawanie oraz mnożenie są funkcjami n-arnymi, mogą mieć 3 lub więcej argumentów. Odejmowanie i dzielenie są funkcjami jednoargumentowymi. 

Aby znaleźć wartość wyrażenia arytmetycznego, korzystamy z rozdzielności mnożenia względem dodawania, traktując dzielenie jako mnożenie wartości odwrotnej. Uzyskujemy kolejno cyfry od najmniej znaczącej.

Podstawowe formuły są następujące:
Dodawanie: 
2a+(2b+b) -> a+b + [y/2] , cyfra x=y%2
gdzie y jest całością z połowy sumy składników nieparzystych. Np. 4+7+1+1 -> 2+3+1, cyfrą jest x=1, bo mamy trzy składniki nieparzyste, połowę y [3/2]=1 dodajemy do wartości.

Odejmowanie traktowane jako dodawanie liczby przeciwnej:
2a-2b-(2c+c) -> a-b-c+[y/2], cyfra x=y%2
gdzie y powstaje jako połowa różnicy sumy wartości nieparzystych dodatnich i nieparzystych ujemnych. Jeśli wartość y jest ujemna, zmniejsza się ją dodatkowo o 1, by reszta - cyfra była dodatnia. Np. 6 - 3 - 2 -> 3-1-1-1, y=-1 bo mamy jeden składnik ujemny, traktujemy jako -2. Połowa z tego jest odejmowana w wyniku, cyfra x=1. Można zerować przeciwne wartości.

Mnożenie sprowadza się do połowienia tylko jednego (najmniejszego) czynnika; wartości parzyste:
2a*b -> a*b
nieparzyste
(2a+a)*b -> a*b+[a*b/2]  
Np. 5*7*12 -> 2*5*7 + 1/2*(7*12) -> 2*5*7 + 3*12 + 6.

Dzielenie jest najtrudniejsze, nie można go przeprowadzać standardowo.Jeszcze nad nim pracuję. Należy zastosować dzielenie od końca, które zawodzi w przypadku gdy dzielna nie jest podzielna przez dzielnik.

Gdy uzyskamy pojedyńczą wartość, można ją bezpośrednio przekonwertować na system binarny. 

Przykład:
15+4*7-13 =
7+2*7-6+0 =     y=0, cyfra 0
3+7-3+0 =         y=1, cyfra 1
7                        y=3, cyfry 111b
Wynik czytamy od końca 11110b = 30.