Ten pomysł nie jest najlepszy obliczeniowo, ale w pobliżu pierwiastka z liczby rzadko natrafia się na dzielniki. Znalazłem sposób zmniejszenia krotności przypadków, szacuję, że nawet do pierwiastka sześciennego z rozkładanej liczby. Ale koszt jest duży.
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];
Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k.
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.
Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1) tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p.
W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.
Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087 dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7
25 stycznia 2016
05 stycznia 2016
Podnoszenie do kwadratu lub mnożenie
Podobny sposób, który był użyty do znajdowania pierwiastka kwadratowego w ostatnim poście, może też być użyty do podnoszenia liczby do kwadratu.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
10 grudnia 2015
Pierwiastkowanie złożoności logarytmicznej
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.
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.
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)
03 grudnia 2014
Faktoryzacja dwoma kandydatami równocześnie, szczegóły
W poprzednim poście wspomniałem o pomyśle równoczesnego badania dwu dzielników s*t, s<t, w którym s i t tworzą ciągi arytmetyczne o przyroście |2|. Sposób nie unika mnożeń lub dzieleń, lecz obecne są przez stosunkowo małe wartości. Dodatkowo wartości te łatwo jest szacować.
Wygodnie jest nie pamiętać liczb n, lecz ich trójki [a,p,b]: n = a*p+b.
Jest to na dwu poziomach, jeden przy podstawie p, obliczanej przez dodanie zmniejszającej się o 8 wartości w. Drugi poziom dotyczy iloczynu a*w, rozpisanego trójką a*w = [c,t,d].
Wartość b zapisujemy analogiczną trójką b = [e,t,f]. Przy przekształcaniu odejmujemy b-a*w = [e-c,t,f-d] starając się, by wartość f-d była dodatnia. W razie potrzeby dodajemy s*t zmniejszając a. Wartość e-c dla sprawdzanego zakresu jest zawsze dodatnia. Podobnie można zrobić z wartością s.
Pamiętamy stare wartości (to te z primami).
Zaczynamy od s=3, t będącą nieparzystą wartością nieco mniejszą niż pierwiastek kwadratowy z rozkładanej liczby n, przyjmujemy w = 2*t-10;
Przy sprawdzaniu kolejnych dwu dzielników postępujemy następująco:
w = w'-8;
p = p'+w = (s'+2)*(t'-2) = s*t;
a*w = [ct, t, dt] = [cs, s, ds]
b' - a*w + s*t*x = [e, t', f] - [ct, t, dt] + s*t*x = [e-ct+s*x, t, 2*e+f-dt]
Rozwiązujemy nierówność liniową e-ct+s*x>0 zmiennej x szukając najmniejszego możliwego x. Od pewnego momentu jest x=1 lub x=0.
Jeśli 2*e+f-dt= 0, mamy dzielnik t.
Podobnie można zrobić z kandydatem na dzielnik s, uwzględniając znaleziony x. Tym razem:
b'-a*w + s*t*x = [e, s', f] - [cs, s, ds] + s*t*x = [e-cs+t*x, s, f-2*e-ds]
Jednak ostatnia wartość f-2*e-ds bywa na tyle mała, że trzeba dodać kilka s, aby uczynić ją nieujemną. Krotność dodanych s zmniejsza (e-cs+t*x).
Po tych przekształceniach zmniejszamy a = a'-x
Przykład numeryczny.
Wartość w = 2164, p' = s'*t' = 955*2035, 'obliczamy' p = p'+w = (s'+2)*(t'-2):
n = [a, p, b] =
4 * 1 943 425 + [570, 2035, 403] = 4 * 1 943 425 + [1215, 955, 28]
Sprawdzamy kandydatów t=2033, s=957:
w = 2164-8 = 2156,
a*w = [4, 2033, 492] = [9, 957, 11]
nowe b = [ct, t, dt] = 570*2035+403 - 4*2033-482 + 2033*957x =
(570-4+957x)*2033 + (1140+403-492)
w tym przypadku mamy x=0, bo 570-4>0
b = 566*2033+1051 = [566, 2033, 1051], 1051<>0, t=2033 nie jest dzielnikiem
dla s:
b = 1215*955+28 - 9*957-11 + 957*2033*0 = 1206*957-2413 = 1206*957+458 = [1206, 957, 458]
s też nie jest dzielnikiem
wartości a nie zmniejszamy, bo x=0.
Następna para s*t = 959*2033 ma a*w = 4*2156 = [4, 2031, 468] = [8, 959, 920]
Przekształcamy dopóki s stanie się większe niż t albo trzeci element trójki będzie zerem.
Wydaje mi się, że obliczanie s w analogiczny sposób jak t jest bezcelowe, lepiej podzielić znaną wartość b = ct*t+dt przez s resztami modulo.
Jak już wspomniałem poprzednio, dla małych s 'a*w' są gigantyczne, ale dla nich x jest duże. Zatem w maleje, a maleje, wkrótce zaczynamy coraz rzadziej dodawać s*t, tylko przy zmianie a.
Wygodnie jest nie pamiętać liczb n, lecz ich trójki [a,p,b]: n = a*p+b.
Jest to na dwu poziomach, jeden przy podstawie p, obliczanej przez dodanie zmniejszającej się o 8 wartości w. Drugi poziom dotyczy iloczynu a*w, rozpisanego trójką a*w = [c,t,d].
Wartość b zapisujemy analogiczną trójką b = [e,t,f]. Przy przekształcaniu odejmujemy b-a*w = [e-c,t,f-d] starając się, by wartość f-d była dodatnia. W razie potrzeby dodajemy s*t zmniejszając a. Wartość e-c dla sprawdzanego zakresu jest zawsze dodatnia. Podobnie można zrobić z wartością s.
Pamiętamy stare wartości (to te z primami).
Zaczynamy od s=3, t będącą nieparzystą wartością nieco mniejszą niż pierwiastek kwadratowy z rozkładanej liczby n, przyjmujemy w = 2*t-10;
Przy sprawdzaniu kolejnych dwu dzielników postępujemy następująco:
w = w'-8;
p = p'+w = (s'+2)*(t'-2) = s*t;
a*w = [ct, t, dt] = [cs, s, ds]
b' - a*w + s*t*x = [e, t', f] - [ct, t, dt] + s*t*x = [e-ct+s*x, t, 2*e+f-dt]
Rozwiązujemy nierówność liniową e-ct+s*x>0 zmiennej x szukając najmniejszego możliwego x. Od pewnego momentu jest x=1 lub x=0.
Jeśli 2*e+f-dt= 0, mamy dzielnik t.
Podobnie można zrobić z kandydatem na dzielnik s, uwzględniając znaleziony x. Tym razem:
b'-a*w + s*t*x = [e, s', f] - [cs, s, ds] + s*t*x = [e-cs+t*x, s, f-2*e-ds]
Jednak ostatnia wartość f-2*e-ds bywa na tyle mała, że trzeba dodać kilka s, aby uczynić ją nieujemną. Krotność dodanych s zmniejsza (e-cs+t*x).
Po tych przekształceniach zmniejszamy a = a'-x
Przykład numeryczny.
Wartość w = 2164, p' = s'*t' = 955*2035, 'obliczamy' p = p'+w = (s'+2)*(t'-2):
n = [a, p, b] =
4 * 1 943 425 + [570, 2035, 403] = 4 * 1 943 425 + [1215, 955, 28]
Sprawdzamy kandydatów t=2033, s=957:
w = 2164-8 = 2156,
a*w = [4, 2033, 492] = [9, 957, 11]
nowe b = [ct, t, dt] = 570*2035+403 - 4*2033-482 + 2033*957x =
(570-4+957x)*2033 + (1140+403-492)
w tym przypadku mamy x=0, bo 570-4>0
b = 566*2033+1051 = [566, 2033, 1051], 1051<>0, t=2033 nie jest dzielnikiem
dla s:
b = 1215*955+28 - 9*957-11 + 957*2033*0 = 1206*957-2413 = 1206*957+458 = [1206, 957, 458]
s też nie jest dzielnikiem
wartości a nie zmniejszamy, bo x=0.
Następna para s*t = 959*2033 ma a*w = 4*2156 = [4, 2031, 468] = [8, 959, 920]
Przekształcamy dopóki s stanie się większe niż t albo trzeci element trójki będzie zerem.
Wydaje mi się, że obliczanie s w analogiczny sposób jak t jest bezcelowe, lepiej podzielić znaną wartość b = ct*t+dt przez s resztami modulo.
Jak już wspomniałem poprzednio, dla małych s 'a*w' są gigantyczne, ale dla nich x jest duże. Zatem w maleje, a maleje, wkrótce zaczynamy coraz rzadziej dodawać s*t, tylko przy zmianie a.
12 listopada 2014
Równoczesne sprawdzanie dwu kandydatów na dzielniki
Dokończyłem standardowy przykład, w którym wyrażałem n w systemach o podstawach s*t, s<t oraz s i t są liczbami nieparzystymi sumującymi się do stałej wartości parzystej równej sufitowi z pierwiastka z n.
Wykorzystałem
n = a*(s*t)+b,
gdzie s=3+2k, t = 2(1/2 int sqrt n)-1-2k (nieparzysta wartość naturalna ograniczajaca pierwiastek z n z dołu).
Liczba n jest równaniem kwadratowym zmiennej k, zatem druga różnica jest stałą równą 8. Ewentualny dzielnik liczny n dzieli także resztę b, przy czym należy sprawdzić obydwa przypadki dla s oraz dla t.
Startujemy z s=3, t odpowiednio dopasowane do n. Przekształcamy n zwiększając równocześnie s o 2 oraz zmniejszając t o 2. Oznacza to przechodzenie na system o podstawie (s+2)(t-2), który różni się od danego o stałą (drugą różnicę, czyli 8a). Wartość a dla małych s bardzo szybko maleje. Przy małych a możemy zapisywać współczynnik b w systemach o podstawach s oraz t. Te przekształcenia są liniowe.
Mając iloczyn st, iloczyn (s+2)(t-2) uzyskuje się przez dodanie 8a do zapamiętanej wartości, ta zaś jest dodawana do podstawy. Ze wzrostem s (suma s+t jest stała) wartość ta maleje.
Jest to nadal trial division. Lecz wydaje mi się, że pomijając skrajne przypadki małych s uzyskamy algorytm mający mniej operacji aniżeli algorytm konwersji na kolejne systemy liczenia. Zwłaszcza jeśli nie zmieni się współczynnik a, gdyż po zmianie s, t zmniejszamy współczynnik b o pewną stale malejącą o 8 wartość (modulo st).
Niestety, występuje dzielenie b/s oraz b/t. Brak części ułamkowej tych ilorazów wskazuje dzielnik. Nie można przewidzieć jego wystąpienia.
Algorytm kończy się, gdy s stanie się większe od t. Praktycznie wyglądało to tak, że zapowiadał się koniec dla współczynnika a=4, dla którego jest kilkadziesiąt procent przypadków. Jednak w przykładzie pojawiły się wartości iloczynów st, dla których a było równe 3.
Obliczenia pomijając początkowe przypadki są bardzo proste. Jeszcze je badam.
Wykorzystałem
n = a*(s*t)+b,
gdzie s=3+2k, t = 2(1/2 int sqrt n)-1-2k (nieparzysta wartość naturalna ograniczajaca pierwiastek z n z dołu).
Liczba n jest równaniem kwadratowym zmiennej k, zatem druga różnica jest stałą równą 8. Ewentualny dzielnik liczny n dzieli także resztę b, przy czym należy sprawdzić obydwa przypadki dla s oraz dla t.
Startujemy z s=3, t odpowiednio dopasowane do n. Przekształcamy n zwiększając równocześnie s o 2 oraz zmniejszając t o 2. Oznacza to przechodzenie na system o podstawie (s+2)(t-2), który różni się od danego o stałą (drugą różnicę, czyli 8a). Wartość a dla małych s bardzo szybko maleje. Przy małych a możemy zapisywać współczynnik b w systemach o podstawach s oraz t. Te przekształcenia są liniowe.
Mając iloczyn st, iloczyn (s+2)(t-2) uzyskuje się przez dodanie 8a do zapamiętanej wartości, ta zaś jest dodawana do podstawy. Ze wzrostem s (suma s+t jest stała) wartość ta maleje.
Jest to nadal trial division. Lecz wydaje mi się, że pomijając skrajne przypadki małych s uzyskamy algorytm mający mniej operacji aniżeli algorytm konwersji na kolejne systemy liczenia. Zwłaszcza jeśli nie zmieni się współczynnik a, gdyż po zmianie s, t zmniejszamy współczynnik b o pewną stale malejącą o 8 wartość (modulo st).
Niestety, występuje dzielenie b/s oraz b/t. Brak części ułamkowej tych ilorazów wskazuje dzielnik. Nie można przewidzieć jego wystąpienia.
Algorytm kończy się, gdy s stanie się większe od t. Praktycznie wyglądało to tak, że zapowiadał się koniec dla współczynnika a=4, dla którego jest kilkadziesiąt procent przypadków. Jednak w przykładzie pojawiły się wartości iloczynów st, dla których a było równe 3.
Obliczenia pomijając początkowe przypadki są bardzo proste. Jeszcze je badam.
29 września 2014
Inne wyszukiwanie siłowe zamiast 'trial division'
Zapragnałem już pisać w C++ prototyp podejścia wielowątkowego relacyjno-funkcyjnego pod DOSa, kiedy pomyślałem sobie obejrzeć liczbę w systemach będących kwadratami kolejnych liczb naturalnych. Spodziewałem się, że pojawią małe reszty. Myliłem się.
Pojawiły się za to inne proste zależności. Mianowicie wiedziałem od początku, że nie będę musiał szukać kolejnego kwadratu siłowo. Różnica między p^2 oraz (p+2)^2 wynosi 4(p+1). Kiedy p jest nieparzyste, różnica ta jest kolejną wielokrotnością 8. Wynika to z p=2k+1, stąd 4((2k+1)+1) = 8k+8. Wartość k ma znaczenie w przebiegu i jest wykorzystywana.
Dla liczby n, począwszy od wartości p spełniajacej warunek p^4>n, dostajemy liczby 'dwucyfrowe' [a, b]_{p^2}:
n = a*p^2 + b = a*(2k+1)^2 + b.
Zatem liczb mających więcej niż 3 cyfry jest zaledwie pierwiastek czwartego stopnia.
Zwiękzając p, wartość a z początku bardzo szybko maleje, lecz gdy 8ak<p, pojawia się prostsza zależność.
Normalnie obliczałem odległość do kolejnego pierwiastka z p+1 do p+3, oraz zwiększałem zapamiętaną podstawę systemu o 8. W ten sposób znałem nową podstawę systemu bez podnoszenia do kwadratu, lecz przez dodanie sumy narastajacej o stałą. Teraz wystarczyło przekonwertować liczbę do odpowiedniego systemu.
Kiedy 'cyfra dziesiątek' a była odpowiednio mała, w szczególności spełniała warunek 8ak<p, okazało się, że konwersja sprowadza się do odjęcia stałej wartości 8a od b. Zatem można ją było zastąpić zwykłym odejmowaniem oraz naprawą w postaci, gdy b było ujemne operacjami
b=b+p^2; a=a-1
oraz oczywiście p=p+2.
Przy stałym a reszty b (wzrost p) tworzą ciąg malejący. Dla małych a wykres jest piłokształtny, a ciąg lokalnych maksimum b tworzy ciąg rosnący. Przejścia są proste, nie wymagają mnożenia ani dzielenia, jedyne co trzeba pamiętać od pewnego momentu i modyfikować to wartości
{a, b, k, p^2}.
Wartość a maleje jak 1/x, b ma charakter piłokształtny, k rośnie liniowo, p^2 rośnie kwadratowo, lecz wyznacza się je liniowo.
Najgorsze operacje to mnożenie 8ak po zmianie a, gdy a jest duże, oraz odejmowanie tej wartości od b. Oczywiście wtedy b staje się ujemne, oraz trzeba je skorygować dodając odpowiednią krotność aktualnego p^2.
Kolejnym niemiłym elementem jest znajdowanie dzielnika d, że n = d*q. Otóż wtedy d dzieli także b. Zatem mamy dzielenie (często dużych wartości) b przez d=(2k+1). Czyli to samo co w sposobie 'trial division'.
Wartości b były duże, gdyż p^2 dążyło do n. Tak więc metoda nie jest lepsza niż trywialne dzielenie przez kolejne wartości. Może tylko nieco dłużej utrzymuje mniejsze liczby dla dzielenia.
Metodę można bardzo łatwo odwrócić zaczynając od pierwiastka p^2<n<(p+3)^2, p nieparzyste. Wtedy zmniejszamy p, obliczenia przez pewien czas są bardzo proste, dopóki nie zaczynamy dodawać (konwersja) wartości większych niż podstawa p^2. Wtedy lepiej zmienić sposób, lecz kandydatów na dzielniki jest już stosunkowo mało (szacuję na parędziesiąt procent).
Metoda zasugerowała jednak kolejny sposób, w którym można badać równocześnie dwóch kandydatów na dzielniki. Przypadek ten jest obecnie sprawdzany.
Pojawiły się za to inne proste zależności. Mianowicie wiedziałem od początku, że nie będę musiał szukać kolejnego kwadratu siłowo. Różnica między p^2 oraz (p+2)^2 wynosi 4(p+1). Kiedy p jest nieparzyste, różnica ta jest kolejną wielokrotnością 8. Wynika to z p=2k+1, stąd 4((2k+1)+1) = 8k+8. Wartość k ma znaczenie w przebiegu i jest wykorzystywana.
Dla liczby n, począwszy od wartości p spełniajacej warunek p^4>n, dostajemy liczby 'dwucyfrowe' [a, b]_{p^2}:
n = a*p^2 + b = a*(2k+1)^2 + b.
Zatem liczb mających więcej niż 3 cyfry jest zaledwie pierwiastek czwartego stopnia.
Zwiękzając p, wartość a z początku bardzo szybko maleje, lecz gdy 8ak<p, pojawia się prostsza zależność.
Normalnie obliczałem odległość do kolejnego pierwiastka z p+1 do p+3, oraz zwiększałem zapamiętaną podstawę systemu o 8. W ten sposób znałem nową podstawę systemu bez podnoszenia do kwadratu, lecz przez dodanie sumy narastajacej o stałą. Teraz wystarczyło przekonwertować liczbę do odpowiedniego systemu.
Kiedy 'cyfra dziesiątek' a była odpowiednio mała, w szczególności spełniała warunek 8ak<p, okazało się, że konwersja sprowadza się do odjęcia stałej wartości 8a od b. Zatem można ją było zastąpić zwykłym odejmowaniem oraz naprawą w postaci, gdy b było ujemne operacjami
b=b+p^2; a=a-1
oraz oczywiście p=p+2.
Przy stałym a reszty b (wzrost p) tworzą ciąg malejący. Dla małych a wykres jest piłokształtny, a ciąg lokalnych maksimum b tworzy ciąg rosnący. Przejścia są proste, nie wymagają mnożenia ani dzielenia, jedyne co trzeba pamiętać od pewnego momentu i modyfikować to wartości
{a, b, k, p^2}.
Wartość a maleje jak 1/x, b ma charakter piłokształtny, k rośnie liniowo, p^2 rośnie kwadratowo, lecz wyznacza się je liniowo.
Najgorsze operacje to mnożenie 8ak po zmianie a, gdy a jest duże, oraz odejmowanie tej wartości od b. Oczywiście wtedy b staje się ujemne, oraz trzeba je skorygować dodając odpowiednią krotność aktualnego p^2.
Kolejnym niemiłym elementem jest znajdowanie dzielnika d, że n = d*q. Otóż wtedy d dzieli także b. Zatem mamy dzielenie (często dużych wartości) b przez d=(2k+1). Czyli to samo co w sposobie 'trial division'.
Wartości b były duże, gdyż p^2 dążyło do n. Tak więc metoda nie jest lepsza niż trywialne dzielenie przez kolejne wartości. Może tylko nieco dłużej utrzymuje mniejsze liczby dla dzielenia.
Metodę można bardzo łatwo odwrócić zaczynając od pierwiastka p^2<n<(p+3)^2, p nieparzyste. Wtedy zmniejszamy p, obliczenia przez pewien czas są bardzo proste, dopóki nie zaczynamy dodawać (konwersja) wartości większych niż podstawa p^2. Wtedy lepiej zmienić sposób, lecz kandydatów na dzielniki jest już stosunkowo mało (szacuję na parędziesiąt procent).
Metoda zasugerowała jednak kolejny sposób, w którym można badać równocześnie dwóch kandydatów na dzielniki. Przypadek ten jest obecnie sprawdzany.
Subskrybuj:
Posty (Atom)