Mnożenie bez przeniesień jest specyficznym zapisem liczb, w którym na miejscu cyfr mamy liczby. Mnożenie tak wykonywane nie ma ostatniej czynności, w której sumuje się iloczyny cząstkowe, przenosząc nadmiary. Przypominam sposób mnożenia, np. 15*15:
[1 5] * [1 5] = [1 5+5 25] = [1 10 25]
Po wykonaniu przeniesień: 15*15= [1+1 0+2 5] = 225.
Niech s będzie podłogą z pierwiastka kwadratowego liczby N, oraz s nie dzieli N. Wtedy w systemie liczbowym o podstawie s liczba N ma postać:
[1 y r],
gdzie -1<y<2, 0<r<s.
Usuńmy przeniesienie cyfry setek uzyskując:
[1 y r] = [0 s+y r] .
Jest to równocześnie iloczyn [a b]*[0 d] = [ad bd].
Oznacza to, że dla liczby zlożonej N istnieje takie k, że największy wspólny dzielnik
gcd(s+y-k, r+sk) > 1
jest dodatni, a nawet bywa dzielnikiem.
Zmieniając k o pozycję, nasunęły mi się przedstawienia iloczynów ks jako cyfr jedności w systemie o podstawie (s-k).
I to rzeczywiście działa. Dla N=8934053 mamy postać [2989 2921], zaś szukając k rozwiazujemy kongruencje:
2921 + 2988k > 0 (mod 2989-k) .
Przyrost przy zmianie k o 1 ma drugą róznicę stałą, A do rozkładu interesuje nas tylko największy wspólny dzielnik reszty i podstawy systemu. Dla dużych wartości są one bliskie sobie.
Dodatkowo, k nie musi być dodatnie, może też być ujemne. W podanym przykładzie uzyskałem
k=-272 oraz gcd(2989+272, 2921-k*2988) \equiv gcd(3261, 1087) = 1087.
Ciąg reszt z r+ks (mod s-k): 67, 64, 59, 52, 43, 32, 19, 4, 2985, 2967, ...
Z drugiej strony
k=815 oraz gcd(2989-815, 2921+k*815) \equiv gcd(2174, 1087)=1087 . Ciąg reszt 2923, 2927, ...
25 października 2018
Faktoryzacja metodą różnicy kwadratów
Ze wzorów skróconego mnożenia uzyskamy kolejny algorytm faktoryzacji. Cechuje się małymi wartościami roboczymi oraz brakiem mnożenia, dzielenia, Wykorzystuje za to dwukrotnie pierwiastkowanie całkowito-liczbowe.
Znany jest wzór dla n=p*q:
(p+q)^2 - (p-q)^2 = 4pq = 4n
Jeśli n jest nieparzyste, każdy składnik tego wzoru jest podzielny przez 4. Zatem istnieją takie a, b, że
a^2 - b^2 = n .
Odwracamy to rozumowanie: bierzemy różnicę kwadratów aproksymujących n z niedomiarem. Dodajemy po obu stronach różnicę do kolejnego kwadratu (tego mniejszego). Wartość ta zmniejsza niedomiar, a jak zamieni na nadmiar, łatwo policzyć kolejną wartość kwadratu.
Potrzebne sa: pierwiastek a, niedomiar r, pierwiastek b i niezmiennik
a^2 - r - b^2 =n
Zaczynamy pierwiastkując 4n dla uzyskania a (nadmiarowe), zaś resztę po drobnym dopasowaniu (połowienie dla możności wzięcia czwartej części) pierwiastkujemy ponownie dla uzyskania b i niedomiaru r.
Kiedy znajdziemy n jako różnicę pełnych kwadratów, dzielniki p, q liczymy z układu równań:
p + q = 2a
p - q = 2b
Pomijając rozwiązanie tego układu równań, Nie mamy więcej niż (p+q)+(p-q) = 2p modyfikacji polegających na dodaniu 2a+1, 2b+1 oraz równocześnie odpowiednio a++, b++. Wartość ta jest zmniejszana pierwiastkowaniami inicjującymi,
Złożoność nie przekracza O(P log n) gdzie stała P zależy od większego z dzielników n, złożoność arytmetyczna O(n).
Przykład: n=8934053, 2a = ceil sqrt(4n) > 5977, b policzymy po modyfikacji.
Mamy własność: suma dzielników nieparzystych jest parzysta podzielna przez 2, niepodzielna przez 4. Zatem jeszcze modyfikujemy a=(a+3)/2 uzyskując
a^2 - r - b^2 = 2990^2 - 118 - 77^2 = n
Następny kwadrat dla b to 78, większy o 2*77+1 = 155. Dodając tę wartość do niedomiaru 118 uzyskamy nadmiar 37, by uzyskać znów niedomiar dodajemy 2*2990+1 = 5981. Nowy niedomiar dla a=2991 to 5944.
2991^2 - 5944 - 78^2 = n
Postępując dalej w ten sposób uzyskamy a=4653, b=3566, z których jedno jest sumą połowy dzielników, drugie różnicą.
Wystąpiło (4653-2990)+(3566-77) = 5152 iteracji w porównaniu z 543 dzieleniami. Ale różnica między dzielnikami mająca wpływ na szybkość przekracza 7000.
Znany jest wzór dla n=p*q:
(p+q)^2 - (p-q)^2 = 4pq = 4n
Jeśli n jest nieparzyste, każdy składnik tego wzoru jest podzielny przez 4. Zatem istnieją takie a, b, że
a^2 - b^2 = n .
Odwracamy to rozumowanie: bierzemy różnicę kwadratów aproksymujących n z niedomiarem. Dodajemy po obu stronach różnicę do kolejnego kwadratu (tego mniejszego). Wartość ta zmniejsza niedomiar, a jak zamieni na nadmiar, łatwo policzyć kolejną wartość kwadratu.
Potrzebne sa: pierwiastek a, niedomiar r, pierwiastek b i niezmiennik
a^2 - r - b^2 =n
Zaczynamy pierwiastkując 4n dla uzyskania a (nadmiarowe), zaś resztę po drobnym dopasowaniu (połowienie dla możności wzięcia czwartej części) pierwiastkujemy ponownie dla uzyskania b i niedomiaru r.
Kiedy znajdziemy n jako różnicę pełnych kwadratów, dzielniki p, q liczymy z układu równań:
p + q = 2a
p - q = 2b
Pomijając rozwiązanie tego układu równań, Nie mamy więcej niż (p+q)+(p-q) = 2p modyfikacji polegających na dodaniu 2a+1, 2b+1 oraz równocześnie odpowiednio a++, b++. Wartość ta jest zmniejszana pierwiastkowaniami inicjującymi,
Złożoność nie przekracza O(P log n) gdzie stała P zależy od większego z dzielników n, złożoność arytmetyczna O(n).
Przykład: n=8934053, 2a = ceil sqrt(4n) > 5977, b policzymy po modyfikacji.
Mamy własność: suma dzielników nieparzystych jest parzysta podzielna przez 2, niepodzielna przez 4. Zatem jeszcze modyfikujemy a=(a+3)/2 uzyskując
a^2 - r - b^2 = 2990^2 - 118 - 77^2 = n
Następny kwadrat dla b to 78, większy o 2*77+1 = 155. Dodając tę wartość do niedomiaru 118 uzyskamy nadmiar 37, by uzyskać znów niedomiar dodajemy 2*2990+1 = 5981. Nowy niedomiar dla a=2991 to 5944.
2991^2 - 5944 - 78^2 = n
Postępując dalej w ten sposób uzyskamy a=4653, b=3566, z których jedno jest sumą połowy dzielników, drugie różnicą.
Wystąpiło (4653-2990)+(3566-77) = 5152 iteracji w porównaniu z 543 dzieleniami. Ale różnica między dzielnikami mająca wpływ na szybkość przekracza 7000.
13 października 2018
Najkrótsze sieci a plaster miodu
Lev Kurlyandchik napisał książkę pt. Najkrótsze sieci. Są tam tematy, które poruszam na tym blogu, ułamki egipskie. Rozdział pierwszy jest poświęcony drzewom Steinera - w grafie szukamy połaczeń węzłów, by suma krawędzi była jak najmniejsza. W odróżnieniu od najkrótszego drzewa rozpinającego, do grafu tego można, a nawet czasem należy dołączać nowe węzły.
Autor pisze językiem matematyki skupiając się na szczególnych przypadkach, mam podejście nieco bardziej inżynieryjne. Jest opis 'gotowego' algorytmu, ale nie podchodzi mi on. Polega na połączeniu dwu wejściowych wierzchołków z nowo wyznaczanym wierzchołkiem w jeden 'wierzchołek' dla rekursji. Mamy wtedy graf o mniejszej liczności wierzchołków. Ale wyczuwam pewny kłopot związany z kolejnością wierzchołków grafu.
Widzę inne rozwiązanie.
Najpierw jednak powtórzę za autorem własności najkrótszej sieci:
- z każdego węzła wychodzą co najwyżej 3 krawędzie, zaś kąty między nimi wynoszą nie mniej niż 120 stopni;
- nie istnieje łamana zamknięta.
Przyjmując te własności za punkt wyjścia, istnieje zanurzenie grafu w plaster miodu mające podane własności. Plaster miodu jest parkietem sześciokątów foremnych, w którym suma przeciwległych krawędzi jest stała. Usuwając którąkolwiek dostajemy dobre przybleżenie drzewa Steinera. Zatem sposób konstrukcji byłby następujący (płaszczyzna Euklidesowa analitycznie):
- pierwsze dwa wierzchołki wejsciowe są połączone krawędzią równoległą do plastra miodu (np. pionową, w razie potrzeby wystarczy obrócić);
- pobieram wierzchołek, oraz prowadzę z niego do 6 półprostych w kierunkach plastra miodu;
- półproste przecinają najbliższe krawędzie grafu, szukam wierzchołków grafu wyznaczonych tymi krawędziami W, mogą być wejściowe (zbiór D) lub Steinera (wyznaczone łamanymi);
- z każdego wskazanego wierzchołka W prowadzę dwie łamane po krawędziach plastra do nowo przyłączanego wierzchołka D, wyznaczają one po dwa nowe wierzchołki Steinera S, część z nich może należeć do generowanego docelowo drzewa;
- po uwzględnieniu wszystkich wierzchołków wejściowych następuje druga faza
- eliminacja cykli - łamanych zamkniętych przez kasowanie najdłuższej pojedynczej krawędzi (suma długości krawędzi przeciwległych plastra miodu jest stała); czasem można skasować także pomocniczy wierzchołek S;
- warunek trzech wychodzących krawędzi nachylonych względem siebie o 120 stopni przesuwa niektóre wierzchołki S; modyfikacje są w obrębie 7 najbliższych plastrów, nie mają one wpływu na resztę grafu;
- finalizacja, jeśli dwa wierzchołki sa połączone łamaną z wierzchołkiem S, jest on kasowany, zaś łamana jest zastępowana krawędzią je łączącą.
Uzyskamy w ten sposób drzewo, które ma małą sumę długości krawędzi. Nie orientuję się do końca, czy jest to drzewo Steinera, ale jest mu bardzo bliskie.
Autor pisze językiem matematyki skupiając się na szczególnych przypadkach, mam podejście nieco bardziej inżynieryjne. Jest opis 'gotowego' algorytmu, ale nie podchodzi mi on. Polega na połączeniu dwu wejściowych wierzchołków z nowo wyznaczanym wierzchołkiem w jeden 'wierzchołek' dla rekursji. Mamy wtedy graf o mniejszej liczności wierzchołków. Ale wyczuwam pewny kłopot związany z kolejnością wierzchołków grafu.
Widzę inne rozwiązanie.
Najpierw jednak powtórzę za autorem własności najkrótszej sieci:
- z każdego węzła wychodzą co najwyżej 3 krawędzie, zaś kąty między nimi wynoszą nie mniej niż 120 stopni;
- nie istnieje łamana zamknięta.
Przyjmując te własności za punkt wyjścia, istnieje zanurzenie grafu w plaster miodu mające podane własności. Plaster miodu jest parkietem sześciokątów foremnych, w którym suma przeciwległych krawędzi jest stała. Usuwając którąkolwiek dostajemy dobre przybleżenie drzewa Steinera. Zatem sposób konstrukcji byłby następujący (płaszczyzna Euklidesowa analitycznie):
- pierwsze dwa wierzchołki wejsciowe są połączone krawędzią równoległą do plastra miodu (np. pionową, w razie potrzeby wystarczy obrócić);
- pobieram wierzchołek, oraz prowadzę z niego do 6 półprostych w kierunkach plastra miodu;
- półproste przecinają najbliższe krawędzie grafu, szukam wierzchołków grafu wyznaczonych tymi krawędziami W, mogą być wejściowe (zbiór D) lub Steinera (wyznaczone łamanymi);
- z każdego wskazanego wierzchołka W prowadzę dwie łamane po krawędziach plastra do nowo przyłączanego wierzchołka D, wyznaczają one po dwa nowe wierzchołki Steinera S, część z nich może należeć do generowanego docelowo drzewa;
- po uwzględnieniu wszystkich wierzchołków wejściowych następuje druga faza
- eliminacja cykli - łamanych zamkniętych przez kasowanie najdłuższej pojedynczej krawędzi (suma długości krawędzi przeciwległych plastra miodu jest stała); czasem można skasować także pomocniczy wierzchołek S;
- warunek trzech wychodzących krawędzi nachylonych względem siebie o 120 stopni przesuwa niektóre wierzchołki S; modyfikacje są w obrębie 7 najbliższych plastrów, nie mają one wpływu na resztę grafu;
- finalizacja, jeśli dwa wierzchołki sa połączone łamaną z wierzchołkiem S, jest on kasowany, zaś łamana jest zastępowana krawędzią je łączącą.
Uzyskamy w ten sposób drzewo, które ma małą sumę długości krawędzi. Nie orientuję się do końca, czy jest to drzewo Steinera, ale jest mu bardzo bliskie.
09 września 2018
Szukanie dzielników liczby wprost, odwrócenie mnożenia, pierwsze rezultaty
Pogubiłem się w przykładzie dla większej liczby. Kalkulatory przy tych obliczeniach przestały być pomocne.
Zmodyfikowałem zatem przebieg. Nie muszę brać liczb większych, lecz wybierać wzrastajace wartości. Zatem przebieg jest następujący (to jeszcze nie algorytm).
Mam wartości binarne a, b, liczbę binarną N, oraz kontrolny schemat W (niepotrzebny, ale służy do testowania).
Mam już wyznaczone najbardziej znaczące cyfry a i b.
Zwiększam a i b dwukrotnie i przesuwam o jedną pozycję ku cyfrom mniej znaczącym. Jeszcze nie znam najmniej znaczących bitów a i b. To mogę być zera lub jedynki, np. gdy a=10001, uzyskamy wzorzec a=0100010 (długość o 2 większa). Teraz chcę dopasować najmniej znaczace bity.
Modyfikuję N (a_{k+1} = 2a_k) by móc porównać z wzorcami dla a, b.
Teraz przypadki dla odpowiednio przyciętego do schematów N:
- kiedy N<a,b, wartości te zostają bez zmian,
- kiedy N>a+b, odejmuję a, b; zwiększam najmniej znaczącą pozycję tych wzorców o 1, ale od N przenoszę tyko jedynkę do schematu W
- w pozostałych przypadkach odejmuję od N któryś ze wzorców a albo b (zwiększając równocześnie o tę wartosć W), zwiększając o jeden najmniej znaczącą cyfrę drugiego schematu.
Wybór wzorca z początku był prosty - upodabniał się do cyfr początkowych a albo b.
Z początku gładko, ale po wyznaczeniu (dokładnym) kilku cyfr binarnych dzielników pojawiły się drobne niuanse. Wartość z N sugerowała istnienie ustawionego bitu, choć wartości a i b miały kończyć się zerami.
Docelowo a, b stają się dzielnikami, nie dbam tu o zgodnosć długości, wyniknie to przy końcu sprawdzania gdy wzorce wypełnią liczbę N do końca. Wtedy wystarczy przyciąć ich długość - kiedy dzielniki są różnej długości jeden z nich kończy się zerami a powinien jedynką. Podczas procesów narzucam równą długość schematów a i b.
Zatem jest to sposób na wyznaczenie wielu bitów dzielników, ale jeszcze nie do końca skuteczny. Dla testowanej liczby 101-bitowej wyznaczyłem poprawnie po 12 bitów obu dzielników.
Pomyślałem o możliwości zmiany reszty wskazującej stan bitu - raz działa, raz nie. Zatem wyznaczanie dzielników od najbardziej znaczących bitów jest zawodne. Spróbuję od najmniej znaczących pozycji.
Zmodyfikowałem zatem przebieg. Nie muszę brać liczb większych, lecz wybierać wzrastajace wartości. Zatem przebieg jest następujący (to jeszcze nie algorytm).
Mam wartości binarne a, b, liczbę binarną N, oraz kontrolny schemat W (niepotrzebny, ale służy do testowania).
Mam już wyznaczone najbardziej znaczące cyfry a i b.
Zwiększam a i b dwukrotnie i przesuwam o jedną pozycję ku cyfrom mniej znaczącym. Jeszcze nie znam najmniej znaczących bitów a i b. To mogę być zera lub jedynki, np. gdy a=10001, uzyskamy wzorzec a=0100010 (długość o 2 większa). Teraz chcę dopasować najmniej znaczace bity.
Modyfikuję N (a_{k+1} = 2a_k) by móc porównać z wzorcami dla a, b.
Teraz przypadki dla odpowiednio przyciętego do schematów N:
- kiedy N<a,b, wartości te zostają bez zmian,
- kiedy N>a+b, odejmuję a, b; zwiększam najmniej znaczącą pozycję tych wzorców o 1, ale od N przenoszę tyko jedynkę do schematu W
- w pozostałych przypadkach odejmuję od N któryś ze wzorców a albo b (zwiększając równocześnie o tę wartosć W), zwiększając o jeden najmniej znaczącą cyfrę drugiego schematu.
Wybór wzorca z początku był prosty - upodabniał się do cyfr początkowych a albo b.
Z początku gładko, ale po wyznaczeniu (dokładnym) kilku cyfr binarnych dzielników pojawiły się drobne niuanse. Wartość z N sugerowała istnienie ustawionego bitu, choć wartości a i b miały kończyć się zerami.
Docelowo a, b stają się dzielnikami, nie dbam tu o zgodnosć długości, wyniknie to przy końcu sprawdzania gdy wzorce wypełnią liczbę N do końca. Wtedy wystarczy przyciąć ich długość - kiedy dzielniki są różnej długości jeden z nich kończy się zerami a powinien jedynką. Podczas procesów narzucam równą długość schematów a i b.
Zatem jest to sposób na wyznaczenie wielu bitów dzielników, ale jeszcze nie do końca skuteczny. Dla testowanej liczby 101-bitowej wyznaczyłem poprawnie po 12 bitów obu dzielników.
Pomyślałem o możliwości zmiany reszty wskazującej stan bitu - raz działa, raz nie. Zatem wyznaczanie dzielników od najbardziej znaczących bitów jest zawodne. Spróbuję od najmniej znaczących pozycji.
04 sierpnia 2018
Szukanie dzielników liczby wprost, odwrócenie mnożenia
Szuka się dzielników liczby w różny sposób. Ale w żadnym miejscu nie spotkałem zwykłego odwrócenia mnożenia. Domyślam się, co jest tego powodem - przeniesienia. Kiedy próbowałem znaleźć funkcję odwrotną do mnozenia od cyfr najmniej znaczących, przeniesienia wyzwalały nieoznaczoność, dzięki czemu znajdowałem zaledwie cyfrę najmniej znaczącą (też nie w każdym przypadku).
Jest jeszcze jeden problem - znajomość długości dzielników, czyli liczność ich bitów. To skomplikowało jeden z algorytmów, w których dopasowywałem liczbę do wzorca bitowego.
Niech zatem a i b będą stosunkowo małymi liczbami binarnymi, oraz dla pewnego wykładnika potegi k mamy
a*b*2^k <= N < a*(b+1)*2^k .
Dalej będę dopasowywał liczbę binarną N do wzorca binarnego W o wartości N, ale subtelniej.Wzorzec przypomina liczbę, lecz na pozycji cyfr mogą stać dowolne liczby nieujemne, ograniczone z góry krotnością bitów przypuszczalnych dzielników. Tzn. jeśli dzielnik ma 7 cyfr, w tym 3 ustawione bity, na żaden pozycji wzorca wartość nie przekroczy 3. Dla liczby 7-bitowej z siedmioma ustawionymi bitami na żadnej pozycji wzorca nie pojawi się wartość większa niż 7.
Na wzorzec najlepiej spojrzeć jak na iloczyn pisemny dwu liczb binarnych, w których nie dokonaliśmy przeniesień, czyli np. 11b * 111b = [1 2 2 1] (po trzech przeniesieniach 10101b).
Pierwsze spostrzeżenie, długość a można przenosić do długości b, o ile a kończy się zerami, tzn. ab = 1100*101 = 11*10100.
A najlepiej niech a i b zaczynają się i kończą ustawionymi bitami, a potrzebną długość pobieramy z k. Dlatego pozwalam by liczba 'binarna' a kończyła się dwójką, np. 12b = 1*2+2=4.
Spstrzeżenie drugie, gdy liczba po lekkiej modyfikacji a_{m+1) = 2a_m będzie mniejsza niż liczba o cyfrach najbardziej znaczących 10..020..011... (krotność zer jest równa), dzielniki na pewno zaczynają się od 10..0... z daną krotnością. W tym przypadku suma długości a*b i potęgi k jest długością liczby N. W innym przypadku suma długości a*b i k jest o 1 mniejsza.
Spostrzeżenie trzecie, jeśli wciskamy liczbę N we wzorzec W dla znalezionych wartości a*b*2^k, możliwe maksymalne przeniesienie cyfr bardziej znaczących N jest pojedynczym bitem na pozycji k+1. Zmniejszając tę wartość znika jedno z przeniesień.
I wydaje mi się, że te spostrzeżenia wystarczą do wyznaczenia dzielników.
Przyjmujemy a=11 lub a=12, dopasowujemy b tak, by schemat dla a*b*2^k był tylko odrobinę większy niż N. Długość b ma być nie mniejsza niż długość a. Dopasowujemy najbardziej znaczące cyfry binarne N do wzorca. Często uzyskamy za dużo, co oznacza, że wzięta została za duża wartość a, należy ją zmniejszyć. Niech jednak a nie kończy się zerem, lecz wartością 1, 2.
Powinniśmy sprawdzić, czy przypadkiem nie trafiliśmy już na dzielnik.
Jeśli już przekształcimy co się da, zwiększamy a=2a+1 i znów dopasowujemy b oraz N do wzorca dla a*b.
Ciąg (a) w kolejnych iteracjach powinien rozbieżnie dążyć do dzielnika. Tyle teoria wg jednego przykładu. A jak praktyka w ogólności?
Jest jeszcze jeden problem - znajomość długości dzielników, czyli liczność ich bitów. To skomplikowało jeden z algorytmów, w których dopasowywałem liczbę do wzorca bitowego.
Niech zatem a i b będą stosunkowo małymi liczbami binarnymi, oraz dla pewnego wykładnika potegi k mamy
a*b*2^k <= N < a*(b+1)*2^k .
Dalej będę dopasowywał liczbę binarną N do wzorca binarnego W o wartości N, ale subtelniej.Wzorzec przypomina liczbę, lecz na pozycji cyfr mogą stać dowolne liczby nieujemne, ograniczone z góry krotnością bitów przypuszczalnych dzielników. Tzn. jeśli dzielnik ma 7 cyfr, w tym 3 ustawione bity, na żaden pozycji wzorca wartość nie przekroczy 3. Dla liczby 7-bitowej z siedmioma ustawionymi bitami na żadnej pozycji wzorca nie pojawi się wartość większa niż 7.
Na wzorzec najlepiej spojrzeć jak na iloczyn pisemny dwu liczb binarnych, w których nie dokonaliśmy przeniesień, czyli np. 11b * 111b = [1 2 2 1] (po trzech przeniesieniach 10101b).
Pierwsze spostrzeżenie, długość a można przenosić do długości b, o ile a kończy się zerami, tzn. ab = 1100*101 = 11*10100.
A najlepiej niech a i b zaczynają się i kończą ustawionymi bitami, a potrzebną długość pobieramy z k. Dlatego pozwalam by liczba 'binarna' a kończyła się dwójką, np. 12b = 1*2+2=4.
Spstrzeżenie drugie, gdy liczba po lekkiej modyfikacji a_{m+1) = 2a_m będzie mniejsza niż liczba o cyfrach najbardziej znaczących 10..020..011... (krotność zer jest równa), dzielniki na pewno zaczynają się od 10..0... z daną krotnością. W tym przypadku suma długości a*b i potęgi k jest długością liczby N. W innym przypadku suma długości a*b i k jest o 1 mniejsza.
Spostrzeżenie trzecie, jeśli wciskamy liczbę N we wzorzec W dla znalezionych wartości a*b*2^k, możliwe maksymalne przeniesienie cyfr bardziej znaczących N jest pojedynczym bitem na pozycji k+1. Zmniejszając tę wartość znika jedno z przeniesień.
I wydaje mi się, że te spostrzeżenia wystarczą do wyznaczenia dzielników.
Przyjmujemy a=11 lub a=12, dopasowujemy b tak, by schemat dla a*b*2^k był tylko odrobinę większy niż N. Długość b ma być nie mniejsza niż długość a. Dopasowujemy najbardziej znaczące cyfry binarne N do wzorca. Często uzyskamy za dużo, co oznacza, że wzięta została za duża wartość a, należy ją zmniejszyć. Niech jednak a nie kończy się zerem, lecz wartością 1, 2.
Powinniśmy sprawdzić, czy przypadkiem nie trafiliśmy już na dzielnik.
Jeśli już przekształcimy co się da, zwiększamy a=2a+1 i znów dopasowujemy b oraz N do wzorca dla a*b.
Ciąg (a) w kolejnych iteracjach powinien rozbieżnie dążyć do dzielnika. Tyle teoria wg jednego przykładu. A jak praktyka w ogólności?
Detekcja wielokrotności potęg w dużych liczbach
Palindromy mogą służyć jako w miarę prosty detektor, czy dana liczba (odpowiednio duża) jest postaci
N = p*q^k,
operując na mniejszych potęgach a^k.
Pokażę sposób dla k=2.
Liczbę A = 4a+2b+a zapiszemy jako palindrom [a b a]. Reprezentacja ta jest niejednoznaczna, np. nieparzyste A przedstawimy także jako A = [1 (A-5)/2 1]. Niezmienicza jest jednak wartość liczby. Podobnie inne palindromy nad systemem binarnym mają niezmienianą wartość.
Pomnóżmy zachowując strukturę palindromu [...], tzn. nie wykonując przeniesień pomiędzy poszczególnymi pozycjami:
A*A = A^2 = [a^2 2ab 2a^2+b^2 2ab a^2]
Pomnóżmy to dodatkowo przez Q = [1 c 1]
QA^2 = [a^2 ca^2+2ab 3a^2+b^2+2abc c(2a^2+b^2)+4ab 3a^2+b^2+2abc ca^2+2ab a^2]
Na poszczególnych pozycjach pojawia się stosunkowo prosta kombinacja współczynników.
Wystarczy teraz dopasować wartość liczby N do tych współczynników.
Pragniemy uzyskać jak najprostsza postać, czyli stosunkowo największe a, najmniejsze b i ogromne c. Rozwiązujemy układ równań na a, b, c, przenosząc wartości jak w systemie binarnym, tzn.
schemat [2 -1 0 -12 0 -1 2] oznacza 2*(64+1) - (32+8*12+2) = 0.
Inny schemat roboczy [0 2 -1 -6 -1 2 0]
Dla liczby 1087^2 * 8219 takim palindromem jest:
[217^2 217^2*4107+434 1+4107*2*217+3*217^2 4107(1+2*217^2)+2*2*217 1+4107*2*217+3*217^2 217^2*4107+434 217^2]
oraz [217 1 217] = 1087, [1 4107 1] = 8219.
Wartość 1087^2 została zastąpiona przez 217^2, co przy detekcji ma znaczenie.
Dodatkowo, dla liczb nieparzystych a jest zawsze nieparzyste.
N = p*q^k,
operując na mniejszych potęgach a^k.
Pokażę sposób dla k=2.
Liczbę A = 4a+2b+a zapiszemy jako palindrom [a b a]. Reprezentacja ta jest niejednoznaczna, np. nieparzyste A przedstawimy także jako A = [1 (A-5)/2 1]. Niezmienicza jest jednak wartość liczby. Podobnie inne palindromy nad systemem binarnym mają niezmienianą wartość.
Pomnóżmy zachowując strukturę palindromu [...], tzn. nie wykonując przeniesień pomiędzy poszczególnymi pozycjami:
A*A = A^2 = [a^2 2ab 2a^2+b^2 2ab a^2]
Pomnóżmy to dodatkowo przez Q = [1 c 1]
QA^2 = [a^2 ca^2+2ab 3a^2+b^2+2abc c(2a^2+b^2)+4ab 3a^2+b^2+2abc ca^2+2ab a^2]
Na poszczególnych pozycjach pojawia się stosunkowo prosta kombinacja współczynników.
Wystarczy teraz dopasować wartość liczby N do tych współczynników.
Pragniemy uzyskać jak najprostsza postać, czyli stosunkowo największe a, najmniejsze b i ogromne c. Rozwiązujemy układ równań na a, b, c, przenosząc wartości jak w systemie binarnym, tzn.
schemat [2 -1 0 -12 0 -1 2] oznacza 2*(64+1) - (32+8*12+2) = 0.
Inny schemat roboczy [0 2 -1 -6 -1 2 0]
Dla liczby 1087^2 * 8219 takim palindromem jest:
[217^2 217^2*4107+434 1+4107*2*217+3*217^2 4107(1+2*217^2)+2*2*217 1+4107*2*217+3*217^2 217^2*4107+434 217^2]
oraz [217 1 217] = 1087, [1 4107 1] = 8219.
Wartość 1087^2 została zastąpiona przez 217^2, co przy detekcji ma znaczenie.
Dodatkowo, dla liczb nieparzystych a jest zawsze nieparzyste.
21 czerwca 2018
Faktoryzacja według Fermata - lecz z innego wzoru
Fermat zaproponował faktoryzację z pomocą
n = a^2-b^2 = (a-b)*(a+b).
Sa też inne wzory skróconego mnożenia, np.
(a+b)^2 = a^2 + 2ab + b^2.
W szczególnym przypadku n=a*b kwadratami są:
t^2 = a^2+b^2 + 2n;
r^2 = a^2+b^2 - 2n
Możemy zacząć od a = b równym albo bliskim pierwiastkowi sqrt n, poczym zwiększać a, zmniejszać b
a^2 + b^2 = (a+2)^2+(b-2)^2 - (4a-4b+8) = (a+2)^2+(b-2)^2 - 4(a-b+2) (0)
sprawdzajac, czy uzyskane reszty są kwadratami. Nie musimy tego liczyć. Wystarczy znać odległość od najbliższego kwadratu
c = t^2 - (a^2+b^2+2n) > 0 (1)
d = (a^2+b^2-2n)-r^2 > 0
oraz zmieniać
c = c-4(a+b-2), gdy przekroczymy t^2 zmieniamy na (t+2)^2 stosując przekształcenie
(t+2)^ - t^2 = 4t+4 = 4(t+1)
które znowu pozwala przybliżać się do kwadratu po c dodatnich. Pamiętamy tylko t.
Z kwadratem r^2 robimy podobnie modyfikując dystans d od r^2, tu jest gorzej, gdyż kwadraty są stosunkowo małymi liczbami, przynajmniej początkowo.
Istotna jest parzystość. Wartości a,b są nieparzyste, zaś t, r parzyste. Wtedy uzyskamy nieparzyste dzielniki liczby n.
Przykładowo dla n=8934053 mamy inicjację
t=5978, a=b=2989
różnica c = 136 z (1), różnica d=8;
modyfikujemy a+2, b-2 uzyskując zmianę e=4(a-b+2), którą odejmujemy od c,d:
t=5978, a=2991, b=2987, c=128, d=0
mamy kwadrat dla różnicy, dla rozkładu potrzebny jest równocześnie kwadrat różnicy i kwadrat sumy. Początkowo często e>d, zatem zwiększamy r o 2.
Okazuje się, że przekształcenie (0) nie wystarczy. Potrzebne jest jeszcze jedno:
a^2+b^2 = (a+2)^2+b^2 - (4a+4) (2)
To przekształcenie też bardzo miesza z kwadratem r.
Rozkład n następuje wtedy, gdy osiągniemy
t = 9306 = suma dzielników n,
a, b są dzielnikami n
r = 7132 = różnica dzielników n
Obliczeń jest tak dużo, że metoda ta ma wiecej przekształceń niż 'trial division'. Nie jest efektywna, choć istnieje możliwość przyspieszenia obliczeń, gdy c jest tak duże że można je częściowo zastąpić szeregiem
e + (e+16) + (e+2*16) + ... (e+k*16)
wszystko się dzieje dla stałego t, ale r początkowo trzeba liczyć niemal od początku.
n = a^2-b^2 = (a-b)*(a+b).
Sa też inne wzory skróconego mnożenia, np.
(a+b)^2 = a^2 + 2ab + b^2.
W szczególnym przypadku n=a*b kwadratami są:
t^2 = a^2+b^2 + 2n;
r^2 = a^2+b^2 - 2n
Możemy zacząć od a = b równym albo bliskim pierwiastkowi sqrt n, poczym zwiększać a, zmniejszać b
a^2 + b^2 = (a+2)^2+(b-2)^2 - (4a-4b+8) = (a+2)^2+(b-2)^2 - 4(a-b+2) (0)
sprawdzajac, czy uzyskane reszty są kwadratami. Nie musimy tego liczyć. Wystarczy znać odległość od najbliższego kwadratu
c = t^2 - (a^2+b^2+2n) > 0 (1)
d = (a^2+b^2-2n)-r^2 > 0
oraz zmieniać
c = c-4(a+b-2), gdy przekroczymy t^2 zmieniamy na (t+2)^2 stosując przekształcenie
(t+2)^ - t^2 = 4t+4 = 4(t+1)
które znowu pozwala przybliżać się do kwadratu po c dodatnich. Pamiętamy tylko t.
Z kwadratem r^2 robimy podobnie modyfikując dystans d od r^2, tu jest gorzej, gdyż kwadraty są stosunkowo małymi liczbami, przynajmniej początkowo.
Istotna jest parzystość. Wartości a,b są nieparzyste, zaś t, r parzyste. Wtedy uzyskamy nieparzyste dzielniki liczby n.
Przykładowo dla n=8934053 mamy inicjację
t=5978, a=b=2989
różnica c = 136 z (1), różnica d=8;
modyfikujemy a+2, b-2 uzyskując zmianę e=4(a-b+2), którą odejmujemy od c,d:
t=5978, a=2991, b=2987, c=128, d=0
mamy kwadrat dla różnicy, dla rozkładu potrzebny jest równocześnie kwadrat różnicy i kwadrat sumy. Początkowo często e>d, zatem zwiększamy r o 2.
Okazuje się, że przekształcenie (0) nie wystarczy. Potrzebne jest jeszcze jedno:
a^2+b^2 = (a+2)^2+b^2 - (4a+4) (2)
To przekształcenie też bardzo miesza z kwadratem r.
Rozkład n następuje wtedy, gdy osiągniemy
t = 9306 = suma dzielników n,
a, b są dzielnikami n
r = 7132 = różnica dzielników n
Obliczeń jest tak dużo, że metoda ta ma wiecej przekształceń niż 'trial division'. Nie jest efektywna, choć istnieje możliwość przyspieszenia obliczeń, gdy c jest tak duże że można je częściowo zastąpić szeregiem
e + (e+16) + (e+2*16) + ... (e+k*16)
wszystko się dzieje dla stałego t, ale r początkowo trzeba liczyć niemal od początku.
05 czerwca 2018
sumy iloczynów jako niedziesiątkowy system liczbowy
Zastanawiało mnie, jak zachowują się reszty, kiedy przechowuję w pamięci nie tyle wartości, co iloczyny.
Niech k będzie liczbą naturalną. Liczbę naturalną N przedstawiamy jako sumę
a_m k(k-1)...(k-m) + a_{m-1}k(k-1)...(k-m+1) + ... + a_1 k + a_0 .
Albo, myśląc o rozkładzie, co druga wartość, czyli przy a_m, 2|m będzie:
k(k-2)(k-4)...(k-m/2)
Zmiany k są jak najbardziej możliwe, zmiana k na k+2 polega na wyłączeniu z iloczynu wartości większej i zmodyfikowaniu sąsiednich wyrazów.
Okazało się, że ten sposób modyfikuje nie tylko a_i, oraz a_{i-1}, ale czasem i iloczyn mający jeden czynnik więcej.
Kiedy nauczyłem się przechodzić z k na k+2, zastanawiały mnie zmiany najmniej znaczącego składnika a_0 ze wzrostem k.
I zauważyłem, że współczynniki a_m, ... a_0 zachowują się jak cyfry, choć z zupełnie innymi zasadami przenoszenia, zaś iloczyny k...(k-i) pełnią rolę podstaw k^i.
Utworzył się w ten sposób nowy system liczbowy, chociaż nie wydaje się on pozycyjny - iloczyny trzeba zawsze zapisywać. Im większa wartość k, tym mniej składników, jak w standardowych systemach pozycyjnych niedziesiątkowych przy dużych podstawach.
A co ze współczynnikiem a_0? Jak systemach pozycyjnych przy p^k wartości tej reszty od pewnego miejsca zaczęły aproksymować przedziałami równanie logistyczne ax(b-x), tak tu takie zachowanie jest bardzo rzadkie. Przy dużych wartościach (trzech składnikach) kolejny przyrost to prosta kombinacja liniowa, o tyle o a_0 nie możemy niemal nic powiedzieć oprócz tego, że rzadko bywa skrajna. Silne regularności występują natomiast przy współczynnikach a_2, a_1.
Przykładowo, liczbę przedstawioną jako
N = 9 * 967 * 969 + 516 * 969 + 842
przekształcamy z k=969 na k=971 następująco:
pozycja 9*967*969 chwilowo bez zmian,
różnica 971-967=4, daje zmianę 9*4 dla a_1, czyli ten wspólczynnik oblicza się następująco:
516-4*9 = 480
Dodatni, więc a_2 pozostaje bez zmian.
Ale mamy 480*969, a powinniśmy mieć 480*971, różnica 2, kontynuujemy z a_0:
842-2*480 = -118, za mało
wykorzystujemy przeniesienie 1 z a_1, czyli 480-1 = 479, a dodajemy zwiększone k=971, czyli
842-2*480+971 = 853
Nowa postać dla k=971 wygląda:
N = 9 * 969 * 971 + 479 * 971 + 853
I takie przeniesienia są bardzo częste.
Czy zatem opłaca się trzymać wartości jako sumę iloczynów? Czy lepiej używać standardowych postaci systemów pozycyjnych? Są tu dodatkowe przekształcenia pozwalające wprowadzić nowe typy cech podzielności, niewiele więcej.
Niech k będzie liczbą naturalną. Liczbę naturalną N przedstawiamy jako sumę
a_m k(k-1)...(k-m) + a_{m-1}k(k-1)...(k-m+1) + ... + a_1 k + a_0 .
Albo, myśląc o rozkładzie, co druga wartość, czyli przy a_m, 2|m będzie:
k(k-2)(k-4)...(k-m/2)
Zmiany k są jak najbardziej możliwe, zmiana k na k+2 polega na wyłączeniu z iloczynu wartości większej i zmodyfikowaniu sąsiednich wyrazów.
Okazało się, że ten sposób modyfikuje nie tylko a_i, oraz a_{i-1}, ale czasem i iloczyn mający jeden czynnik więcej.
Kiedy nauczyłem się przechodzić z k na k+2, zastanawiały mnie zmiany najmniej znaczącego składnika a_0 ze wzrostem k.
I zauważyłem, że współczynniki a_m, ... a_0 zachowują się jak cyfry, choć z zupełnie innymi zasadami przenoszenia, zaś iloczyny k...(k-i) pełnią rolę podstaw k^i.
Utworzył się w ten sposób nowy system liczbowy, chociaż nie wydaje się on pozycyjny - iloczyny trzeba zawsze zapisywać. Im większa wartość k, tym mniej składników, jak w standardowych systemach pozycyjnych niedziesiątkowych przy dużych podstawach.
A co ze współczynnikiem a_0? Jak systemach pozycyjnych przy p^k wartości tej reszty od pewnego miejsca zaczęły aproksymować przedziałami równanie logistyczne ax(b-x), tak tu takie zachowanie jest bardzo rzadkie. Przy dużych wartościach (trzech składnikach) kolejny przyrost to prosta kombinacja liniowa, o tyle o a_0 nie możemy niemal nic powiedzieć oprócz tego, że rzadko bywa skrajna. Silne regularności występują natomiast przy współczynnikach a_2, a_1.
Przykładowo, liczbę przedstawioną jako
N = 9 * 967 * 969 + 516 * 969 + 842
przekształcamy z k=969 na k=971 następująco:
pozycja 9*967*969 chwilowo bez zmian,
różnica 971-967=4, daje zmianę 9*4 dla a_1, czyli ten wspólczynnik oblicza się następująco:
516-4*9 = 480
Dodatni, więc a_2 pozostaje bez zmian.
Ale mamy 480*969, a powinniśmy mieć 480*971, różnica 2, kontynuujemy z a_0:
842-2*480 = -118, za mało
wykorzystujemy przeniesienie 1 z a_1, czyli 480-1 = 479, a dodajemy zwiększone k=971, czyli
842-2*480+971 = 853
Nowa postać dla k=971 wygląda:
N = 9 * 969 * 971 + 479 * 971 + 853
I takie przeniesienia są bardzo częste.
Czy zatem opłaca się trzymać wartości jako sumę iloczynów? Czy lepiej używać standardowych postaci systemów pozycyjnych? Są tu dodatkowe przekształcenia pozwalające wprowadzić nowe typy cech podzielności, niewiele więcej.
14 maja 2018
Liczby dziesiętne jako palindromy
Palindromy opisane dla systemu binarnego działają także dla odpowiednio dużych liczb dziesiętnych.
Okazuje się, że każdą liczbę większą niż 4 można w pewnym systemie zapisać jako palindrom długości 3.
Każdą liczbę większą niż 16 można w pewnym systemie zapisać jako palindrom długości 5, może być zarówno liczbą pierwszą jak i złożoną. Wynika to z faktu, że jest to mieszanka liczb względnie pierwszych (w binarnym: 17, 10, 4; oraz nwd(17,10,4)=1 )
Zatem to podejście nie nadaje się na faktoryzację.
Przykład palindromu wskazującego dzielniki wg wzoru:
(a, b, a) * (c, d, c) = (ac, ad+bc, 2ac+bd, ad+bc, ac)
8934053 = (63, 5459, 27904, 5459, 63)
I jest to jedyny wskazujący dzielniki w dziesiętnym o wartościach nieujemnych, gdyż chcąc uzyskać a, c dwucyfrowe mamy
(1653, -7600, 784, -7600, 1653).
Są też inne z których niewiele odczytamy, np. (3, 5, 88990, 5, 3), (873, 8, 1951, 8, 883).
Okazuje się, że każdą liczbę większą niż 4 można w pewnym systemie zapisać jako palindrom długości 3.
Każdą liczbę większą niż 16 można w pewnym systemie zapisać jako palindrom długości 5, może być zarówno liczbą pierwszą jak i złożoną. Wynika to z faktu, że jest to mieszanka liczb względnie pierwszych (w binarnym: 17, 10, 4; oraz nwd(17,10,4)=1 )
Zatem to podejście nie nadaje się na faktoryzację.
Przykład palindromu wskazującego dzielniki wg wzoru:
(a, b, a) * (c, d, c) = (ac, ad+bc, 2ac+bd, ad+bc, ac)
8934053 = (63, 5459, 27904, 5459, 63)
I jest to jedyny wskazujący dzielniki w dziesiętnym o wartościach nieujemnych, gdyż chcąc uzyskać a, c dwucyfrowe mamy
(1653, -7600, 784, -7600, 1653).
Są też inne z których niewiele odczytamy, np. (3, 5, 88990, 5, 3), (873, 8, 1951, 8, 883).
25 kwietnia 2018
Własność liczb złożonych
Liczby złożone można zapisać w postaci tożsamości:
2N = 2p*q
= (a-b)(a+b+1) = (a-b)*(a+b) + (a-b) = a^2 - b^2 + a - b
= a(a+1)-b(b+1)
Dla liczby nieparzystej N o dzielnikach nieparzystych czynniki (a-b), (a+b+1) mają różną parzystość.
Porównując ten wzór z szeregiem harmonicznym uzyskujemy, że 2N można przedstawić jako różnicę dwu sum skończonych szeregów harmonicznych, na które ogólny wzór jest
1+2+...+n = n(n+1)/2 .
Np. 2*8934053 = 8762*8763 - 7675*7676 =
sum _{0<i<8763} i - sum _{0<i<7676} i.
Ekstremalne przypadki są przy jak najmniejszych wartościach a~sqrt N, oraz b bliskim sqrt (a(a+1)-N).
Drugi ekstremalny przypadek jest przy a=N, b=N-1:
N(N+1) - (N-1)N = 2N
Oznaczmy funkcję r(N, a, b) daną wzorem:
r() = ( a(a+1) - 2N - b(b+1) )/2
Okazuje się, że funkcję r można ustawić w ciąg dla różnych możliwości (a,b) tak, by r była przedziałami monotoniczna, ograniczona przez 0 oraz b.
Ze względu na tożsamość
x(x+1) = 2x + (x-1)x
zmiana a, b o 1 powoduje zmianę r() o a, b odpowiednio.
Funkcja r() zeruje się, gdy a-b jest dzielnikiem N. Także kiedy r() dzieli b, rozkład a-b zawiera dzielnik N.
Na razie jest tu wiele niewiadomych. Na pewno tej postaci nie można jeszcze zastosować do algorytmu faktoryzacji, ale znajdowanie lokalnych minimów r() jest stosunkowo łatwe do przeprowadzenia, np. równaniem kwadratowym, metodą połowienia.
Sam algorytm wstępnie może wyglądać następująco:
a = sqrt (2N), b = sqrt( a(a+1)-2N ), r= ( a(a+1)-2N-b(b+1) )/2
while( a-b>1 ) {
a++; r+=a;
while( r>b-1 ) {
b++; r-=b;
}
if( 0==r ) return dzielnik a-b liczby N;
}
Potem w każdym kroku a i b się zwiększają prawie równolegle, b dogania a dla a=N. Gdy a-b malejąc osiągnie b, warto zmienić sposób działania - pętla wewnętrzna będzie się wykonywać rzadziej niż zewnętrzna.
Nieznana jest wartość stopu, gdyż podana pętla sprawdza te same wartości na różne sposoby. Mam podejrzenie, że wystarczy połowa sqrt(2N) przypadków przy podejściu siłowym. A kod jest niesamowicie prosty...
2N = 2p*q
= (a-b)(a+b+1) = (a-b)*(a+b) + (a-b) = a^2 - b^2 + a - b
= a(a+1)-b(b+1)
Dla liczby nieparzystej N o dzielnikach nieparzystych czynniki (a-b), (a+b+1) mają różną parzystość.
Porównując ten wzór z szeregiem harmonicznym uzyskujemy, że 2N można przedstawić jako różnicę dwu sum skończonych szeregów harmonicznych, na które ogólny wzór jest
1+2+...+n = n(n+1)/2 .
Np. 2*8934053 = 8762*8763 - 7675*7676 =
sum _{0<i<8763} i - sum _{0<i<7676} i.
Ekstremalne przypadki są przy jak najmniejszych wartościach a~sqrt N, oraz b bliskim sqrt (a(a+1)-N).
Drugi ekstremalny przypadek jest przy a=N, b=N-1:
N(N+1) - (N-1)N = 2N
Oznaczmy funkcję r(N, a, b) daną wzorem:
r() = ( a(a+1) - 2N - b(b+1) )/2
Okazuje się, że funkcję r można ustawić w ciąg dla różnych możliwości (a,b) tak, by r była przedziałami monotoniczna, ograniczona przez 0 oraz b.
Ze względu na tożsamość
x(x+1) = 2x + (x-1)x
zmiana a, b o 1 powoduje zmianę r() o a, b odpowiednio.
Funkcja r() zeruje się, gdy a-b jest dzielnikiem N. Także kiedy r() dzieli b, rozkład a-b zawiera dzielnik N.
Na razie jest tu wiele niewiadomych. Na pewno tej postaci nie można jeszcze zastosować do algorytmu faktoryzacji, ale znajdowanie lokalnych minimów r() jest stosunkowo łatwe do przeprowadzenia, np. równaniem kwadratowym, metodą połowienia.
Sam algorytm wstępnie może wyglądać następująco:
a = sqrt (2N), b = sqrt( a(a+1)-2N ), r= ( a(a+1)-2N-b(b+1) )/2
while( a-b>1 ) {
a++; r+=a;
while( r>b-1 ) {
b++; r-=b;
}
if( 0==r ) return dzielnik a-b liczby N;
}
Potem w każdym kroku a i b się zwiększają prawie równolegle, b dogania a dla a=N. Gdy a-b malejąc osiągnie b, warto zmienić sposób działania - pętla wewnętrzna będzie się wykonywać rzadziej niż zewnętrzna.
Nieznana jest wartość stopu, gdyż podana pętla sprawdza te same wartości na różne sposoby. Mam podejrzenie, że wystarczy połowa sqrt(2N) przypadków przy podejściu siłowym. A kod jest niesamowicie prosty...
26 marca 2018
Liczby binarne jako palindromy
Liczby binarne można zanurzyć w strukturę palindromu - listy wyglądającej identycznie wspak.
Do zanurzenia korzystamy z własności, którą ostatnio też często stosuję - na miejscu cyfr mogą stać dowolne wartości, jak reprezentacja Zeckendorfa liczb Fibonacciego.
Najlepiej to widać, kiedy zastosujemy cyfry systemu mającego nieskończenie wiele różnych cyfr, jaki opisywałem kilka miesięcy temu. Stosując system dziesiętny lub binarny nie widać tego od razu (cyfry zapisywane jako liczby nie wyglądają na palindromy).
Potęgę 2 zapisujemy jedną cyfrą, jest to palindrom długosci 1.
Dzielnik 3 liczby pozwala uzyskać palindrom o jeden dłuższy.
Pozostałe dzielniki pozwalają uzyskać palindrom o dwa dłuższy.
Twierdzenie. Dowolną liczbę binarną możemy przedstawić jako palindrom.
Dowód - konstrukcja.
Dla potęgi 2 nic więcej nie można zrobić. Liczba trzy jest już palindromem
3 = 11b = (1 1)
Dowolną liczbę nieparzystą N przedstawiamy np. jako trójkę:
(1 (N-5)/2 1) ,
gdyż 1*4+ (N-5)/2*2 + 1 = N.
Liczbę parzystą 2N zapisujemy jako palindrom liczby N podwajając jej współczynniki.
Przykłady takich palindromów:
37 = (1 16 1) = (1 0 5 0 1) = (1 2 0 2 1);
20 = (4 0 4);
51 = (3 0 0 0 3) = (17 17)
Widać, że reprezentacja nie jest jednoznaczna.
Struktura ta ma pewne ciekawe własności. Iloczyn dwu palindromów też jest palindromem:
(a b a) * (c d c) = (1)
(ac (ad+bc) (bd+2ac) (ad+bc) ac)
Wartości a, c są zawsze nieparzyste dla liczby N nieparzystej.
Schematy przekształceń palindromów wykorzystują zasady systemu binarnego, np.:
[+2 -3 -1 -3 +2],
po przetłumaczeniu na liczbę binarną polega na dodaniu 2*17=34 i odjęciu (3*5+2)*2 = 34.
Czy można to zastosować do rozkładu liczb? Niezbyt. Przedstawiając liczbę N jako przykładowy palindrom z twierdzenia (1 (N-5)/2 1) szukałem odpowiedniego iloczynu palindromów, z którego jestem w stanie rekursywnie wydobyć dzielniki. Doszedłem do wzorów dla odpowiednio dużych N:
N = 4k+1, wyrażenie
(-2+(N-17)/4 + x^2) / (2x+5)
ma rozwiązanie całkowite dla dzielników liczby N.
N = 4k+3, odpowiednie wyrażenie to
(-2+(N-27)/4 + x^2 - x) / (2x+5).
Jest to inna postać rozkładu metodą 'trial division'. Jedynym plusem są mniejsze dzielne, podzielność można rozdzielić na sumę stałej (rzędu N/4) i kwadratu zmiennej. Rekursja dla rozkładu ac zawiedzie. Dopasowanie właściwej postaci też jest żmudne (iloczyn na pozycji pierwszej, suma jego czynników na drugiej).
Do zanurzenia korzystamy z własności, którą ostatnio też często stosuję - na miejscu cyfr mogą stać dowolne wartości, jak reprezentacja Zeckendorfa liczb Fibonacciego.
Najlepiej to widać, kiedy zastosujemy cyfry systemu mającego nieskończenie wiele różnych cyfr, jaki opisywałem kilka miesięcy temu. Stosując system dziesiętny lub binarny nie widać tego od razu (cyfry zapisywane jako liczby nie wyglądają na palindromy).
Potęgę 2 zapisujemy jedną cyfrą, jest to palindrom długosci 1.
Dzielnik 3 liczby pozwala uzyskać palindrom o jeden dłuższy.
Pozostałe dzielniki pozwalają uzyskać palindrom o dwa dłuższy.
Twierdzenie. Dowolną liczbę binarną możemy przedstawić jako palindrom.
Dowód - konstrukcja.
Dla potęgi 2 nic więcej nie można zrobić. Liczba trzy jest już palindromem
3 = 11b = (1 1)
Dowolną liczbę nieparzystą N przedstawiamy np. jako trójkę:
(1 (N-5)/2 1) ,
gdyż 1*4+ (N-5)/2*2 + 1 = N.
Liczbę parzystą 2N zapisujemy jako palindrom liczby N podwajając jej współczynniki.
Przykłady takich palindromów:
37 = (1 16 1) = (1 0 5 0 1) = (1 2 0 2 1);
20 = (4 0 4);
51 = (3 0 0 0 3) = (17 17)
Widać, że reprezentacja nie jest jednoznaczna.
Struktura ta ma pewne ciekawe własności. Iloczyn dwu palindromów też jest palindromem:
(a b a) * (c d c) = (1)
(ac (ad+bc) (bd+2ac) (ad+bc) ac)
Wartości a, c są zawsze nieparzyste dla liczby N nieparzystej.
Schematy przekształceń palindromów wykorzystują zasady systemu binarnego, np.:
[+2 -3 -1 -3 +2],
po przetłumaczeniu na liczbę binarną polega na dodaniu 2*17=34 i odjęciu (3*5+2)*2 = 34.
Czy można to zastosować do rozkładu liczb? Niezbyt. Przedstawiając liczbę N jako przykładowy palindrom z twierdzenia (1 (N-5)/2 1) szukałem odpowiedniego iloczynu palindromów, z którego jestem w stanie rekursywnie wydobyć dzielniki. Doszedłem do wzorów dla odpowiednio dużych N:
N = 4k+1, wyrażenie
(-2+(N-17)/4 + x^2) / (2x+5)
ma rozwiązanie całkowite dla dzielników liczby N.
N = 4k+3, odpowiednie wyrażenie to
(-2+(N-27)/4 + x^2 - x) / (2x+5).
Jest to inna postać rozkładu metodą 'trial division'. Jedynym plusem są mniejsze dzielne, podzielność można rozdzielić na sumę stałej (rzędu N/4) i kwadratu zmiennej. Rekursja dla rozkładu ac zawiedzie. Dopasowanie właściwej postaci też jest żmudne (iloczyn na pozycji pierwszej, suma jego czynników na drugiej).
17 lutego 2018
Kolejna rodzina faktoryzacji, złożoność dochodzi do O(n log n)
Notacja Zeckendorfa używana przy liczbach Fibonacciego zasugerowała mi próbę wykorzystywania przesunięć reszt przy działaniach typu 19+3 = 12 + przesunięcie 10.
Kilka prób i powstał algorytm, w którym znów nie dzielimy, przynajmniej nie operatorem dzielenia. Dzielenie jednak występuje, lecz jest zaszyte bardzo specyficznie.
Jakie liczby najłatwiej nam dzielić? Takie, w których na miejscu cyfr występują tylko zera i dzielnik. Np.
7077707707070707070777770700007
jest podzielna przez 7, zaś wartość ilorazu to ta sama liczba, w której zastępujemy siódemki jedynkami.
W praktyce nie jest tak dobrze. występuje reszta. Resztę tę można przesuwać, i klasycznie przesuwa się ją do cyfry najmniej znaczącej. Cyfra ta rozrasta się, aż nadmiar należy wrócić do liczby rozkładanej. Można w tym celu posłużyć się dodatkową cyfrą binarną A, której ustawione bity sygnalizują daną wartość liczbową d.
Wtedy podczas algorytmu wykorzystamy równość:
d*A = (d+2)*A - 2A
odejmując podwojony bit A od reszty przechodząc z wartości d na (d+2).
Kiedy przystąpiłem do implementacji tego algorytmu, oceniłem, że lepiej będzie zmienić kolejność przesunięć do cyfry najbardziej znaczącej R.
I algorytm zmienił swoje możliwości, uprościł się likwidując cyfrę binarną A.
Algorytm teraz działa następująco:
liczbę N = n_m 2^m + ... + n_1*2 + n_0
zapisujemy w tablicy binarnej b bez najbardziej znaczącego bitu r=n_m. Dalej przekształcenia można zapisać:
for( d=3; d< sqrt N; d=d+2) {
v=0;
for( i=0; i<m; i++) {
if( b[i] ) v= v+(d-2);
if( 2|d ) b[i]=0; else { v = v-d; b[i]=1; }
v = v/2;
}
r = r+v;
while( r<0 ) { r= 2*r+b[m]*d; m--; }
if( r>d-1 ) {
if( ~(2|r) ) { b[m]=1; r=r-d; } else b[m]=0;
m++;
r = r/2;
}
if( 0==r ) return dzielniki d, A(binarnie)
if( 2*m< log N ) return liczba pierwsza
}
Algorytm sprawdza stałą krotność liczb na minutę (prawie, ma lekką tendecję przyspieszania, gdyż zakres [0..m] nieco drga zmniejszając m).
Ma złożoność arytmetyczną O(n log n). Cechuje się tłumieniem rozwoju reszt.
I jak na razie, jest bardzo szybki jak na dotychczasowe rozważania.
Przesunięcia nie powiedziały jeszcze ostatniego słowa. Podejrzewam, że wkrótce odsłonią mi coś nowego.
Kilka prób i powstał algorytm, w którym znów nie dzielimy, przynajmniej nie operatorem dzielenia. Dzielenie jednak występuje, lecz jest zaszyte bardzo specyficznie.
Jakie liczby najłatwiej nam dzielić? Takie, w których na miejscu cyfr występują tylko zera i dzielnik. Np.
7077707707070707070777770700007
jest podzielna przez 7, zaś wartość ilorazu to ta sama liczba, w której zastępujemy siódemki jedynkami.
W praktyce nie jest tak dobrze. występuje reszta. Resztę tę można przesuwać, i klasycznie przesuwa się ją do cyfry najmniej znaczącej. Cyfra ta rozrasta się, aż nadmiar należy wrócić do liczby rozkładanej. Można w tym celu posłużyć się dodatkową cyfrą binarną A, której ustawione bity sygnalizują daną wartość liczbową d.
Wtedy podczas algorytmu wykorzystamy równość:
d*A = (d+2)*A - 2A
odejmując podwojony bit A od reszty przechodząc z wartości d na (d+2).
Kiedy przystąpiłem do implementacji tego algorytmu, oceniłem, że lepiej będzie zmienić kolejność przesunięć do cyfry najbardziej znaczącej R.
I algorytm zmienił swoje możliwości, uprościł się likwidując cyfrę binarną A.
Algorytm teraz działa następująco:
liczbę N = n_m 2^m + ... + n_1*2 + n_0
zapisujemy w tablicy binarnej b bez najbardziej znaczącego bitu r=n_m. Dalej przekształcenia można zapisać:
for( d=3; d< sqrt N; d=d+2) {
v=0;
for( i=0; i<m; i++) {
if( b[i] ) v= v+(d-2);
if( 2|d ) b[i]=0; else { v = v-d; b[i]=1; }
v = v/2;
}
r = r+v;
while( r<0 ) { r= 2*r+b[m]*d; m--; }
if( r>d-1 ) {
if( ~(2|r) ) { b[m]=1; r=r-d; } else b[m]=0;
m++;
r = r/2;
}
if( 0==r ) return dzielniki d, A(binarnie)
if( 2*m< log N ) return liczba pierwsza
}
Algorytm sprawdza stałą krotność liczb na minutę (prawie, ma lekką tendecję przyspieszania, gdyż zakres [0..m] nieco drga zmniejszając m).
Ma złożoność arytmetyczną O(n log n). Cechuje się tłumieniem rozwoju reszt.
I jak na razie, jest bardzo szybki jak na dotychczasowe rozważania.
Przesunięcia nie powiedziały jeszcze ostatniego słowa. Podejrzewam, że wkrótce odsłonią mi coś nowego.
Subskrybuj:
Posty (Atom)