Tym razem, po długiej przerwie, kolejny algorytm 'trial division' na rozkład liczby N na czynniki. Jak moje najnowsze podejścia, znów jest prosty dla bardzo dużych wartości, zaś daje w kość dla małych dzielników.
Przedstawiam liczbę N w postaci iloczynu dwu wartości p, q i reszty r:
N = p*q + r,
gdzie p>q są liczbami nieparzystymi, r jest liczbą nieujemną, zmniejszaną by nie przekraczała podwojonego q.
Podstawowym przekształceniem jest
(p+k)*(q-k) = pq + k(q-p) - k^2 (1) ,
albo w używanej postaci szczególnej
(p+2)*(q-2) = pq - 2(p-q) - 4 (2) .
Inicjacja następuje dla nieparzystych p = q < sqrt(N) lub p < sqrt N < q = p+2 gdy sqrt N jest parzyste. Liczba
r = N - pq
jest parzysta.
W kolejnych iteracjach wykorzystujemy stary iloczyn pq by dostać nowe r następująco:
p = p+2;
q = q-2;
s = r + 2(p-q) + 4;
r = s (mod 2q); // s można zapamiętać by mniej liczyć
p = p+ floor( s/ 2q );
jeśli r =0, dzielnikami są p i q.
niezmienniki: p, q nieparzyste, z r zabierana parzysta wielokrotność q, która jest dodawana do p.
W ten sposób p rośnie wykładniczo, zwłaszcza dla małych q, q maleje liniowo. Zmiany są bardzo małe, zwłaszcza dla q mniejszych niż pierwiastek sześcienny z 2N. Z kolei dla q mniejszych efekt wykładniczy modyfikuje p bardzo silnie.
W praktyce przeważająca krotność przypadków przypada na małe zmiany.
Do tego stopnia zmiany są małe, że dla dużych q możemy korzystać ze cech podzielności dla q i korzystając z (1) przeskakiwać nie po kolejnych nieparzystych, ale wybierać te, które nie mają dzielników 3, 5. Podobna zakusa istnieje też dla p, ale tylko dla tak dużych wartości, by p/q <2.
Przykład: fragment
sqrt 8934053 jest bliskie 2988
p = 2989, q = 2987, r = 5910
różnica 2(p-q)+4 = 8, zatem
p = 2991, q = 2985, r = 5918
jeszcze dwa razy i mamy
p = 2997, q = 2979, r = 5990 = 2*2979+32,
za duże r, dochodzi do głosu dzielenie r/ 2q , zatem uzyskujemy zwiększenie p:
p = 2999, q = 2979, r = 32
przy kolejnym zmniejszaniu q przenoszenia do p występują coraz częściej, aż od
p = 4169+2, q = 2141, r = 2*2141+3942
stają się powszechne
dochodzimy w pobliże dzielnika,
p = 8189+14 = 8203, q = 1089, r = 14*1089+986
p = 8205+14 = 8219, q = 1087, r = 14*1087
p = 8221+12 = 8233, q = 1085, r = 12*1085+1248
poczynając od wartości
p = 33971+258, q = 261, r = 258*261+284
lepiej zmienić algorytm. Tu już q jest stosunkowo bardzo małe względem p.
11 listopada 2016
27 czerwca 2016
Czy istnieje logarytmiczny sposób rozkładu liczb
Czy istnieje sposób rozkładu liczb, w którym kolejne obliczenia wyznaczają kolejne cyfry dzielników?
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
29 maja 2016
Zmniejszenie krotności przypadków dla bardzo dużych liczb, poprawka
Wspomniany w styczniu sposób zmniejszania krotności nie jest tak dobry, jak początkowo uważałem.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
25 stycznia 2016
Zmniejszenie krotności przypadków rozkładu dla bardzo dużych liczb
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
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
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)
Subskrybuj:
Posty (Atom)