Ostatni algorytm konwersji wskazał możliwość uzyskania pierwiastka kwadratowego stosunkowo małym kosztem. Jako pierwszy znalazłem sposób dla licz zapisanych w postaci binarnej. Istnieje też sposób w systemie dziesiętnym, który jest nieco bardziej rozbudowany.
Liczbę będącą kwadratem p^2 zapiszemy jako czwórkę [1,0,0,p], w której pierwsze pozycje to cyfry rozwinięcia w systemie o podstawie p, czyli
N = 1*p^2 + 0*p+0 .
Oto wszystkie używane manipulacje:
1) [1, a+2, b+a+1, p] = [1, a, b, p+1]
2) [1, a, 2*p+c, p ] = [1, a+2, c, p]
3) [100, 10*a, b, p] = [1, a, b, 10*p] .
Pierwsza to konwersja na system o 1 większy.
Bierzemy liczbę N i odcinamy grupy po 2 cyfry. Następnie wyznaczamy przybliżoną wartość pierwiastka. Mając ją, mnożymy wszystkie wartości przez 100 i stosujemy konwersję 3). Uzyskujemy w ten sposób przybliżenie pierwiastka uciętej liczby z niedomiarem, który poprawiamy za pomocą 1) lub 2). Powtórzą się one nie więcej niż 9 razy.
Staramy się doprowadzać do tego, by wszystkie wyrazy były nieujemne, oraz na pozycji drugiej była wartość 0 lub 1 ([1, 0|1, b, p]. Bardzo rzadko pojawia się przypadek, kiedy uzyskamy [1, 2, 0, p] - o 1 mniej niż kwadrat. Zamieniamy go na niepoprawne w systemie [1, 1, p, p]. Uzyskamy w ten sposób dokładną kolejną cyfrę pierwiastka.
Zatem złożoność to logarytm z liczby znajdowanych cyfr plus stały narzut.
Jeśli kto chce znaleźć właściwą wartość pierwiastka i nadmiar, wartość pierwiastka jest przybliżana przez p, zaś nadmiar z [1, a, b, p] jest liczony jako a*p+b większy od p^2.
Przykład: 8 93 40 53
kwadrat z 8 to [1, 2, 0, 2]=[1,1,2,2] (2^2+2*2) - jest to ten wyjątkowy przypadek z drugą wartością większą niż 1.
Mnożymy przez 100 i dodajemy kolejne 2 cyfry uzyskując 893
[100, 100*1/10, 100*2+93, 2] = [1, 10, 293, 20] z 3)
konwersje 1) i poprawki 2) przybliżają p do pierwiastka:
[1, 10, 293, 20] = [1, 8, 284, 21] = [1, 10, 242, 21] = ...
= [1,1, 23, 29] jest kolejnym przybliżeniem do pierwiastka z przyciętej wartości.
Dokładamy kolejne cyfry 40 uzyskując po konwersji 3):
[1, 10, 2340, 290] = ... = [1, 1, 238, 298]
Ostatnie cyfry 53 i mamy
[1, 10, 23853, 2980] = ... = [1, 1, 2921, 2988]
pierwiastkiem całkowitym jest 2988 z resztą 1*2988+2921.
Możemy kontynuować dokładając '00', uzyskamy w ten sposób kolejne cyfry części ułamkowej z niedomiarem.
10 grudnia 2015
12 listopada 2015
Konwersje a rozkład liczb o dużych podstawach
W ostatnim poście wspominałem o sposobie 'trial division' dla liczb postaci
n = a*p+b (1)
gdzie a,b<p oraz p^2>n.
Przy zmieniającym się a szukamy dzielników kiedy a=b (cecha podzielności, bo a*p+a = a*(p+1) = n ).
Zastanawiałem się nad przechodzeniem między różnymi p. Mamy tu aż n-sqrt(n) możliwości, przy czym dla dzielników wystarczy znajomość sqrt(n) wartości p. Albo wystarczy umieć znajdować p dla zmienianego a. Jest to obarczone błędem, jednak łatwym do skorygowania.
Niech r oznacza różnicę między p-q, gdzie
n = (a+1)*q+c = a*p+b .
Różnica ta jest bardzo duża dla małych a, zaś dla większych maleje, w szczególności dąży do 1 gdy a dąży do sqrt(n).
Kiedy konwertujemy a*p+b o k-tą wielokrotność r, wykonujemy przekształcenia:
a*p+b = a*(p-rk)+(b+ark) (2)
Dobierając r bliskie a*r=p, możemy w ten sposób zwiększać a o prawie dowolną wartość. Oczywiście, dla większych a błąd jest mniejszy. Pozwala to pomijać podczas faktoryzacji kolejne przypadki, kiedy a nie jest dzielnikiem.
Występuje błąd, który należy skorygować. Jeśli uzyskamy wartość c>a+k, dokonujemy dzielenia c/a, co jest znacznie prostsze i szybsze niż dzielenie p/a. Uzyskaną część całkowitą odejmujemy od c uzyskując właściwą resztę.
W przypadku niedomiaru, dopasowujemy współczynnik konwersji
1+(q-c)/(a+k),
by uzyskać c z przedziału [0,a+k]. Brzegowe wartości oznaczają dzielnik. Przyrost r(a) należy modyfikować, np. odejmując iloraz nadmiaru przez przyrost k .
Zobaczmy na przykładzie.
Liczba 8934053 ma przedstawienie a*p+b = 91 * 98176 + 37,
r bliskie 98176 / 91 jest równe np. 1078.
Przejdziemy z a na 97, przyrost 6. Zatem najpierw wyznaczamy przybliżenie podstawy systemu q = p-6r = 98176 - 6*1078 = 91708.
Teraz dokonujemy właściwej konwersji, co sprowadza się do obliczenia
c = 37 + 91*1078*6 - 6*91708 = 38377
W tym miejscu mamy już a zwiększone o 6 (odejmowanie 6*q oznacza a+6),
dokonujemy korekty, w czasie której uzyskujemy nadmiar dzieleniem
38377 / 97 = 395.
Nasza konwersja przeskoczyła o 395 za daleko. Modyfikujemy r o 395/6 oraz wracamy by c było nie większe niż a+k:
38377 - 97*395 = 62
wtedy q = 91708 + 395 = 92103.
Mamy przedstawienie liczby n = (a+6)*q+c = 97 * 92103 + 62
W ten sposób pamiętając r można przebiegać po różnych a testując kandydatów na dzielniki - liczby pierwsze a. Po każdym przekształceniu należy jednak zmodyfikować r, tu r przechodzi na 1078 - 395/6 = 1012, co tylko przybliża p/a = 949, lecz jest wystarczające do dalszych obliczeń.
Jeśli uzyskamy wartość c>q, możemy ją zignorować. Korekta to naprawi pozostawiając właściwą wartość.
n = a*p+b (1)
gdzie a,b<p oraz p^2>n.
Przy zmieniającym się a szukamy dzielników kiedy a=b (cecha podzielności, bo a*p+a = a*(p+1) = n ).
Zastanawiałem się nad przechodzeniem między różnymi p. Mamy tu aż n-sqrt(n) możliwości, przy czym dla dzielników wystarczy znajomość sqrt(n) wartości p. Albo wystarczy umieć znajdować p dla zmienianego a. Jest to obarczone błędem, jednak łatwym do skorygowania.
Niech r oznacza różnicę między p-q, gdzie
n = (a+1)*q+c = a*p+b .
Różnica ta jest bardzo duża dla małych a, zaś dla większych maleje, w szczególności dąży do 1 gdy a dąży do sqrt(n).
Kiedy konwertujemy a*p+b o k-tą wielokrotność r, wykonujemy przekształcenia:
a*p+b = a*(p-rk)+(b+ark) (2)
Dobierając r bliskie a*r=p, możemy w ten sposób zwiększać a o prawie dowolną wartość. Oczywiście, dla większych a błąd jest mniejszy. Pozwala to pomijać podczas faktoryzacji kolejne przypadki, kiedy a nie jest dzielnikiem.
Występuje błąd, który należy skorygować. Jeśli uzyskamy wartość c>a+k, dokonujemy dzielenia c/a, co jest znacznie prostsze i szybsze niż dzielenie p/a. Uzyskaną część całkowitą odejmujemy od c uzyskując właściwą resztę.
W przypadku niedomiaru, dopasowujemy współczynnik konwersji
1+(q-c)/(a+k),
by uzyskać c z przedziału [0,a+k]. Brzegowe wartości oznaczają dzielnik. Przyrost r(a) należy modyfikować, np. odejmując iloraz nadmiaru przez przyrost k .
Zobaczmy na przykładzie.
Liczba 8934053 ma przedstawienie a*p+b = 91 * 98176 + 37,
r bliskie 98176 / 91 jest równe np. 1078.
Przejdziemy z a na 97, przyrost 6. Zatem najpierw wyznaczamy przybliżenie podstawy systemu q = p-6r = 98176 - 6*1078 = 91708.
Teraz dokonujemy właściwej konwersji, co sprowadza się do obliczenia
c = 37 + 91*1078*6 - 6*91708 = 38377
W tym miejscu mamy już a zwiększone o 6 (odejmowanie 6*q oznacza a+6),
dokonujemy korekty, w czasie której uzyskujemy nadmiar dzieleniem
38377 / 97 = 395.
Nasza konwersja przeskoczyła o 395 za daleko. Modyfikujemy r o 395/6 oraz wracamy by c było nie większe niż a+k:
38377 - 97*395 = 62
wtedy q = 91708 + 395 = 92103.
Mamy przedstawienie liczby n = (a+6)*q+c = 97 * 92103 + 62
W ten sposób pamiętając r można przebiegać po różnych a testując kandydatów na dzielniki - liczby pierwsze a. Po każdym przekształceniu należy jednak zmodyfikować r, tu r przechodzi na 1078 - 395/6 = 1012, co tylko przybliża p/a = 949, lecz jest wystarczające do dalszych obliczeń.
Jeśli uzyskamy wartość c>q, możemy ją zignorować. Korekta to naprawi pozostawiając właściwą wartość.
26 października 2015
Nowa metoda faktoryzacji 'trial division'
Cechą podzielności n przez liczbę a jest możliwość zapisania n = a*p+a.
Zastanawiało mnie, czy można łatwo przechodzić z liczby postaci a*p+b do (a+1)*q+c, gdzie q jest bliskie p zaś b<2a, c<2(a+1).
Można, co doprowadziło do uzyskania kolejnego siłowego algorytmu faktoryzacji typu 'trial division'.
W postaci n=a*p+b największą trudność wydaje się zachowywać b w przedziale (0,2a), lecz gorsze jest znajdowanie kolejnej podstawy systemu q. Znajdujemy ją za pomocą dzielenia n/(a+1), co nie zawsze trafia we właściwą wartość.
Oto jedna z wersji tego algorytmu rozkładu liczby n:
a = b = 1; p=n-1;
while( a<p ) {
a++;
b = b-p%a;
p = p-p/a;
if( b<a ) { p--; b = b+a; }
if( a==b ) return dzielniki a, p+1
}
return liczba pierwsza;
Sposób ten niezwykle szybko pozwala znajdować kolejne reszty b, ale tylko dla sąsiedniej wartości a.
Oto początek rozkładu liczby 8934053:
a b p
1 1 8934052
2 3 4467025 (4467025:3=1489008, 4467025-1489008-1 = 2978016)
3 5 2978016 (2978016:4=744504, 2978016-744504 = 2233512)
4 5 2233512 (2233512:5=446702, 2233512-446702-1 = 1786809)
5 8 1786809
6 11 1489007
7 9 1276292
...
Wartości p początkowo szybko maleją dążąc do pierwiastka kwadratowego z n, potem różnica między p na wejściu oraz wyjściu z pętli zmniejsza się do jedynki. Nie jest znana dokładnie, lecz błąd jest rzędu a, czyli stosunkowo mały. Dzielenia są prostsze niż w standardowym algorytmie dzielenia przez kolejne liczby.
Jeśli chcemy mieć mniejsze reszty b, należy zapamiętać wartość c=b z początku pętli oraz zmienić warunek pod if na tę kopię if(c<a)... Wtedy zamiast
5 8 1786809
mamy
5 3 1786810
Przebieg ten sam. Algorytm rekursywny (nie równoważny powyższemu, robiący to samo)
factd(a,p,b) {
if( a==b ) return dzielniki a, p+1;
if( a>p ) return liczba pierwsza;
q=p-p/(a+1);
c=p%b;
if( b<a+1 ) {q--; c=c+a+1; }
return factd(a+1, q, c);
}
Liczby złożone nieparzyste charakteryzują się nieparzystymi a i b=a oraz parzystymi p. Pojawia się chęć przeskoków tylko po nieparzystych a, jak w algorytmie standardowym. Jest to możliwe, lecz wtedy należy użyć konwersji. Tracimy łatwość wyznaczania reszt b. Pojawia się dodatkowe mnożenie, oraz konieczność korekty, gdyż b ma często zbyt dużą wartość. Wyliczane kolejne ilorazy nie są równe. Tworzą zaszumiony ciąg statystycznie nierosnący (fragmenty ciągu kolejnych ilorazów mogą być postaci: ..., 273, 270, 268, 265,..., 2, 1, 1, 1, 2, 1, 1, ).
Zastanawiało mnie, czy można łatwo przechodzić z liczby postaci a*p+b do (a+1)*q+c, gdzie q jest bliskie p zaś b<2a, c<2(a+1).
Można, co doprowadziło do uzyskania kolejnego siłowego algorytmu faktoryzacji typu 'trial division'.
W postaci n=a*p+b największą trudność wydaje się zachowywać b w przedziale (0,2a), lecz gorsze jest znajdowanie kolejnej podstawy systemu q. Znajdujemy ją za pomocą dzielenia n/(a+1), co nie zawsze trafia we właściwą wartość.
Oto jedna z wersji tego algorytmu rozkładu liczby n:
a = b = 1; p=n-1;
while( a<p ) {
a++;
b = b-p%a;
p = p-p/a;
if( b<a ) { p--; b = b+a; }
if( a==b ) return dzielniki a, p+1
}
return liczba pierwsza;
Sposób ten niezwykle szybko pozwala znajdować kolejne reszty b, ale tylko dla sąsiedniej wartości a.
Oto początek rozkładu liczby 8934053:
a b p
1 1 8934052
2 3 4467025 (4467025:3=1489008, 4467025-1489008-1 = 2978016)
3 5 2978016 (2978016:4=744504, 2978016-744504 = 2233512)
4 5 2233512 (2233512:5=446702, 2233512-446702-1 = 1786809)
5 8 1786809
6 11 1489007
7 9 1276292
...
Wartości p początkowo szybko maleją dążąc do pierwiastka kwadratowego z n, potem różnica między p na wejściu oraz wyjściu z pętli zmniejsza się do jedynki. Nie jest znana dokładnie, lecz błąd jest rzędu a, czyli stosunkowo mały. Dzielenia są prostsze niż w standardowym algorytmie dzielenia przez kolejne liczby.
Jeśli chcemy mieć mniejsze reszty b, należy zapamiętać wartość c=b z początku pętli oraz zmienić warunek pod if na tę kopię if(c<a)... Wtedy zamiast
5 8 1786809
mamy
5 3 1786810
Przebieg ten sam. Algorytm rekursywny (nie równoważny powyższemu, robiący to samo)
factd(a,p,b) {
if( a==b ) return dzielniki a, p+1;
if( a>p ) return liczba pierwsza;
q=p-p/(a+1);
c=p%b;
if( b<a+1 ) {q--; c=c+a+1; }
return factd(a+1, q, c);
}
Liczby złożone nieparzyste charakteryzują się nieparzystymi a i b=a oraz parzystymi p. Pojawia się chęć przeskoków tylko po nieparzystych a, jak w algorytmie standardowym. Jest to możliwe, lecz wtedy należy użyć konwersji. Tracimy łatwość wyznaczania reszt b. Pojawia się dodatkowe mnożenie, oraz konieczność korekty, gdyż b ma często zbyt dużą wartość. Wyliczane kolejne ilorazy nie są równe. Tworzą zaszumiony ciąg statystycznie nierosnący (fragmenty ciągu kolejnych ilorazów mogą być postaci: ..., 273, 270, 268, 265,..., 2, 1, 1, 1, 2, 1, 1, ).
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.
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.
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.
23 sierpnia 2015
Sito liczb złożonych
Czasem pojawia się pomysł, jak zmniejszyć krotność przypadków faktoryzacji zachłannej. Pomysł ten często jest chybiony. Podobnie jak poniższy.
Nieparzyste dzielniki liczby N są jednej z postaci: 4p+1 oraz 4p+3.
Liczba N także, lecz w jej przypadku łatwo ją znajdziemy.
Wtedy możemy dopasować a, b w taki sposób, by N = a+4b, stąd b=(N-a)/4.
Wykorzystując cechy podzielności, N jest podzielna przez a wtedy i tylko wtedy, gdy N = a*(4b)+a w przypadku dzielnika postaci 4p+1 (b=p); lub N=a*(4b)-a w przypadku dzielnika 4p+3 (b=p+1).
Sugeruje to, że możemy badać pary (a,b), w których mamy nie połowę, ale czwartą część wartości mniejszych niż pierwiastek z N. Niestety, znajdujemy tylko dzielniki określonej postaci. Dzielnik występuje gdy a dzieli b.
Ostatecznie uzyskujemy następujący sposób rozkładu:
załóżmy, że N = 4b+1
tworzymy ciągi a=1+4k, b=(N-1)/4-k dla k dodatnich. Inicjacja a=5, b=(N-5)/4.
Dla każdej wartości b przypisujemy zbiór jego dzielników {d}, początkowo pusty.
Przekształcamy: a=a+4, b=b-1. Korzystając ze zbioru dzielników {d} znajdujemy częściowy rozkład b na czynniki. W rozkładzie tym z b są wyłączone dzielniki nie większe niż a, mnożone przez wartość c. Wartość c jest 1, liczbą pierwszą lub iloczynem liczb pierwszych większych niż a. Gdy c =1, nie mamy dzielników, do zbiorów przypisanych wartościom b-d dodajemy dzielniki d.
Gdy c jest liczbą większą niż a, obliczamy resztę s z dzielenia c przez a. Pozwala nam ona znaleźć resztę r z dzielenia b przez a. Teraz do zbioru przypisanego wartości b-r dokładamy jego dzielnik a. Nie musimy się przejmować pominiętymi liczbami pierwszymi. Mogą się jeszcze pojawić, albo są w danej gałęzi nieistotne.
Kontynuujemy z kolejnymi k, uzyskując zbiór liczb, które na pewno nie są dzielnikami N.
Występujące dzielenia operują na mniejszych wartościach jak zwykłe dzielenie N przez a, co najmniej 4 razy w przypadku, gdy zarówno a, jak i b są pierwsze.
Kończymy, gdy wartość a przekroczy pierwiastek z N.
Niestety, nie wyłapane są wszystkie dzielniki, do reszty należy zmienić znak, oraz zmodyfikować a=3, teraz b zwiększamy zamiast zmniejszać (b+d), oraz w przypadku c większych od a do zbioru dzielników wartości (b-r+a) dołączamy a.
Dla N = 4b+3 wartości inicjujące a są odwrócone. Mamy 3 zamiast 5 i na odwrót. Chodzi o to, żeby po odjęciu a wartość była podzielna przez 4.
Skomplikowane, przykład może nieco rozjaśni.
Liczba 8934053
a=5; b=(8934053-5)/4 = 2233512. Rozkład częściowy b = 2^3*279189. Liczba c=279189, jej reszta z dzielenia przez 5 jest 4. Różna od 0, zatem 5 nie jest dzielnikiem. Liczbą pierwszą 3 się nie przejmujemy.
Znajdujemy resztę z dzielenia b przez a: r = 4*8 = 2 (5).
Uzupełniamy tabele dzielników dla wartości: [b=2233512-2, {2}] = [2233510, {2}]. c>a, zatem [b=2233512-2, {a}] = [2233510, {2,5}]
W następnym kroku mamy a=5+4=9, b = c = 2233511, reszta r=s=8, czyli [b=2233511-8, {9}] nie jest dzielnikiem N. Najgorszy przypadek z największymi wartościami.
Kolejny krok a=9+4=13, b=2233510 mamy zbiór dzielników {2,5}, czyli b = 2*5*223351. Nie mamy dzielników, ale korzystając z reszty r=6 modyfikujemy zbiory dla wartości [2233508, {2}], [2233505, {5}] i [2233504, {13}]
W tej części nie znajdziemy dzielników. Zajrzyjmy do drugiej:
a=3, b=2233514
Tu pojawia się czynnik 3.
Przeskoczmy nieco przypadków:
a=411, b=2233616 = 2^4*7^3*11*37 jest pełnym rozkładem, czyli c=1, wprowadzając wartości do zbiorów [2233618, {2}], [2233623, {7}], [2233627, {11}, [2233653, {37}] nie modyfikujemy zbioru dla wartości b=2233616-242+411 = 2233785 wartością {a=411}. Nie musimy mając już wszystkie dzielniki.
Dzielnik pojawia się dla a=1087, b= (8934053+1087)/4 = 2233785 = 5*411*1087. jest on równy 1087.
Nieparzyste dzielniki liczby N są jednej z postaci: 4p+1 oraz 4p+3.
Liczba N także, lecz w jej przypadku łatwo ją znajdziemy.
Wtedy możemy dopasować a, b w taki sposób, by N = a+4b, stąd b=(N-a)/4.
Wykorzystując cechy podzielności, N jest podzielna przez a wtedy i tylko wtedy, gdy N = a*(4b)+a w przypadku dzielnika postaci 4p+1 (b=p); lub N=a*(4b)-a w przypadku dzielnika 4p+3 (b=p+1).
Sugeruje to, że możemy badać pary (a,b), w których mamy nie połowę, ale czwartą część wartości mniejszych niż pierwiastek z N. Niestety, znajdujemy tylko dzielniki określonej postaci. Dzielnik występuje gdy a dzieli b.
Ostatecznie uzyskujemy następujący sposób rozkładu:
załóżmy, że N = 4b+1
tworzymy ciągi a=1+4k, b=(N-1)/4-k dla k dodatnich. Inicjacja a=5, b=(N-5)/4.
Dla każdej wartości b przypisujemy zbiór jego dzielników {d}, początkowo pusty.
Przekształcamy: a=a+4, b=b-1. Korzystając ze zbioru dzielników {d} znajdujemy częściowy rozkład b na czynniki. W rozkładzie tym z b są wyłączone dzielniki nie większe niż a, mnożone przez wartość c. Wartość c jest 1, liczbą pierwszą lub iloczynem liczb pierwszych większych niż a. Gdy c =1, nie mamy dzielników, do zbiorów przypisanych wartościom b-d dodajemy dzielniki d.
Gdy c jest liczbą większą niż a, obliczamy resztę s z dzielenia c przez a. Pozwala nam ona znaleźć resztę r z dzielenia b przez a. Teraz do zbioru przypisanego wartości b-r dokładamy jego dzielnik a. Nie musimy się przejmować pominiętymi liczbami pierwszymi. Mogą się jeszcze pojawić, albo są w danej gałęzi nieistotne.
Kontynuujemy z kolejnymi k, uzyskując zbiór liczb, które na pewno nie są dzielnikami N.
Występujące dzielenia operują na mniejszych wartościach jak zwykłe dzielenie N przez a, co najmniej 4 razy w przypadku, gdy zarówno a, jak i b są pierwsze.
Kończymy, gdy wartość a przekroczy pierwiastek z N.
Niestety, nie wyłapane są wszystkie dzielniki, do reszty należy zmienić znak, oraz zmodyfikować a=3, teraz b zwiększamy zamiast zmniejszać (b+d), oraz w przypadku c większych od a do zbioru dzielników wartości (b-r+a) dołączamy a.
Dla N = 4b+3 wartości inicjujące a są odwrócone. Mamy 3 zamiast 5 i na odwrót. Chodzi o to, żeby po odjęciu a wartość była podzielna przez 4.
Skomplikowane, przykład może nieco rozjaśni.
Liczba 8934053
a=5; b=(8934053-5)/4 = 2233512. Rozkład częściowy b = 2^3*279189. Liczba c=279189, jej reszta z dzielenia przez 5 jest 4. Różna od 0, zatem 5 nie jest dzielnikiem. Liczbą pierwszą 3 się nie przejmujemy.
Znajdujemy resztę z dzielenia b przez a: r = 4*8 = 2 (5).
Uzupełniamy tabele dzielników dla wartości: [b=2233512-2, {2}] = [2233510, {2}]. c>a, zatem [b=2233512-2, {a}] = [2233510, {2,5}]
W następnym kroku mamy a=5+4=9, b = c = 2233511, reszta r=s=8, czyli [b=2233511-8, {9}] nie jest dzielnikiem N. Najgorszy przypadek z największymi wartościami.
Kolejny krok a=9+4=13, b=2233510 mamy zbiór dzielników {2,5}, czyli b = 2*5*223351. Nie mamy dzielników, ale korzystając z reszty r=6 modyfikujemy zbiory dla wartości [2233508, {2}], [2233505, {5}] i [2233504, {13}]
W tej części nie znajdziemy dzielników. Zajrzyjmy do drugiej:
a=3, b=2233514
Tu pojawia się czynnik 3.
Przeskoczmy nieco przypadków:
a=411, b=2233616 = 2^4*7^3*11*37 jest pełnym rozkładem, czyli c=1, wprowadzając wartości do zbiorów [2233618, {2}], [2233623, {7}], [2233627, {11}, [2233653, {37}] nie modyfikujemy zbioru dla wartości b=2233616-242+411 = 2233785 wartością {a=411}. Nie musimy mając już wszystkie dzielniki.
Dzielnik pojawia się dla a=1087, b= (8934053+1087)/4 = 2233785 = 5*411*1087. jest on równy 1087.
07 lipca 2015
Dodawanie z pomocą logiki
Swego czasu w czerwcu 2015 roku opublikowałem posta o tytule: "Operatory arytmetyczne wyrażone operatorami logicznymi".
Niedawno spróbowałem dodawać następującą metodą rekursywną:
przechodząc po cyfrach argumentów, przy generowaniu kolejnej sumy biorę mniejszą z nich dla pierwszego argumentu a, zaś moduł różnicy cyfr jako argument drugiej b. Suma docelowa jest równa 2a+b.
Np. 4283 + 1728 = 1223 * 2 + 3565
bo np. min(4,1)=1, 4-1=3 na pozycji tysięcy itd. Na pozycji jedności jest min(3,8)=3, 8-3=5.
bo np. min(4,1)=1, 4-1=3 na pozycji tysięcy itd. Na pozycji jedności jest min(3,8)=3, 8-3=5.
Sposób ten czasem się zapętla, lecz jest proste rozwiązanie. Przekształcam b=2*c+e, gdzie e jest zerem lub jedynką w zależności od parzystości b, oraz do dalszych przekształceń stosuję a+c, wartość zmniejszona co najmniej dwukrotnie.
4283 + 2728 = (1223*2 + 3564)+1 = (1223+1782)*2+1
4283 + 2728 = (1223*2 + 3564)+1 = (1223+1782)*2+1
Tym razem zapętlenie nie występuje.
Metoda działa też w innych systemach liczbowych. Zaś w binarnym sprowadza się do opublikowanego w czerwcu algorytmu.
Jest coś więcej. Algorytm ten wyznacza w jednej iteracji bit najmniej znaczący oraz z dużą dokładnością bit najbardziej znaczący. Chodzi o ten na pozycji, do której występuje przeniesienie przy zmianie długości liczby. Nazwę maską wartość, w niej tylko skrajne bity mają znaczenie.
Kiedy następuje podsumowanie - dodawanie można zastąpić OR-owaniem.
Przykład: 15+9 = 1111b + 1001b
pierwsza iteracja: a=1001b, b=0110b, do dalszej części przechodzą
(1001b+11b)*2 + 0
które przekształcamy do (001b+11b)*2 + 10000b (b jest parzyste, bit najmniej znaczący jest równy 0)
druga iteracja: a = 1, b=10b,
po przekształceniu: (1+1), maska 0000
trzecia iteracja: a=1, b=0, tu wyznaczenie 2a = 10 jest tak duże, że zahacza o wyznaczony już bit maski w poprzedniej iteracji.
Podsumowanie, czyli orowanie wartości 10000b | 0000<<1 | 10<<2 = 11000b = 24
jest to wartość 15+9 = 24.
Inny przykład: 15+7, już szybciej. 1111b + 111b
a = 111b, b = 1000b, maska 00000b
suma 111b + 100b
a = 100b, b = 11b, maska 1001b, bit najbardziej znaczący pobrany z 2a = 1000b
suma 0+1 = 1, kończymy wartością 01, co dajemy jako maskę.
Podsumowanie: 00000 | 10010 | 0100 = 10110b
Są 3 iteracje w porównaniu z przechodzeniem 4 razy po bitach. Wszystkie przechodzenia można traktować równocześnie jedną operacją logiczną.
19 marca 2015
Inne podejście do programowania
W Świecie Nauki 3/2015 jest artykuł "Wystarczy dodać pamięć" o komputerach pamięciowych, w których procesorem obliczeniowym jest sama pamięć. Potrzebne jest nowe oprogramowanie sterujące.
Jest ono bliskie mojemu pomysłowi, dążącemu do obliczeń rekursywnych.
Paradygmat o zachowywaniu stałego programu jest bardzo silny. A widzę potrzebę jego zniesienia.
Program może być tablicą wskaźników na dane umieszczone w pamięci. Następują dwa przebiegi.
Pierwszy z nich porównuje dane ze sobą, sortuje i przygotowywuje trójki wskaźników do obliczeń. Wykorzystuje formuły programowania relacyjnego, takiego jak w Prologu.
Dopiero drugi przebieg przelicza dane wskazane w pierwszym przebiegu.
Funkcje dodawania i mnożenia są wielowartościowe. Potrzebny jest zatem znacznik zakończenia, tu średnik. Składniki sortowane są najpierw funkcjami, potem malejąco. Czynniki sortowane są najpierw funkcjami, potem malejąco.
Funkcje odejmowania i dzielenia są jednoargumentowe, tworząc formuły zapisane w ONP:
a - b = + - b a
a : b = * : b a
Formuł jest dużo, oto niektóre z nich:
+ a 0 = a
+ - a a = 0
+ * a b; * a c;; = * + b c; a;
Ostatnia jest formułą, gdyż kolejność nie ma znaczenia. Sortowanie i tak może ją zmienić.
Przy odejmowaniu, dzieleniu następuje próba wyłączenia wartości tworząc funkcję, tak
+ - 5 12;
jest przekształcane formułą w drugiej fazie na (12 = 5+7)
+ - 5 7 5;
kolejny krok w pierwszej fazie wyznacza do obliczeń + - 5 5, czyli w drugiej fazie uzyskujemy
+ 7 0;
pierwsza faza znów modyfikuje do wyniku
7
Jest ono bliskie mojemu pomysłowi, dążącemu do obliczeń rekursywnych.
Paradygmat o zachowywaniu stałego programu jest bardzo silny. A widzę potrzebę jego zniesienia.
Program może być tablicą wskaźników na dane umieszczone w pamięci. Następują dwa przebiegi.
Pierwszy z nich porównuje dane ze sobą, sortuje i przygotowywuje trójki wskaźników do obliczeń. Wykorzystuje formuły programowania relacyjnego, takiego jak w Prologu.
Dopiero drugi przebieg przelicza dane wskazane w pierwszym przebiegu.
Funkcje dodawania i mnożenia są wielowartościowe. Potrzebny jest zatem znacznik zakończenia, tu średnik. Składniki sortowane są najpierw funkcjami, potem malejąco. Czynniki sortowane są najpierw funkcjami, potem malejąco.
Funkcje odejmowania i dzielenia są jednoargumentowe, tworząc formuły zapisane w ONP:
a - b = + - b a
a : b = * : b a
Formuł jest dużo, oto niektóre z nich:
+ a 0 = a
+ - a a = 0
+ * a b; * a c;; = * + b c; a;
Ostatnia jest formułą, gdyż kolejność nie ma znaczenia. Sortowanie i tak może ją zmienić.
Przy odejmowaniu, dzieleniu następuje próba wyłączenia wartości tworząc funkcję, tak
+ - 5 12;
jest przekształcane formułą w drugiej fazie na (12 = 5+7)
+ - 5 7 5;
kolejny krok w pierwszej fazie wyznacza do obliczeń + - 5 5, czyli w drugiej fazie uzyskujemy
+ 7 0;
pierwsza faza znów modyfikuje do wyniku
7
26 lutego 2015
Cechy podzielności w systemach niedziesiątkowych
Znane są cechy podzielności przez 2, 3, 4, 5, 9, 10, 11 w systemie dziesiątkowym.
Okazuje się, że w systemie o podstawie n cechy podzielności są równie łatwe do wyprowadzenia.
W szczególności, traktując kolejne cyfry liczby w systemie o podstawie n jako współczynniki wielomianu, znajdujemy resztę z dzielenia przez n-x obliczając wartość tego wielomianu dla x modulo (n-x).
Wynika to z tych sposobów mnożenia i dzielenia, w których dowodach korzystamy z konwersji na inny system.
Sposoby te są przenośne na wszystkie systemy, w których rozpisaniu kolejne cyfry są przy potęgach liczby naturalnej większej od 1.
Przykładowo mając liczbę w systemie o podstawie 20, np 13 7 2 8 10, daje ona w wyniku dzielenia przez 19 resztę 2, bo cecha podzielności to wartość wielomianu w 1:
13+7+2+8+10 = 22_{19} (dziesiętnie 40) = 2 (mod 19)
Okazuje się, że w systemie o podstawie n cechy podzielności są równie łatwe do wyprowadzenia.
W szczególności, traktując kolejne cyfry liczby w systemie o podstawie n jako współczynniki wielomianu, znajdujemy resztę z dzielenia przez n-x obliczając wartość tego wielomianu dla x modulo (n-x).
Wynika to z tych sposobów mnożenia i dzielenia, w których dowodach korzystamy z konwersji na inny system.
Sposoby te są przenośne na wszystkie systemy, w których rozpisaniu kolejne cyfry są przy potęgach liczby naturalnej większej od 1.
Przykładowo mając liczbę w systemie o podstawie 20, np 13 7 2 8 10, daje ona w wyniku dzielenia przez 19 resztę 2, bo cecha podzielności to wartość wielomianu w 1:
13+7+2+8+10 = 22_{19} (dziesiętnie 40) = 2 (mod 19)
Subskrybuj:
Posty (Atom)