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.
algorytmy, pomysły na rozkład liczb i arytmetykę, także systemów niedziesiątkowych; elementy programowania pod DOSem
24 września 2015
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.
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.
Etykiety:
Janusz z Będzina,
lista,
programowanie,
Wyrazenia arytmetyczne
Subskrybuj:
Posty (Atom)