Tak podglądam sobie zachowanie liczb podczas konwersji. Chcę teraz podsumować główne spostrzeżenia.
Jeśli natrafimy na miejsce, gdzie dla podstawy nieparzystej mamy na pozycji jedności zero, mamy dzielnik. Z kolei, gdy dla podstawy parzystej mamy sumę cyfr równą dzielnikowi, albo naprzemienną sumę cyfr równą 0, mamy dzielnik na sąsiedniej pozycji.
Krotność obliczeń jest nie większa niż ta potęga dwójki i = 2^k, gdy i<=sqrt n < 2i.
Zatem przegląd zupełny może biec tylko po liczbach trój- oraz dwycyfrowych. Konwersja o 1. Cyfra setek przyjmuje wtedy jedną z czterech wartości: 0, 1, 2, 3. Małe liczby pierwsze mają silne ślady w tym przedziale.
Znalezienie dzielnika zamiast rozkładu całej liczby, sprowadza się do rozkładu podstaw systemów oraz obliczanie największego wspólnego dzielnika podstawy z cyfrą jedności. Podstawa nieparzysta odsiewa duże liczby, podstawa parzysta (można wyłączyć dwójki) odsiewa mniejsze liczby, m. in. pierwsze. Można zastosować sito modyfikując podstawę systemu, by sprawdzać kandydatów nie więcej niż raz.
Jeśli chcemy zmniejszać krotność sprawdzanych przypadków, dla podstaw parzystych zapis liczby jest w postaci:
[a, b+a, b+r] _p
przy podstawie p jest nieliniowy, ale zachowuje się na tyle gładko, że r jest przedziałami monotoniczne. Dzielnik towarzyszy jednej z dużych zmian wartości r.
I zapraszam na łowy! Dla jakiej podstawy dzielnik jednocyfrowy liczby staje się dwucyfrowy?
10 maja 2020
Inne spojrzenie na konwersję
Mamy dwa sposoby podejścia do konwersji, rekursywny, który najczęściej stosuję, oraz iteratywny, korzystający pośrednio z wzorów skróconego mnożenia typu (a+kb)^i.
Szukanie rozkładu to dla mnie jest już szukanie systemu, w którym cyfra najmniej znacząca, cyfra jedności jest zerem, albo suma cyfr jest wielokrotnością podstawy systemu. W obu przypadkach zmienia się krotność cyfr zapisu dzielników liczby.
Zapis może zmienić sposób patrzenia, oraz ujawnić nowe możliwości. I tak się stało niedawno.
Skoro liczbę złożoną można przedstawić jako [a, a]_p, to będę odejmował stałą wartość takiej postaci od liczby. Po drobnych kłopotach z zapisem, okazało się, że jest to przekształcenie iteracyjne konwersji.
Najpierw sposób. Mam liczbę w postaci ciągu cyfr w systemie pozycyjnym o podstawie p. Chcę zabrać równowartość cyfry najbardziej znaczącej.
Tworzę wielomian współczynników Newtona mnożonych przez kolejne potęgi dwójki, np.
[1, 12=2*6, 60=4*15, 160=8*20, 240=16*15, 192=32*6, 64]
oraz w liczbie n za pomocą przeniesień nadaję poszczególnym cyfrom wartości większe niż w wielomianie, np. z liczby n = [5, 0, 5, 2, 3, 1, 7] _p=11 tworzę:
[1, 36, 71, 163, 246, 192, 66]_11
Po odjęciu wielomianu po pozycjach mam wartość o mniejszej krotnosci cyfr (początkowe zero do zignorowania):
[0, 24, 11, 3, 6, 0, 2]
z którą postępujemy analogicznie. Kończymy gdy uzyskamy jedną cyfrę.
Odjęcie wartości wielomianu jest odjęciem wielokrotności potęgi 13. Początkowe cyfry (odejmowane) tworzą zapis cyfr systemu trynastkowego właśnie dzięki wielomianowi (11+2)^6 .
I tak powstał nowy zapis sposóbu konwersji, mający więcej obliczeń niż wersja rekursywna.
Jako wniosek, zauważam, że skoro suma cyfr ma być wielokrotnością podstawy, to dla liczby zapisanej w postaci potęg dwójki w miejscu cyfr poza cyfrą jedności, np. [8, 4, 2, 7]_ 31 nia ma szans na dzielniki bliskie 31, 62, 124 itd. przy podwajaniu podstawy. Bo przy konwersji p*2 suma cyfr maleje. Zaś dla dzielnika ma sięgać podstawy. Suma cyfr może wzrosnąć tylko podczas przeniesienia jedynki do cyfry mniej znaczącej, tu o połowę podstawy. Stąd dwa przeniesienia, i suma cyfr wzrasta powyżej podstawy systemu (podwojonemu).
Możemy nawet wzmocnić ograniczenie, by było tylko jedno przeniesienie i suma odpowiednio mała, by zigrorować szukanie dzielników w okolicy.
Uwaga - przeniesienia mogą się propagować, jak przy [7, 4, 4, 1]_p = [3, n+p/2, 2, 1]_2p.
Szukanie rozkładu to dla mnie jest już szukanie systemu, w którym cyfra najmniej znacząca, cyfra jedności jest zerem, albo suma cyfr jest wielokrotnością podstawy systemu. W obu przypadkach zmienia się krotność cyfr zapisu dzielników liczby.
Zapis może zmienić sposób patrzenia, oraz ujawnić nowe możliwości. I tak się stało niedawno.
Skoro liczbę złożoną można przedstawić jako [a, a]_p, to będę odejmował stałą wartość takiej postaci od liczby. Po drobnych kłopotach z zapisem, okazało się, że jest to przekształcenie iteracyjne konwersji.
Najpierw sposób. Mam liczbę w postaci ciągu cyfr w systemie pozycyjnym o podstawie p. Chcę zabrać równowartość cyfry najbardziej znaczącej.
Tworzę wielomian współczynników Newtona mnożonych przez kolejne potęgi dwójki, np.
[1, 12=2*6, 60=4*15, 160=8*20, 240=16*15, 192=32*6, 64]
oraz w liczbie n za pomocą przeniesień nadaję poszczególnym cyfrom wartości większe niż w wielomianie, np. z liczby n = [5, 0, 5, 2, 3, 1, 7] _p=11 tworzę:
[1, 36, 71, 163, 246, 192, 66]_11
Po odjęciu wielomianu po pozycjach mam wartość o mniejszej krotnosci cyfr (początkowe zero do zignorowania):
[0, 24, 11, 3, 6, 0, 2]
z którą postępujemy analogicznie. Kończymy gdy uzyskamy jedną cyfrę.
Odjęcie wartości wielomianu jest odjęciem wielokrotności potęgi 13. Początkowe cyfry (odejmowane) tworzą zapis cyfr systemu trynastkowego właśnie dzięki wielomianowi (11+2)^6 .
I tak powstał nowy zapis sposóbu konwersji, mający więcej obliczeń niż wersja rekursywna.
Jako wniosek, zauważam, że skoro suma cyfr ma być wielokrotnością podstawy, to dla liczby zapisanej w postaci potęg dwójki w miejscu cyfr poza cyfrą jedności, np. [8, 4, 2, 7]_ 31 nia ma szans na dzielniki bliskie 31, 62, 124 itd. przy podwajaniu podstawy. Bo przy konwersji p*2 suma cyfr maleje. Zaś dla dzielnika ma sięgać podstawy. Suma cyfr może wzrosnąć tylko podczas przeniesienia jedynki do cyfry mniej znaczącej, tu o połowę podstawy. Stąd dwa przeniesienia, i suma cyfr wzrasta powyżej podstawy systemu (podwojonemu).
Możemy nawet wzmocnić ograniczenie, by było tylko jedno przeniesienie i suma odpowiednio mała, by zigrorować szukanie dzielników w okolicy.
Uwaga - przeniesienia mogą się propagować, jak przy [7, 4, 4, 1]_p = [3, n+p/2, 2, 1]_2p.
21 kwietnia 2020
Przegląd zupełny w faktoryzacji mogący być stosowany współbieżnie
Łączę ostatnie pomysły, uzyskując działającą metodę rozkładu. Własności powodują, że przegląd zupełny zachowuje się jak współbieżny (wielowątkowy). Dlatego nie podam dokładnego algorytmu, lecz warunki.
Niech i będzie taką potęgą 2, by
2i <= sqrt n < 4i
Dzielników szukamy przeglądem zupełnym po potęgach dwójki 1<k<i w przedziale [2i, 4i). Każda taka potęga, np. k=2^3 wyznacza warstwę, która jest niezależna od pozostałych.
Co więcej, w tym przedziale występuje dokładnie jedna wartość 3*2^k, gdzie k=i/2, dwie wartości 5*2^k, 7*2^k, gdzie k=i/4 i tak dalej. W metodzie chodzimy po tych niezależnych warstwach, komunikując je wątkiem liczb pierwszych.
Opis ogólny metody
Liczba złożona n jest rozłożona na sumę dwu składników. Jeden ze składników stanowi warstwę związaną z nieujemną potęgą 2, czyli k.
n = k*a*p + c.
Sprawdzamy, kiedy p jest liczbą pierwszą, wtedy pytamy, czy reszta c jest też podzielna przez p, c=d*p. W takim przypadku mamy rozkład:
n = k*a*p + d*p = (k*a+d)*p
Wartość a jest ograniczona bardzo specyficznie, zmniejsza się ze wzrostem p w zakresie swojej warstwy przy stałym k do swojej połowy. Np. dla pewnej wartości przy inicjacji wartości a oraz c są stałe, np:
k * 21 490 565 976 844 * p + 10 378 130 574 991
koniec warstwy następuje, gdy a osiągnie 10 745 282 988 422. Równocześnie p osiąga potęgę 2.
Wartość p jest związana z k w ten sposób, że przy inicjacji jest potęgą 2 oraz p*k=2i, następnie jest zwiększana o 1, przebiega liczby nieparzyste do najbliższej potęgi 2, czyli jest ograniczenie p*k<4i, zaś całość k*a*p oscyluje wokół pierwiastka kwadratowego z n. Oznacza to, że c może przyjmować wartości dowolnego znaku, staramy się, by oscylowało wokół a, gdyż w szczególnym przypadku a=c też możemy natrafić na dzielnik n = k*a*p+a = (k*p+1)*a. Wartości k*p bywają bardzo duże, wprowadzone oscylacje dają nam pewność, że jesteśmy najbliżej potencjalnego dzielnika jak się da przy tym znaku c.
Możemy wykonywać obliczenia niemal równocześnie po warstwach z różnymi k.
W obrębie warstwy myślę stosować sito Eratostenesa oraz kopiec na trzymanie par (liczba, jej dzielnik), posortowany według liczb.
Wątek liczb pierwszych
Wątek ten komunikuje się z dowolną z warstw dla danego k, niszcząc je po wykorzystaniu.
Jego zadaniem jest wstawienie świeżo znalezionej (przysłanej z jakiejś warstwy) nowej liczby pierwszej do kopców w odpowiednich warstwach, podawanie zakresu minimalnej liczby pierwszej oraz zatrzymanie w przypadku znalezienia dzielnika albo wykrycia, że liczba n jest pierwsza.
Jeśli warstwa przyśle nowo wykrytą liczbę pierwszą q, stosujemy następujacą procedurę, szukamy wątku o największym k, w którym któraś z wartości p jest równa q, oraz dodajemy do kopca parę (q,q). Teraz szukamy warstwy zawierajacej iloczyn 3q, wstawiajac parę (3q, q). To nie musi być wątek z połową k, lecz z czwartą częścią k.
Teraz modyfikujemy wielokrotność q tak, by była nie większa niż p w inicjacji. W tym celu powinniśmy czasem dodać q. Dla wątku wielokrotność ta ma być nieparzysta, dodajemy mu parę ((s+1[+1])*q,q), jedna suma opcjonalnie, dla nieparzystości. Staramy się trzymać wielokrotność s*q za małą do umieszczenia w wątku.
Przykład, q=11:
Pierwsza odpowiednia warstwa powstała z p=8, odkładamy jej (11,11), następna warstwa z wartością nieparzystą to (33,11), a to jest warstwa z p=32. Pamiętamy jednak q=22. Mnożymy to przez 2 i dodajemy 11, uzyskując s*q=55, jest to ta sama warstwa z p=32. Dodajemy 11 uzyskując wartość większą niż 64, zatem warstwie z p=64 dodajemy ponownie 11 dodając do kopca parę (55+22, 11). Znów podwajamy s 2*55=110, ale 110+11 = 121 jest mniejsze niż p=128, to jest nasza nowa wartość s. Warstwie dla p=128 dokładamy element (121+22, 11). I tak dalej.
Jeśli warstwa przekaże, że skończyły się jej elementy, wątek liczb pierwszych podwaja zakres najmniejszej możliwej liczby pierwszej i każe warstwom sprawdzić swoje wartości. Wykorzystaną warstwę kasuje.
Jeśli skończą się elementy ostatniej, najdłuższej warstwy, z k=2, liczba jest pierwsza.
Działania na warstwach przy stałym k
Pierwszym działaniem po inicjacji jest przejscie na p nieparzyste. Wystarczy konwersja o 1: k*a'*(2p)+c' = k*a*(2p+1)+c. Uzyskamy p = 1+2^t dla pewnego t. Zapamiętujemy całe ostatnio obrabiane wyrażenie.
Wartość p jest albo liczbą pierwszą, albo złożoną. Sprawdzamy, czy ta wartość jest na szczycie kopca. Należy to powtarzać, gdyz jedna wartość może wystąpić tyle razy, ile ma różnych dzielników. Jeśli jej nie ma, lub jest to para (p,p), mamy duże szanse przypuszczać, że p jest liczbą pierwszą. Zwiększamy ją do najbliższej potęgi 2, z której wyciągamy pierwiastek kwadratowy i porównujemy z zakresem minimalnej liczby pierwszej wątku liczb pierwszych. I tak jeśli zakresem tym jest 8, a my mamy wartość p nieparzystą mniejszą niż 64, mamy do czynienia z liczbą pierwszą. Innym sposobem jest spierwiastkowanie, ale nie znajdujemy liczb pierwszych w porządku liniowym. Ta wartość wtedy czeka, a my możemy spokojnie zająć się kolejną, korzystając z kopii jej współczynników.
Jeśli wartość jest poza zakresem minimalnej liczby pierwszej, musimy poczekać, aż wątek liczb pierwszych go zwiększy. Wtedy moze okazać się, że liczba jest pierwsza, wtedy zwracamy ją wątkowi liczb pierwszych jako liczbę pierwszą.
Zarazem uruchamiamy procedurę sprawdzajacą, czy wartość c jest wielokrotnoscią liczby p. Jeżeli trzymam c w systemie o podstawie p, jest to po prostu porównanie najmniej znaczącej cyfry c z p w warstwie o największym k. W pozostałych warstwach należy sprawdzać podzielność bardziej standardowo.
Ale wąŧek liczb pierwszych może wprowadzić nową wartość większą niż aktualnie obsługiwana. Oznacza to, że oczekująca wartość m jest złożona, znamy jej dzielnik, więc wprowadzamy ją do obróbki jak liczbę złożoną.
Liczbę złożoną m o znanych dzielnikach rozkładamy. Może wtedy pojawić się dodatkowy dzielnik, który jest przesyłany jako nowy wątkowi liczb pierwszych.
Odkładamy na kopiec kolejne liczby podzielne przez q, (m-2q, q).
Mamy liczbę pierwszą p oraz przyrost w, jaki nas dzieli od ostatnio obrabianego wyrażenia p'. Liczba w jest parzystą.
Przystępujemy do konwersji:
k*a'*(p-w)+c' = k*a*p+c
gdzie najczęściej w=2. W później jednak możemy mieć często przyrost będący różnicą między kolejnymi liczbami pierwszymi.
Najpierw należy obliczyć przyrosty Delta a oraz Delta c
k*a*w = k* Delta a * p + Delta c
a następnie odjąć te przyrosty od zapamiętanego wyrażenia. Z Delta a nie ma kłopotu, jest to zwykłe a'*w z wyzerowaną cyfrę najmniej znaczącą.
Jednak Delta c wymaga nieco zachodu. Jeśli a'<c', odejmiemy iloczyn k oraz cyfry najmniej znaczącej a'*w od c'. Jeśli jednak a'>c', skorzystamy z własności systemu niedziesiątkowego, oraz dodamy dodatkowo k*p, zabierając jedynkę z a. W ten sposób zamiast zmniejszać c', zwiększamy je.
Przykłady
Możemy liczyć dziesiętnie, jak w tym przykładzie z p'=17 na p=19:
k*a'*(p-2) + c' =
n = 4 398 046 511 104 * 20 226 415 037 029 * 17 + 58 756 642 197 135
przyrosty:
4 398 046 511 104 * 20 226 415 037 029 * 2 =
4 398 046 511 104 * (2 129 096 319 686 * 19 + 5) =
4 398 046 511 104 * 2 129 096 319 686 * 19 + 105 553 116 266 496 =
k * Delta a * p + Delta c
oraz ich odejmowanie od a', c', gdyż a'<c' (20... < 58...):
20 226 415 037 029 - 2 129 096 319 686 = 18 097 318 717 343
58 756 642 197 135 - 105 553 116 266 496 = - 46 796 474 069 361
nowa postać
n = 4 398 046 511 104 * 18 097 318 717 343 * 19 - 46 796 474 069 361
stąd wyznaczamy, że 19 nie dzieli n, bo 46 796 474 069 361 = 1 (mod 19)
Jednak wolę systemy niedziesiątkowe, gdyż dla większych wartości mamy lepiej widoczne działania (separator 'cyfr' to przecinek, dopuszczam 'ujemne'). Najpierw zapisuję wszystkie współczynniki przy podstawie p (3 dodatkowe proste konwersje:
k * a' * (p-2) + c' =
n = 1022, 2056, 1018 * 311, 3962, 172, 1680 * 4097 + 874, 1430, 3799, 918
przyrosty (wartość 1022, 2056, 1018 to duża potega 2):
1022, 2056, 1018 * (311, 3962, 172, 1680 * 2) =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 1022, 2056, 1018 * 3360 =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 838, 643, 2179, 1914
nowa postać (znów a'<c'):
n = 1022, 2056, 1018 * 311, 3340, -7752, 1336 * 1, 0 + 36, 787, 1620, -996
oraz sprawdzamy podzielność -996 = 3103 (mod 4099) z 4099. Od razu widać, że liczba n jest niepodzielna przez liczbę pierwszą 4099.
Ale przechodząc na 4101 mamy a'>c', czyli oprócz odejmowania wyznaczonych przyrostów dodamy przekonwertowaną na system 4101 liczbę 1022, 2056, 1018 z systemu o podstawie 4099 pomnożoną przez 4101, by zwiększyć c.
już dla p=4099 działamy na liczbach co najwyżej czterocyfrowych, a dalej mamy jeszcze mniej cyfr, przez co mamy coraz mniej działań. I konwersje są coraz prostsze. Najwięcej przypadków jest dla małych k, najwiecej obliczeń dla dużych.
Inne własności, badajac 65 = 5 * 13 i znając zakres od warstwy k=2^45 (czyli liczbę pierwszą 3 i minimalny zakres 4) wnioskujemy, że 13 < 4^2 też jest pierwsza. Wartość 13 jest jedną z ostatnich sprawdzanych w swojej warstwie (9, 11, 13, 15).
Można przechodzić szybciej, np. z p'=263 na 267, szukając przyrostów iloczynem k*a'*4.
Przebieg.
Inicjacja, mamy w każdej warstwie wyrażenie na n, w którym p jest postaci p=1+2^t dla odpowiedniego t, czyli: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025,...
kopce puste. Liczymy po jednym elemencie każdej warstwy.
Sprawdzamy liczbę pierwszą 3, do kopca każdej warstwy odkładamy najmniejszą parę liczby podzielnej przez 3 większą niż potęga 2^t. Kasujemy pierwszą warstwę.
Wartości 9, 33, 129, 513 są w kopcu. Liczby mniejsze niż 4^2 nie będące w kopcach są pierwsze. Wartość złożona 15 jeszcze nie jest w kopcu, ale pojawi się tam podczas obsługi wątku p=9.
Wartość 5 nie jest w kopcu, jest pierwsza, kopce powiększają się o tę wartość.
Wartość 9, byłaby zignorowana, ale mamy wyrażenie dla niej z inicjacji. Dalej w takim przypadku tylko zwiększamy przyrost w o 2. Ale do kopca odkładamy wartość (9+6,3) czyli (15,3). Teraz wszystkie liczby złożone nieparzyste mniejsze niz 16 są w kopcach.
Wartości 17, 257 czekają, na tym etapie nie wiemy, czy są pierwsze. Sprawdzamy, czy ich potrojenie mieści się w ograniczeniu warstwy i ewentualnie odkładamy do kopca.
Wartości 33=3*11, 65=5*13 wyznaczają nowe liczby pierwsze. Wartość 513 = 3^3*57 czeka na możliwość stwierdzenia, czy 57 jest pierwsza (wymaga skasowania warstwy z p=4). Sprawdzana podzielność c przez 11, 13.
Podobnie 1025.
Nowy przebieg po warstwach.
Wartość 5+2=7 nie jest w kopcu, jest pierwsza. Warstwa kasowana, zakres minimalnej liczby pierwszej zwiększa się do 8^2=64.
Wartość 9+2=11 pierwsza, bo w kopcu jest (11,11). Podzielność jest sprawdzana w wartwie 33, tu można zignorować.
Wartość 17+2 = 19. Wynik z warstwy 7 wskazuje, że 17 jest pierwsza. Ale rozpatrywana 19 też jest pierwsza. Odkładamy ich nieparzyste wielokrotnosci do kopców w obrębie ograniczeń warstwy, czyli w tej warstwie już nic.
Wartość 35 = 5*7 ignorujemy tylko wstawiając do kopca pary (45,5), (49,7), Są w tej warstwie. Mamy w kopcu dwie pary (45,3) oraz (45,5). Może zrobić listę (45, [3,5])?
Wartość 67 jest pierwsza. Wiadomo, co... Dla kolejnych dwu wartości 131, 259 podobnie.
Wartość 515. Teraz już wiemy, co z 57 z 513 (pierwsza). Testujemy podzielność. W przypadku liczby złożonej czekamy na dalsze informacje. Obrabiamy 515.
... I tak dalej...
Niech i będzie taką potęgą 2, by
2i <= sqrt n < 4i
Dzielników szukamy przeglądem zupełnym po potęgach dwójki 1<k<i w przedziale [2i, 4i). Każda taka potęga, np. k=2^3 wyznacza warstwę, która jest niezależna od pozostałych.
Co więcej, w tym przedziale występuje dokładnie jedna wartość 3*2^k, gdzie k=i/2, dwie wartości 5*2^k, 7*2^k, gdzie k=i/4 i tak dalej. W metodzie chodzimy po tych niezależnych warstwach, komunikując je wątkiem liczb pierwszych.
Opis ogólny metody
Liczba złożona n jest rozłożona na sumę dwu składników. Jeden ze składników stanowi warstwę związaną z nieujemną potęgą 2, czyli k.
n = k*a*p + c.
Sprawdzamy, kiedy p jest liczbą pierwszą, wtedy pytamy, czy reszta c jest też podzielna przez p, c=d*p. W takim przypadku mamy rozkład:
n = k*a*p + d*p = (k*a+d)*p
Wartość a jest ograniczona bardzo specyficznie, zmniejsza się ze wzrostem p w zakresie swojej warstwy przy stałym k do swojej połowy. Np. dla pewnej wartości przy inicjacji wartości a oraz c są stałe, np:
k * 21 490 565 976 844 * p + 10 378 130 574 991
koniec warstwy następuje, gdy a osiągnie 10 745 282 988 422. Równocześnie p osiąga potęgę 2.
Wartość p jest związana z k w ten sposób, że przy inicjacji jest potęgą 2 oraz p*k=2i, następnie jest zwiększana o 1, przebiega liczby nieparzyste do najbliższej potęgi 2, czyli jest ograniczenie p*k<4i, zaś całość k*a*p oscyluje wokół pierwiastka kwadratowego z n. Oznacza to, że c może przyjmować wartości dowolnego znaku, staramy się, by oscylowało wokół a, gdyż w szczególnym przypadku a=c też możemy natrafić na dzielnik n = k*a*p+a = (k*p+1)*a. Wartości k*p bywają bardzo duże, wprowadzone oscylacje dają nam pewność, że jesteśmy najbliżej potencjalnego dzielnika jak się da przy tym znaku c.
Możemy wykonywać obliczenia niemal równocześnie po warstwach z różnymi k.
W obrębie warstwy myślę stosować sito Eratostenesa oraz kopiec na trzymanie par (liczba, jej dzielnik), posortowany według liczb.
Wątek liczb pierwszych
Wątek ten komunikuje się z dowolną z warstw dla danego k, niszcząc je po wykorzystaniu.
Jego zadaniem jest wstawienie świeżo znalezionej (przysłanej z jakiejś warstwy) nowej liczby pierwszej do kopców w odpowiednich warstwach, podawanie zakresu minimalnej liczby pierwszej oraz zatrzymanie w przypadku znalezienia dzielnika albo wykrycia, że liczba n jest pierwsza.
Jeśli warstwa przyśle nowo wykrytą liczbę pierwszą q, stosujemy następujacą procedurę, szukamy wątku o największym k, w którym któraś z wartości p jest równa q, oraz dodajemy do kopca parę (q,q). Teraz szukamy warstwy zawierajacej iloczyn 3q, wstawiajac parę (3q, q). To nie musi być wątek z połową k, lecz z czwartą częścią k.
Teraz modyfikujemy wielokrotność q tak, by była nie większa niż p w inicjacji. W tym celu powinniśmy czasem dodać q. Dla wątku wielokrotność ta ma być nieparzysta, dodajemy mu parę ((s+1[+1])*q,q), jedna suma opcjonalnie, dla nieparzystości. Staramy się trzymać wielokrotność s*q za małą do umieszczenia w wątku.
Przykład, q=11:
Pierwsza odpowiednia warstwa powstała z p=8, odkładamy jej (11,11), następna warstwa z wartością nieparzystą to (33,11), a to jest warstwa z p=32. Pamiętamy jednak q=22. Mnożymy to przez 2 i dodajemy 11, uzyskując s*q=55, jest to ta sama warstwa z p=32. Dodajemy 11 uzyskując wartość większą niż 64, zatem warstwie z p=64 dodajemy ponownie 11 dodając do kopca parę (55+22, 11). Znów podwajamy s 2*55=110, ale 110+11 = 121 jest mniejsze niż p=128, to jest nasza nowa wartość s. Warstwie dla p=128 dokładamy element (121+22, 11). I tak dalej.
Jeśli warstwa przekaże, że skończyły się jej elementy, wątek liczb pierwszych podwaja zakres najmniejszej możliwej liczby pierwszej i każe warstwom sprawdzić swoje wartości. Wykorzystaną warstwę kasuje.
Jeśli skończą się elementy ostatniej, najdłuższej warstwy, z k=2, liczba jest pierwsza.
Działania na warstwach przy stałym k
Pierwszym działaniem po inicjacji jest przejscie na p nieparzyste. Wystarczy konwersja o 1: k*a'*(2p)+c' = k*a*(2p+1)+c. Uzyskamy p = 1+2^t dla pewnego t. Zapamiętujemy całe ostatnio obrabiane wyrażenie.
Wartość p jest albo liczbą pierwszą, albo złożoną. Sprawdzamy, czy ta wartość jest na szczycie kopca. Należy to powtarzać, gdyz jedna wartość może wystąpić tyle razy, ile ma różnych dzielników. Jeśli jej nie ma, lub jest to para (p,p), mamy duże szanse przypuszczać, że p jest liczbą pierwszą. Zwiększamy ją do najbliższej potęgi 2, z której wyciągamy pierwiastek kwadratowy i porównujemy z zakresem minimalnej liczby pierwszej wątku liczb pierwszych. I tak jeśli zakresem tym jest 8, a my mamy wartość p nieparzystą mniejszą niż 64, mamy do czynienia z liczbą pierwszą. Innym sposobem jest spierwiastkowanie, ale nie znajdujemy liczb pierwszych w porządku liniowym. Ta wartość wtedy czeka, a my możemy spokojnie zająć się kolejną, korzystając z kopii jej współczynników.
Jeśli wartość jest poza zakresem minimalnej liczby pierwszej, musimy poczekać, aż wątek liczb pierwszych go zwiększy. Wtedy moze okazać się, że liczba jest pierwsza, wtedy zwracamy ją wątkowi liczb pierwszych jako liczbę pierwszą.
Zarazem uruchamiamy procedurę sprawdzajacą, czy wartość c jest wielokrotnoscią liczby p. Jeżeli trzymam c w systemie o podstawie p, jest to po prostu porównanie najmniej znaczącej cyfry c z p w warstwie o największym k. W pozostałych warstwach należy sprawdzać podzielność bardziej standardowo.
Ale wąŧek liczb pierwszych może wprowadzić nową wartość większą niż aktualnie obsługiwana. Oznacza to, że oczekująca wartość m jest złożona, znamy jej dzielnik, więc wprowadzamy ją do obróbki jak liczbę złożoną.
Liczbę złożoną m o znanych dzielnikach rozkładamy. Może wtedy pojawić się dodatkowy dzielnik, który jest przesyłany jako nowy wątkowi liczb pierwszych.
Odkładamy na kopiec kolejne liczby podzielne przez q, (m-2q, q).
Mamy liczbę pierwszą p oraz przyrost w, jaki nas dzieli od ostatnio obrabianego wyrażenia p'. Liczba w jest parzystą.
Przystępujemy do konwersji:
k*a'*(p-w)+c' = k*a*p+c
gdzie najczęściej w=2. W później jednak możemy mieć często przyrost będący różnicą między kolejnymi liczbami pierwszymi.
Najpierw należy obliczyć przyrosty Delta a oraz Delta c
k*a*w = k* Delta a * p + Delta c
a następnie odjąć te przyrosty od zapamiętanego wyrażenia. Z Delta a nie ma kłopotu, jest to zwykłe a'*w z wyzerowaną cyfrę najmniej znaczącą.
Jednak Delta c wymaga nieco zachodu. Jeśli a'<c', odejmiemy iloczyn k oraz cyfry najmniej znaczącej a'*w od c'. Jeśli jednak a'>c', skorzystamy z własności systemu niedziesiątkowego, oraz dodamy dodatkowo k*p, zabierając jedynkę z a. W ten sposób zamiast zmniejszać c', zwiększamy je.
Przykłady
Możemy liczyć dziesiętnie, jak w tym przykładzie z p'=17 na p=19:
k*a'*(p-2) + c' =
n = 4 398 046 511 104 * 20 226 415 037 029 * 17 + 58 756 642 197 135
przyrosty:
4 398 046 511 104 * 20 226 415 037 029 * 2 =
4 398 046 511 104 * (2 129 096 319 686 * 19 + 5) =
4 398 046 511 104 * 2 129 096 319 686 * 19 + 105 553 116 266 496 =
k * Delta a * p + Delta c
oraz ich odejmowanie od a', c', gdyż a'<c' (20... < 58...):
20 226 415 037 029 - 2 129 096 319 686 = 18 097 318 717 343
58 756 642 197 135 - 105 553 116 266 496 = - 46 796 474 069 361
nowa postać
n = 4 398 046 511 104 * 18 097 318 717 343 * 19 - 46 796 474 069 361
stąd wyznaczamy, że 19 nie dzieli n, bo 46 796 474 069 361 = 1 (mod 19)
Jednak wolę systemy niedziesiątkowe, gdyż dla większych wartości mamy lepiej widoczne działania (separator 'cyfr' to przecinek, dopuszczam 'ujemne'). Najpierw zapisuję wszystkie współczynniki przy podstawie p (3 dodatkowe proste konwersje:
k * a' * (p-2) + c' =
n = 1022, 2056, 1018 * 311, 3962, 172, 1680 * 4097 + 874, 1430, 3799, 918
przyrosty (wartość 1022, 2056, 1018 to duża potega 2):
1022, 2056, 1018 * (311, 3962, 172, 1680 * 2) =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 1022, 2056, 1018 * 3360 =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 838, 643, 2179, 1914
nowa postać (znów a'<c'):
n = 1022, 2056, 1018 * 311, 3340, -7752, 1336 * 1, 0 + 36, 787, 1620, -996
oraz sprawdzamy podzielność -996 = 3103 (mod 4099) z 4099. Od razu widać, że liczba n jest niepodzielna przez liczbę pierwszą 4099.
Ale przechodząc na 4101 mamy a'>c', czyli oprócz odejmowania wyznaczonych przyrostów dodamy przekonwertowaną na system 4101 liczbę 1022, 2056, 1018 z systemu o podstawie 4099 pomnożoną przez 4101, by zwiększyć c.
już dla p=4099 działamy na liczbach co najwyżej czterocyfrowych, a dalej mamy jeszcze mniej cyfr, przez co mamy coraz mniej działań. I konwersje są coraz prostsze. Najwięcej przypadków jest dla małych k, najwiecej obliczeń dla dużych.
Inne własności, badajac 65 = 5 * 13 i znając zakres od warstwy k=2^45 (czyli liczbę pierwszą 3 i minimalny zakres 4) wnioskujemy, że 13 < 4^2 też jest pierwsza. Wartość 13 jest jedną z ostatnich sprawdzanych w swojej warstwie (9, 11, 13, 15).
Można przechodzić szybciej, np. z p'=263 na 267, szukając przyrostów iloczynem k*a'*4.
Przebieg.
Inicjacja, mamy w każdej warstwie wyrażenie na n, w którym p jest postaci p=1+2^t dla odpowiedniego t, czyli: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025,...
kopce puste. Liczymy po jednym elemencie każdej warstwy.
Sprawdzamy liczbę pierwszą 3, do kopca każdej warstwy odkładamy najmniejszą parę liczby podzielnej przez 3 większą niż potęga 2^t. Kasujemy pierwszą warstwę.
Wartości 9, 33, 129, 513 są w kopcu. Liczby mniejsze niż 4^2 nie będące w kopcach są pierwsze. Wartość złożona 15 jeszcze nie jest w kopcu, ale pojawi się tam podczas obsługi wątku p=9.
Wartość 5 nie jest w kopcu, jest pierwsza, kopce powiększają się o tę wartość.
Wartość 9, byłaby zignorowana, ale mamy wyrażenie dla niej z inicjacji. Dalej w takim przypadku tylko zwiększamy przyrost w o 2. Ale do kopca odkładamy wartość (9+6,3) czyli (15,3). Teraz wszystkie liczby złożone nieparzyste mniejsze niz 16 są w kopcach.
Wartości 17, 257 czekają, na tym etapie nie wiemy, czy są pierwsze. Sprawdzamy, czy ich potrojenie mieści się w ograniczeniu warstwy i ewentualnie odkładamy do kopca.
Wartości 33=3*11, 65=5*13 wyznaczają nowe liczby pierwsze. Wartość 513 = 3^3*57 czeka na możliwość stwierdzenia, czy 57 jest pierwsza (wymaga skasowania warstwy z p=4). Sprawdzana podzielność c przez 11, 13.
Podobnie 1025.
Nowy przebieg po warstwach.
Wartość 5+2=7 nie jest w kopcu, jest pierwsza. Warstwa kasowana, zakres minimalnej liczby pierwszej zwiększa się do 8^2=64.
Wartość 9+2=11 pierwsza, bo w kopcu jest (11,11). Podzielność jest sprawdzana w wartwie 33, tu można zignorować.
Wartość 17+2 = 19. Wynik z warstwy 7 wskazuje, że 17 jest pierwsza. Ale rozpatrywana 19 też jest pierwsza. Odkładamy ich nieparzyste wielokrotnosci do kopców w obrębie ograniczeń warstwy, czyli w tej warstwie już nic.
Wartość 35 = 5*7 ignorujemy tylko wstawiając do kopca pary (45,5), (49,7), Są w tej warstwie. Mamy w kopcu dwie pary (45,3) oraz (45,5). Może zrobić listę (45, [3,5])?
Wartość 67 jest pierwsza. Wiadomo, co... Dla kolejnych dwu wartości 131, 259 podobnie.
Wartość 515. Teraz już wiemy, co z 57 z 513 (pierwsza). Testujemy podzielność. W przypadku liczby złożonej czekamy na dalsze informacje. Obrabiamy 515.
... I tak dalej...
08 marca 2020
Faktoryzacja z podstawy systemu, kolejna własność
Przyglądając się uzyskanym wartościom widzę, że nie muszę się ograniczać do nieujemnych b, c w niezmienniku
(d+b)*d+c = n
Liczba n jest wtedy dwucyfrowa, ale dzięki ujemnemu b jest zapisywana jako trójcyfrowa.
Przesunięcie to pozwala wyeliminować obliczanie kolejnych pierwiastków z liczby rozkładanej. Wystarczy jeden, zaś rozpatrywany przedział to potęga dwójki
2^k <= sqrt n < 3*2^k
W tym przedziale mozemy posługiwać się potęgami dwójki, by wyznaczyć tablicę małych liczb pierwszych, by je wyeliminować.Po prostu przechodzimy po wartościach a*2^j, gdzie j>=k/2 szukając liczb pierwszych jak w sicie Eratostenesa. Liczby te łączymy z ich wielokrotnościami jak najbliższymi skrajnej potęgi 2^k, a potem przegląd zupełny.
Reszta jak poprzednio. Znając dzielniki d mniejsze niż sqrt d, wyłączamy je uzyskując 1 lub liczbę pierwszą. Tą prównujemy z c. Jeśli wspólny dzielnik c i którejś z liczb pierwszych jest większy niż 1, jest to dzielnik liczby rozkładanej.
(d+b)*d+c = n
Liczba n jest wtedy dwucyfrowa, ale dzięki ujemnemu b jest zapisywana jako trójcyfrowa.
Przesunięcie to pozwala wyeliminować obliczanie kolejnych pierwiastków z liczby rozkładanej. Wystarczy jeden, zaś rozpatrywany przedział to potęga dwójki
2^k <= sqrt n < 3*2^k
W tym przedziale mozemy posługiwać się potęgami dwójki, by wyznaczyć tablicę małych liczb pierwszych, by je wyeliminować.Po prostu przechodzimy po wartościach a*2^j, gdzie j>=k/2 szukając liczb pierwszych jak w sicie Eratostenesa. Liczby te łączymy z ich wielokrotnościami jak najbliższymi skrajnej potęgi 2^k, a potem przegląd zupełny.
Reszta jak poprzednio. Znając dzielniki d mniejsze niż sqrt d, wyłączamy je uzyskując 1 lub liczbę pierwszą. Tą prównujemy z c. Jeśli wspólny dzielnik c i którejś z liczb pierwszych jest większy niż 1, jest to dzielnik liczby rozkładanej.
23 stycznia 2020
Faktoryzacja z podstawy systemu, przygotowanie do implementacji
Przejrzałem wręcz, co się dzieje, gdy najpierw szukamy postaci kanonicznej podstawy systemu, a z jego pomocą rozkładu liczby.
Założenia:
- pamiętać jak najmniej; wymagana jest jednak znajomość wszystkich liczb pierwszych mniejszych niż pierwiastek czwartego stopnia z liczby rozkładanej n. Wystarczy zapamiętać parę, na którą składają się dzielnik i jego odpowiednia wielokrotność;
- każda liczba pierwsza jest testowana dokładnie raz.
Drugi z warunków w pierwszej wersji sugerował zapamiętanie dodatkowych przedziałów, ale bliższe obserwacje wskazały, że nie są one potrzebne. Są niezbędne z kolei, kiedy chcemy sprawdzić dzielnik jak nakszybciej, zaraz przy jego pierwszym pojawieniu się, nie czekając na odpowiednią wartość.
Jeśli poczekamy, liczby pierwsze będą się spokojnie ujawniać wielokrotnie, a będziemy badać tylko występujące przy potęgach dwójki.
Znowu mamy dwa kierunki przeglądu zupełnego. Od pierwiastka kwadratowego z liczby rozkładanej n do połowy tej liczby, lub na odwrót.
Przy pierwiastku kwadratowym niezmiennik
n = (a+b)*a + c
ma wartości a=sqrt n; b równe 0, 1 albo 2; c jest na moduł ograniczane przez a. Zmiana a o 1 powoduje w tym zakresie zmianę b o 2,
np. 8934053 = (2988+2)*2988-67.
Przy połowie pierwiastka kwadratowego c dalej jest ograniczone na moduł przez a, a = 1/2 sqrt n, zaś b jest bliskie 3/2 sqrt n. Zmianie a o 1 tutaj towarzyszy zmiana b o 4:
np. 8934053 = (1494+4486)*1494-67.
Modyfikacje są na tyle małe, że robimy mały błąd nadając zazwyczaj a~3*b dla szacunku c jak najbliższego zeru. Potem korekta postaci: b+1 oznacza c-a.
Pierwiastek czwartego stopnia z 8934053 to 54. Czyli do rozkładu potrzebujemy zapamiętywać wielokrotności następujących liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 37, 41, 43, 47, 53. Warto mieć je posortowane po wartościach, wystarczy jedna wartość na jedną liczbę pierwszą jak najbliżej pobieranej do testu.
Zaczynając od pierwiastka kwadratowego, zapisujemy (2988; 2), (2988; 3), co można złączyć w (2988; 2, 3); (2985; 5), (2982; 7), itd.
Wbrew początkowym oczekiwaniom, nie musimy znać rozkładu kanonicznego, nawet tej jego części korzystajacej z wymienionych liczb pierwszych. Wystarczy nam liczba oraz jej dzielniki.
Algorytm:
1. k = 1+sqrt n ;
2. pętla, bierzemy wartość o 1 mniejszą (k--);
3. jeśli liczba nie jest zapamiętana, sprawdzamy ją pod kątem pierwszości
jeśli liczba jest zapamiętana, sprawdzamy, czy ma dzielnik większy od 2, jeśli nie, sprawdzamy liczbę pod kątem pierwszości;
4. liczba złożona (k, p) wskazuje, że liczba (k-p, p) też jest złożona, zapamiętujemy ją (dla każdej czynnika pierwszego p), przy czym, jeśli dana wartość k-p już jest zapamiętana, tylko dopisujemy doń kolejny dzielnik;
5. jeśli k<1/2 sqrt n, liczba jest pierwsza; w przeciwnym przypadku wracamy do 2;
Sprawdzenie pod kątem pierwszości, trafiają tu liczby pierwsze oraz postaci k=2^i*p, gdzie p jest pierwsza.
Obliczamy wartość c niezmiennika n=(k+b)*k+c, oraz sprawdzamy |c|%p. Podzielność oznacza znalezienie dzielnika p|n (bo p|k). Dla większości wartości sprowadza się do porównania takiego jak 157<881. Rzadko kiedy trzeba dzielić modulo. Oczywiście wtedy należy zakończyć algorytm.
Dlaczego to działa.
Potęgi dwójki dzielą nam przedział (1, sqrt n) na rozłączne przedziały
(2^{-i}*n, 2^{1-i}*n);
każda liczba pierwsza trafia do dokładnie jednego z nich.
Jeśli dopuścimy inne liczby pierwsze lub rozkład kanoniczny, zakresy przedziałów będą często miały części wspólne. Owszem, początkowo szybko będziemy sprawdzać i eliminować liczby pierwsze, korzystając z dzieleń. Choć wtedy część liczb będzie sprawdzanych wielokrotnie, o ile ich nie zapamiętamy. I tak musimy przejrzeć cały przedział. W dotatku mamy nadmiarowe dzielenia przy szukaniu liczb pierwszych większych niż zapamiętane, gdyż nie znamy wykladników potęg tych liczb pierwszych w rozkładach.
Założenia:
- pamiętać jak najmniej; wymagana jest jednak znajomość wszystkich liczb pierwszych mniejszych niż pierwiastek czwartego stopnia z liczby rozkładanej n. Wystarczy zapamiętać parę, na którą składają się dzielnik i jego odpowiednia wielokrotność;
- każda liczba pierwsza jest testowana dokładnie raz.
Drugi z warunków w pierwszej wersji sugerował zapamiętanie dodatkowych przedziałów, ale bliższe obserwacje wskazały, że nie są one potrzebne. Są niezbędne z kolei, kiedy chcemy sprawdzić dzielnik jak nakszybciej, zaraz przy jego pierwszym pojawieniu się, nie czekając na odpowiednią wartość.
Jeśli poczekamy, liczby pierwsze będą się spokojnie ujawniać wielokrotnie, a będziemy badać tylko występujące przy potęgach dwójki.
Znowu mamy dwa kierunki przeglądu zupełnego. Od pierwiastka kwadratowego z liczby rozkładanej n do połowy tej liczby, lub na odwrót.
Przy pierwiastku kwadratowym niezmiennik
n = (a+b)*a + c
ma wartości a=sqrt n; b równe 0, 1 albo 2; c jest na moduł ograniczane przez a. Zmiana a o 1 powoduje w tym zakresie zmianę b o 2,
np. 8934053 = (2988+2)*2988-67.
Przy połowie pierwiastka kwadratowego c dalej jest ograniczone na moduł przez a, a = 1/2 sqrt n, zaś b jest bliskie 3/2 sqrt n. Zmianie a o 1 tutaj towarzyszy zmiana b o 4:
np. 8934053 = (1494+4486)*1494-67.
Modyfikacje są na tyle małe, że robimy mały błąd nadając zazwyczaj a~3*b dla szacunku c jak najbliższego zeru. Potem korekta postaci: b+1 oznacza c-a.
Pierwiastek czwartego stopnia z 8934053 to 54. Czyli do rozkładu potrzebujemy zapamiętywać wielokrotności następujących liczb pierwszych: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 37, 41, 43, 47, 53. Warto mieć je posortowane po wartościach, wystarczy jedna wartość na jedną liczbę pierwszą jak najbliżej pobieranej do testu.
Zaczynając od pierwiastka kwadratowego, zapisujemy (2988; 2), (2988; 3), co można złączyć w (2988; 2, 3); (2985; 5), (2982; 7), itd.
Wbrew początkowym oczekiwaniom, nie musimy znać rozkładu kanonicznego, nawet tej jego części korzystajacej z wymienionych liczb pierwszych. Wystarczy nam liczba oraz jej dzielniki.
Algorytm:
1. k = 1+sqrt n ;
2. pętla, bierzemy wartość o 1 mniejszą (k--);
3. jeśli liczba nie jest zapamiętana, sprawdzamy ją pod kątem pierwszości
jeśli liczba jest zapamiętana, sprawdzamy, czy ma dzielnik większy od 2, jeśli nie, sprawdzamy liczbę pod kątem pierwszości;
4. liczba złożona (k, p) wskazuje, że liczba (k-p, p) też jest złożona, zapamiętujemy ją (dla każdej czynnika pierwszego p), przy czym, jeśli dana wartość k-p już jest zapamiętana, tylko dopisujemy doń kolejny dzielnik;
5. jeśli k<1/2 sqrt n, liczba jest pierwsza; w przeciwnym przypadku wracamy do 2;
Sprawdzenie pod kątem pierwszości, trafiają tu liczby pierwsze oraz postaci k=2^i*p, gdzie p jest pierwsza.
Obliczamy wartość c niezmiennika n=(k+b)*k+c, oraz sprawdzamy |c|%p. Podzielność oznacza znalezienie dzielnika p|n (bo p|k). Dla większości wartości sprowadza się do porównania takiego jak 157<881. Rzadko kiedy trzeba dzielić modulo. Oczywiście wtedy należy zakończyć algorytm.
Dlaczego to działa.
Potęgi dwójki dzielą nam przedział (1, sqrt n) na rozłączne przedziały
(2^{-i}*n, 2^{1-i}*n);
każda liczba pierwsza trafia do dokładnie jednego z nich.
Jeśli dopuścimy inne liczby pierwsze lub rozkład kanoniczny, zakresy przedziałów będą często miały części wspólne. Owszem, początkowo szybko będziemy sprawdzać i eliminować liczby pierwsze, korzystając z dzieleń. Choć wtedy część liczb będzie sprawdzanych wielokrotnie, o ile ich nie zapamiętamy. I tak musimy przejrzeć cały przedział. W dotatku mamy nadmiarowe dzielenia przy szukaniu liczb pierwszych większych niż zapamiętane, gdyż nie znamy wykladników potęg tych liczb pierwszych w rozkładach.
01 stycznia 2020
Faktoryzacja z podstawy systemu
Wspomniałem 18 grudnia o nowym pomyśle na faktoryzację, związanym z przedstawianiem podstawy systemu w postaci kanonicznej.
Pomysł jest tak specyficzny, że działa także dla normalnych liczb, choć potrzeba pamiętania ogromnych wartości z ich dzielnikami powoduje, że sposób jest nieopłacalny, i nikt o nim nie wspomina.
Podobnie jest i teraz, choć wymagam tylko znajomości tablicy liczb pierwszych nie przekraczajacych pierwiastka czwartego stopnia z rozkładanej liczby. Nie mamy? Nic straconego, delikatna rekursywna modyfikacja i już taką uzyskujemy, niejako przy okazji.Ale teraz podaję jakby tablica ta była znana.
Zacznijmy od nieformalnego podziału liczb pierwszych w zależności od rozkładanej liczby N:
- małe, mniejsze niż pierwiastek czwartego stopnia z N;
- średnie, większe niż pierwiastek czwartego stopnia, ale pojawią się w co najmniej dwu warstwach badanych;
- duże, wystąpią raz, rozpoznajemy je po tym, że podstawa systemu jest albo taką liczbą pierwszą, albo jej podwojeniem.
W pętli przeszukiwania zupełnego duże liczby pierwsze są sprawdzane i ignorowane. Potrzebujemy struktury kopca trzymajacego strukturę (liczba, lista jej dzielników), sortowaną malejąco po liczbie. Wkładając do kopca liczbę z dzielnikiem, sprawdzamy jej obecność. Jeśli już jest, tylko dopisujemy kolejny dzielnik do listy. Kopiec osiąga rozmiar równy krotności wszystkich małych i średnich liczb pierwszych.
Zaczynamy od liczby n będącej pierwiastkiem kwadratowym z N, w kopcu umieszczamy wartości (n- (n%k), k), gdzie k są małymi liczbami pierwszymi. Wiemy, że są one już dzielnikami podstawy systemu, trzeba jeszcze sprawdzić, czy są dzielnikami N.Dlatego specjalnie je zaznaczamy do sprawdzenia. Każdą liczbę pierwszą sprawdzamy dokładnie raz.
Mamy niezmiennik
N = (a+b)*a+c
Jeśli liczba k dzieli a oraz c, dzieli też N.
W pętli algorytmu przechodzimy na kolejną warstwę operacjami:
a-=1;
b+=2;
c+=b-1;
stosując przemieszczenie nadmiaru (z liczby w systemie o podstawie a), by c było ograniczone przez a. Może być też ujemne. Wartosć b tylko zwiększamy, może przekroczyć a. Dzielnik znajdziemy jako wspólny dzielnik gcd(c,a). Wystarczy tylko warunek 0= c%a, zamiast szukać wspólnego dzielnika gcd(c,a). Jest to pierwszy krok szukania tegoż dzielnika, i właśnie tyle wystarczy przy założeniu znajomości małych liczb pierwszych.
Algorytm przebiega następująco:
- pobieramy liczbę o 1 mniejszą, czyli n:=n-1
jeżeli z kopca, dzielimy ją przez jej dzielniki (z listy) by uzyskać jak najmniejszą wartość d, w przeciwnym przypadku generujemy;
uzyskujemy w ten sposób liczbę pierwszą d albo 1;
- dzielimy c%d i sprawdzamy reszty, tak samo z małymi liczbami pierwszymi z pobranej listy, reszta zero oznacza dzielnik, który zwracamy. Wyjście z algorytmu. Przy reszcie niezerowej te liczby pierwsze już nie muszą być sprawdzane, zaznaczają tylko kolejne wartości dla wygodniejszego szukania d;
- dla wszystkich uzyskanych średnich i małych liczb pierwszych k wprowadzamy do kopca pary (n-k, k);- przechodzimy na kolejną warstwę a-1;
- powtarzamy, aż osiągniemy połowę pierwiastka kwadratowego z N, zwracamy że N jest liczb pierwszą;
Załóżmy N=893453
pierwiastek kwadratowy sqrt N = 2988, którego kolejny pierwiastek to 54.
Bierzemy listę liczb pierwszych mniejszych niż 55 i wprowadzamy do kopca w postaci (c2 oznacza konieczność sprawdzenia podzielności 2 przez N):
(2988, [c2,c3])
(2987, [c29])
(2985, [c5])
(2983, [c19])
(2982, [c7])
(2981, [c11])
(2977, [c13])
(2976, [c31])
(2975, [c17])
(2968, [c53])
(2967, [c23, c43])
(2961, [c47])
(2960, [c37])
(2952, [c41])
Przystępujemy do algorytmu:
pobieramy n=a=2988, które ma dwa dzielniki: 2 i 3. Po podzieleniu przez nie n (czasem kilkakrotnie uzyskujemy nową średnią liczbę pierwszą d=83.
Niezmiennik dostarcza a=2988, b=1, c=2921
Sprawdzamy, czy N jest podzielne przez 2, 3, 83, dzieląc c przez te wartości. Zawsze występuje niezerowa reszta, zatem odkładamy do kopca nowe pozycje (2988-83, [83]) = (2905, [83]), (2985, [3]), (2986, [2])
Pozycja wyznaczona przez 2985 przyjmuje teraz wartość (2985, [3, c5])
Następna pozycja (2987, [29]), wskazuje kolejną liczbę pierwszą 103. Ale poznieważ c było duże, możemy przenieść 2987 z c jako jedynkę do b uzyskując
nową postać niezmiennika a=2897, b=4, c=-64
Sprawdzamy obydwie liczby 'dzieląc' 64%29, 64%103, odkładając na kopiec kolejne dwie wartości (2884, [103]) oraz (2958, [29]).
I tak początkowo co iterację dostajemy nową liczbę pierwszą, którą sprawdzamy. Ale wkrótce mamy wziąć 2978, na kopcu jest (2978, [2]), i mamy rozkład 2978 = 2*1489. Jest to duża liczba pierwsza w myśl podziału. Wartości (1489, [1489]) nie odkładamy do kopca.
Wartość (2976, [2,3,c31]) ma rozkład wykorzystujący tylko te cyfry, d=1. Z niezmiennika, c urosło do 101, sprawdzamy 101%31. Przy następnej takiej wartości 2970 nie ma już nic do sprawdzenia - wszystkie użyte dzielniki zostały sprawdzone.
Nieco wcześniej mamy 2971, której to wartości nie ma w kopcu. Jest to duża liczba pierwsza d=2971, która jest za duża, by być dzielnikiem. Niezmiennik ma wtedy znacznie mniejsze c=256.
W ten sposób znajdujemy kolejne liczby pierwsze; zeszlibyśmy z a do połowy 2988 czyli 1494, gdyby nie dzielnik, który znajdziemy dla pozycji o niezmienniku a=2174, b=1935 lub b=1936, c=|1087|, d=1087 = |c|.
Teraz modyfikacje.
Jeśli nie znamy wszystkich małych liczb pierwszych, możemy wywołać procedurę dla pierwiastka rekursywnie. Jednak wtedy każda znaleziona wartość pierwsza (także duza) generuje nowy obiekt do kopca do sprawdzenia. Przy wywołaniu rekursywnym niezmiennik jest nieistotny, nie porównujemy ani nie sprawdzamy. Uzyskamy w ten sposób tablicę liczb pierwszych.
Może być, że w petli głównej wartość jest iloczynem mniejszych liczb pierwszych, dla średnich liczb pierwszych wkrótce napotkamy kolejną warstwę z tym dzielnikiem, który powienien być lepiej widoczny (bo np. zmieni się parzystość). Ale dla dużych liczb pierwszych obawiam się przeoczenia tego dzielnika.
Na szczęście kierunek przechodzenia warstw można odwrócić.Proponowanym punktem startowym jest połowa pierwiastka z N, czyli w tym przykładzie a=1494, b=3a=4482 (choć lepiej 4486, gdyż wtedy c=-67).
Pomysł jest tak specyficzny, że działa także dla normalnych liczb, choć potrzeba pamiętania ogromnych wartości z ich dzielnikami powoduje, że sposób jest nieopłacalny, i nikt o nim nie wspomina.
Podobnie jest i teraz, choć wymagam tylko znajomości tablicy liczb pierwszych nie przekraczajacych pierwiastka czwartego stopnia z rozkładanej liczby. Nie mamy? Nic straconego, delikatna rekursywna modyfikacja i już taką uzyskujemy, niejako przy okazji.Ale teraz podaję jakby tablica ta była znana.
Zacznijmy od nieformalnego podziału liczb pierwszych w zależności od rozkładanej liczby N:
- małe, mniejsze niż pierwiastek czwartego stopnia z N;
- średnie, większe niż pierwiastek czwartego stopnia, ale pojawią się w co najmniej dwu warstwach badanych;
- duże, wystąpią raz, rozpoznajemy je po tym, że podstawa systemu jest albo taką liczbą pierwszą, albo jej podwojeniem.
W pętli przeszukiwania zupełnego duże liczby pierwsze są sprawdzane i ignorowane. Potrzebujemy struktury kopca trzymajacego strukturę (liczba, lista jej dzielników), sortowaną malejąco po liczbie. Wkładając do kopca liczbę z dzielnikiem, sprawdzamy jej obecność. Jeśli już jest, tylko dopisujemy kolejny dzielnik do listy. Kopiec osiąga rozmiar równy krotności wszystkich małych i średnich liczb pierwszych.
Zaczynamy od liczby n będącej pierwiastkiem kwadratowym z N, w kopcu umieszczamy wartości (n- (n%k), k), gdzie k są małymi liczbami pierwszymi. Wiemy, że są one już dzielnikami podstawy systemu, trzeba jeszcze sprawdzić, czy są dzielnikami N.Dlatego specjalnie je zaznaczamy do sprawdzenia. Każdą liczbę pierwszą sprawdzamy dokładnie raz.
Mamy niezmiennik
N = (a+b)*a+c
Jeśli liczba k dzieli a oraz c, dzieli też N.
W pętli algorytmu przechodzimy na kolejną warstwę operacjami:
a-=1;
b+=2;
c+=b-1;
stosując przemieszczenie nadmiaru (z liczby w systemie o podstawie a), by c było ograniczone przez a. Może być też ujemne. Wartosć b tylko zwiększamy, może przekroczyć a. Dzielnik znajdziemy jako wspólny dzielnik gcd(c,a). Wystarczy tylko warunek 0= c%a, zamiast szukać wspólnego dzielnika gcd(c,a). Jest to pierwszy krok szukania tegoż dzielnika, i właśnie tyle wystarczy przy założeniu znajomości małych liczb pierwszych.
Algorytm przebiega następująco:
- pobieramy liczbę o 1 mniejszą, czyli n:=n-1
jeżeli z kopca, dzielimy ją przez jej dzielniki (z listy) by uzyskać jak najmniejszą wartość d, w przeciwnym przypadku generujemy;
uzyskujemy w ten sposób liczbę pierwszą d albo 1;
- dzielimy c%d i sprawdzamy reszty, tak samo z małymi liczbami pierwszymi z pobranej listy, reszta zero oznacza dzielnik, który zwracamy. Wyjście z algorytmu. Przy reszcie niezerowej te liczby pierwsze już nie muszą być sprawdzane, zaznaczają tylko kolejne wartości dla wygodniejszego szukania d;
- dla wszystkich uzyskanych średnich i małych liczb pierwszych k wprowadzamy do kopca pary (n-k, k);- przechodzimy na kolejną warstwę a-1;
- powtarzamy, aż osiągniemy połowę pierwiastka kwadratowego z N, zwracamy że N jest liczb pierwszą;
Załóżmy N=893453
pierwiastek kwadratowy sqrt N = 2988, którego kolejny pierwiastek to 54.
Bierzemy listę liczb pierwszych mniejszych niż 55 i wprowadzamy do kopca w postaci (c2 oznacza konieczność sprawdzenia podzielności 2 przez N):
(2988, [c2,c3])
(2987, [c29])
(2985, [c5])
(2983, [c19])
(2982, [c7])
(2981, [c11])
(2977, [c13])
(2976, [c31])
(2975, [c17])
(2968, [c53])
(2967, [c23, c43])
(2961, [c47])
(2960, [c37])
(2952, [c41])
Przystępujemy do algorytmu:
pobieramy n=a=2988, które ma dwa dzielniki: 2 i 3. Po podzieleniu przez nie n (czasem kilkakrotnie uzyskujemy nową średnią liczbę pierwszą d=83.
Niezmiennik dostarcza a=2988, b=1, c=2921
Sprawdzamy, czy N jest podzielne przez 2, 3, 83, dzieląc c przez te wartości. Zawsze występuje niezerowa reszta, zatem odkładamy do kopca nowe pozycje (2988-83, [83]) = (2905, [83]), (2985, [3]), (2986, [2])
Pozycja wyznaczona przez 2985 przyjmuje teraz wartość (2985, [3, c5])
Następna pozycja (2987, [29]), wskazuje kolejną liczbę pierwszą 103. Ale poznieważ c było duże, możemy przenieść 2987 z c jako jedynkę do b uzyskując
nową postać niezmiennika a=2897, b=4, c=-64
Sprawdzamy obydwie liczby 'dzieląc' 64%29, 64%103, odkładając na kopiec kolejne dwie wartości (2884, [103]) oraz (2958, [29]).
I tak początkowo co iterację dostajemy nową liczbę pierwszą, którą sprawdzamy. Ale wkrótce mamy wziąć 2978, na kopcu jest (2978, [2]), i mamy rozkład 2978 = 2*1489. Jest to duża liczba pierwsza w myśl podziału. Wartości (1489, [1489]) nie odkładamy do kopca.
Wartość (2976, [2,3,c31]) ma rozkład wykorzystujący tylko te cyfry, d=1. Z niezmiennika, c urosło do 101, sprawdzamy 101%31. Przy następnej takiej wartości 2970 nie ma już nic do sprawdzenia - wszystkie użyte dzielniki zostały sprawdzone.
Nieco wcześniej mamy 2971, której to wartości nie ma w kopcu. Jest to duża liczba pierwsza d=2971, która jest za duża, by być dzielnikiem. Niezmiennik ma wtedy znacznie mniejsze c=256.
W ten sposób znajdujemy kolejne liczby pierwsze; zeszlibyśmy z a do połowy 2988 czyli 1494, gdyby nie dzielnik, który znajdziemy dla pozycji o niezmienniku a=2174, b=1935 lub b=1936, c=|1087|, d=1087 = |c|.
Teraz modyfikacje.
Jeśli nie znamy wszystkich małych liczb pierwszych, możemy wywołać procedurę dla pierwiastka rekursywnie. Jednak wtedy każda znaleziona wartość pierwsza (także duza) generuje nowy obiekt do kopca do sprawdzenia. Przy wywołaniu rekursywnym niezmiennik jest nieistotny, nie porównujemy ani nie sprawdzamy. Uzyskamy w ten sposób tablicę liczb pierwszych.
Może być, że w petli głównej wartość jest iloczynem mniejszych liczb pierwszych, dla średnich liczb pierwszych wkrótce napotkamy kolejną warstwę z tym dzielnikiem, który powienien być lepiej widoczny (bo np. zmieni się parzystość). Ale dla dużych liczb pierwszych obawiam się przeoczenia tego dzielnika.
Na szczęście kierunek przechodzenia warstw można odwrócić.Proponowanym punktem startowym jest połowa pierwiastka z N, czyli w tym przykładzie a=1494, b=3a=4482 (choć lepiej 4486, gdyż wtedy c=-67).
18 grudnia 2019
Rozkład liczb, kolejny algorytm
Na początku grudnia opublikowałem zarys algorytmu, w którym podstawową ideą jest utworzenie płaszczyzny z liczby, oraz szukanie śladu dzielników dla dużych wartości.
Na razie coś mnie blokuje przed napisaniem tego w C++, ale jest już wersja w Pythonie.
Miałem kłopoty, jak szybko ominąć część kodu po znalezieniu małego dzielnika. Zdecydowałem się na pętlę.
[code python]
def nwd(a,b,s):
if( 0==b ):
return a
if( a<b ): #swap(a,b)
c=a
a=b
b=c
while( 1 ): # zmniejszamy b, bo wiemy, ze sa one wzglednie pierwsze
if( 0==b%2 ):
b/=2
continue
if( 0==b%3 ):
b/=3
continue
if( 0==b%5 ):
b/=5
continue
if( 0==b%7 ):
b/=7
continue
break
if( 0==a%b ):
return b
a = a%b
if( a+a>b ) :
a = b-a
if( s>a ): #zatrzyma: wiemy ze nie ma tak malych dzielnikow
return 1
return nwd(b,a,s)
def modstop(s):
# zwieksza s do najblizszej liczby nieparzystej nie podzielnej przez 3, 5, 7
while( 1 ):
s+=2
if( 0==s%3 ):
continue
if( 0==s%5 ):
continue
if( 0==s%7 ):
continue
#break
return s
s=7 # lub wiecej, jesli jestesmy pewni
n= duza liczba
a=int (sqrt n) # jak to policzyc na liczbach calkowitych?
#a=int (n**(0.5)) # blad w liczeniu pozniejszych operacji
b= 1+(n-a*a)//a
c= n-(a+b)*a # w algorytmie c<0, trzymamy je jako ujemna wartosc
print a,b,c, (a+b)*a+c # sprawdzenie niezmiennika (a+b)*a+c = n
while( 1 ):
if( 0==n%2 ): # male dzielniki
n /=2
print "Dzielnik 2"
break
if( 0==n%3 ):
n/=3
print "Dzielnik 3"
break
if( 0==n%5 ):
n/=5
print "Dzielnik 5"
break
if( 0==n%7 ):
n/=7
print "Dzielnik 7"
break
while ( 1 ):
f = a%s # obliczenie (a+b)*a+c modulo s czyli spr. male dzielniki
e = ((f+b)*f+c)%s
if( 0==e ):
print "Dzielnik z modulo ",s
break
s = modstop(s) # zwiekszenie s
e = nwd(a,-c,s) # nwd wyrazu wolnego i podstawy systemu
if( 1<e ):
print "Dzielnik ze sladu ",e
break;
a-=1 # pelni role podstawy systemu, zmniejszamy o 1
b+=2 # wyrugowanie wplywu podstawy na wyraz wolny
c+=b-1 # modyfikacja wyrazu wolnego
if( 0==c ) :
print "Dzielnik z wyrazu wolnego ",a
break
if( 0<c ) : // wyraz wolny wiekszy niz podstawa a
b+=1
c-=a
#mozna wypisac - dla testow
#print "liczba (1*",a,"+",b,")*",a,c," stop = ",s
if( s>a ) : # duze lub male dzielniki nie znalezione, brak mozliwosci innych
print "Liczba pierwsza ",n
break
break
[\code python]
Dla malych wartosci dziala. Dla liczby 90-bitowej po dobie liczenia iloraz wartosci do sprawdzenia do oszacowania dzielnika z dołu jest mniejszy niż 2000, następnego dnia poniżej 1000. Sprawdzane są równocześnie małe i duże kandydaci, dlatego zakres możliwości się zmniejsza z obu stron.
Drugiego dnia zostało sprawdzone około 0,1% wszystkich możliwości, zastosowany wzór: iloraz różnicy podstawy a i minimalnej możliwej liczby pierwszej s przez liczność początkową (a-s)/(sqrt n). Można zatem spróbować oszacować czas przebiegu na tej maszynie na kilkaset dni. Choć podejrzewam istnienie przedziałów, w których po wejściu do nwd nastąpi od razu wyjście ( bo |c|<s ).
Mam jeszcze jeden pomysł związany z tą płaszczyzną, choć będzie wymagał sporo pamieci i moze być nieefektywny. Przechowywanie podstawy w postaci docelowo kanonicznej... Jako skutek uboczny pojawi się tablica liczb pierwszych.
Na razie coś mnie blokuje przed napisaniem tego w C++, ale jest już wersja w Pythonie.
Miałem kłopoty, jak szybko ominąć część kodu po znalezieniu małego dzielnika. Zdecydowałem się na pętlę.
[code python]
def nwd(a,b,s):
if( 0==b ):
return a
if( a<b ): #swap(a,b)
c=a
a=b
b=c
while( 1 ): # zmniejszamy b, bo wiemy, ze sa one wzglednie pierwsze
if( 0==b%2 ):
b/=2
continue
if( 0==b%3 ):
b/=3
continue
if( 0==b%5 ):
b/=5
continue
if( 0==b%7 ):
b/=7
continue
break
if( 0==a%b ):
return b
a = a%b
if( a+a>b ) :
a = b-a
if( s>a ): #zatrzyma: wiemy ze nie ma tak malych dzielnikow
return 1
return nwd(b,a,s)
def modstop(s):
# zwieksza s do najblizszej liczby nieparzystej nie podzielnej przez 3, 5, 7
while( 1 ):
s+=2
if( 0==s%3 ):
continue
if( 0==s%5 ):
continue
if( 0==s%7 ):
continue
#break
return s
s=7 # lub wiecej, jesli jestesmy pewni
n= duza liczba
a=int (sqrt n) # jak to policzyc na liczbach calkowitych?
#a=int (n**(0.5)) # blad w liczeniu pozniejszych operacji
b= 1+(n-a*a)//a
c= n-(a+b)*a # w algorytmie c<0, trzymamy je jako ujemna wartosc
print a,b,c, (a+b)*a+c # sprawdzenie niezmiennika (a+b)*a+c = n
while( 1 ):
if( 0==n%2 ): # male dzielniki
n /=2
print "Dzielnik 2"
break
if( 0==n%3 ):
n/=3
print "Dzielnik 3"
break
if( 0==n%5 ):
n/=5
print "Dzielnik 5"
break
if( 0==n%7 ):
n/=7
print "Dzielnik 7"
break
while ( 1 ):
f = a%s # obliczenie (a+b)*a+c modulo s czyli spr. male dzielniki
e = ((f+b)*f+c)%s
if( 0==e ):
print "Dzielnik z modulo ",s
break
s = modstop(s) # zwiekszenie s
e = nwd(a,-c,s) # nwd wyrazu wolnego i podstawy systemu
if( 1<e ):
print "Dzielnik ze sladu ",e
break;
a-=1 # pelni role podstawy systemu, zmniejszamy o 1
b+=2 # wyrugowanie wplywu podstawy na wyraz wolny
c+=b-1 # modyfikacja wyrazu wolnego
if( 0==c ) :
print "Dzielnik z wyrazu wolnego ",a
break
if( 0<c ) : // wyraz wolny wiekszy niz podstawa a
b+=1
c-=a
#mozna wypisac - dla testow
#print "liczba (1*",a,"+",b,")*",a,c," stop = ",s
if( s>a ) : # duze lub male dzielniki nie znalezione, brak mozliwosci innych
print "Liczba pierwsza ",n
break
break
[\code python]
Dla malych wartosci dziala. Dla liczby 90-bitowej po dobie liczenia iloraz wartosci do sprawdzenia do oszacowania dzielnika z dołu jest mniejszy niż 2000, następnego dnia poniżej 1000. Sprawdzane są równocześnie małe i duże kandydaci, dlatego zakres możliwości się zmniejsza z obu stron.
Drugiego dnia zostało sprawdzone około 0,1% wszystkich możliwości, zastosowany wzór: iloraz różnicy podstawy a i minimalnej możliwej liczby pierwszej s przez liczność początkową (a-s)/(sqrt n). Można zatem spróbować oszacować czas przebiegu na tej maszynie na kilkaset dni. Choć podejrzewam istnienie przedziałów, w których po wejściu do nwd nastąpi od razu wyjście ( bo |c|<s ).
Mam jeszcze jeden pomysł związany z tą płaszczyzną, choć będzie wymagał sporo pamieci i moze być nieefektywny. Przechowywanie podstawy w postaci docelowo kanonicznej... Jako skutek uboczny pojawi się tablica liczb pierwszych.
09 grudnia 2019
Obliczanie silni większych liczb
Spróbowałem kilkoma sposobami obliczyć silnię ze 100.
W tym celu należy dobrze przygotować strukturę. Liczbę trzymam na liście dwukierunkowej o węzłach link postaci:
[int cyfra, link prev, link next, int flaga]
Okazało się, że same wskaźniki na sąsiednie cyfry prev oraz next nie wystarczą. Aby dobrze zaalokować liczbę na liście potrzebna była flaga, gdyż w przeciwnym przypadku były kłopoty z jednocyfrową liczbą 0. Nie była ona odróżniana od węzła pustego. Ponieważ węzły należały do dużego kontenera, szukanie w tym kontenerze wolnego miejsca na kolejną cyfrę wskazywało taką liczbę jako puste miejsce i nadpisywało...
Sama liczba ma dwa pola: link value oraz link baze. Składa się z cyfr dziesiętnych (docelowo), chwyconych za cyfrę najmniej znaczącą oraz podstawę systemu liczbowego.
Oprócz tego występują funkcje mnożenia przez 10 "mul0()" oraz przez małą wartość "mula( int a)". Dołączyłem także konwersje między systemami niedziesiątkowymi "convert (int new_baze)".
Wykorzystałem najpierw standardowe mnożenie dla liczenia silni z liczby n dla sprawdzenia wyników:
Liczba a;
for( i=n; 0<i; i-- )
a.mula(i);
a.show();
Następnie konwersje, by uniknąć kłopotów rozbiłem je na trzy fazy:
- liczenie 9! małymi iloczynami - by uzyskać odpowiednią wartość początkową;
- przekształcenie wartości do liczby w systemie o podstawie n;
- reszta obliczeń, by wynik wyszedł w dziesiątkowym:
Liczba a = 9!;
a.baze( n );
a.mul0();
for( i=n-1; 9<i; i-- ) {
a.convert(i);
a.mul0();
};
a.show();
Wreszcie rozklad kanoniczny czyli mieszanka konwersji oraz mul0() w odpowiednich systemach. I tu się sypało, uzyskana wartość była znacznie za mała.
W pozostałych też były kłopoty. Okazało się, że zarówno przy mnożeniu mula(int), jak i przy konwersjach nie mogę sobie pozwolić na przechowywanie reszt w dodatkowej zmiennej przechodząc między węzłami cyfr. Należy je przekazać sąsiedniej cyfrze zaraz po ich zaobserwowaniu. Inaczej czasem miewałem błędy oraz uzyskana wartość była zawyżana.
A oto szczególy funkcji:
mul0() { // mnożenie przez 10 (dokładniej: przez baze)
link cyfr = t.add(); // nowy węzeł z kontenera;
cyfr.cyfra = 0;
value->next = cyfr;
cyfr->prev = value;
value = cyfr;
};
czyli zwykłe doczepienie węzła z zerem na końcu liczby i uchwycenie go jako liczby.
mula( int a ) {}
// pierwszy przebieg: mnożenie każdej cyfry liczby przez a
link b = value;
while( b ) { b->item *= a; b=b->prev; }
// przeniesienia wartości
b = value;
int s=0;
while( 1 ) {
s = b->cyfra;
b->cyfra = s% 10; // system dziesiątkowy
s /= 10;
if( s ) {
if( b-> prev ) b->prev->cyfra += s;
else {
link c=t.add();
c->cyfra = s;
c->next = b; b->prev = c; // przypięcie węzła cyfry najbardziej znaczącej
}
};
s=0;
if( b->prev ) b = b->prev; else break;
};
Konwersja też jest podzielona na dwa moduły, w pierwszym wymagana jest liczba dwucyfrowa oraz ustawienie węzła blokującego b na cyfrę poprzedzajacą najbardziej znaczącą. Drugi węzeł link c przebiega cyfry bardziej znaczące od b ze wzorem s = cyfra*r, której część całkowita zasila bieżącą cyfrę wskazywaną przez c, zaś reszta jest odkładana do cyfry mniej znaczącej c->next->cyfra. Podstawa baze maleje, zatem wartość liczby rośnie.
int r = baze->cyfra - new-baze;
int s=0;
// modyfikacja pól baze
link b = value;
while( b->prev ) b = b->prev;
while( 1 ) {
if( b->next ) b = b->next; else break;
c = b->prev;
while( 1 ) {
s = c->cyfra * r;
c->cyfra += s/new_baze;
c->next->cyfra += s % new_baze;
if( c->prev ) c = c->prev; else break;
};
c=b; ... // druga część
};
W drugiej części zmieniamy kierunek c=b oraz przenosimy nadmiary podobnie jak przy mnozeniu mula(int).
Potem przesuwamy b = b->next; aż przekształcane będą wszystkie cyfry liczby.
Obydwoma sposobami w przeciągu sekund wypisało mi wartość wszystkich 158 cyfr dziesiętnych silni 100!
W tym celu należy dobrze przygotować strukturę. Liczbę trzymam na liście dwukierunkowej o węzłach link postaci:
[int cyfra, link prev, link next, int flaga]
Okazało się, że same wskaźniki na sąsiednie cyfry prev oraz next nie wystarczą. Aby dobrze zaalokować liczbę na liście potrzebna była flaga, gdyż w przeciwnym przypadku były kłopoty z jednocyfrową liczbą 0. Nie była ona odróżniana od węzła pustego. Ponieważ węzły należały do dużego kontenera, szukanie w tym kontenerze wolnego miejsca na kolejną cyfrę wskazywało taką liczbę jako puste miejsce i nadpisywało...
Sama liczba ma dwa pola: link value oraz link baze. Składa się z cyfr dziesiętnych (docelowo), chwyconych za cyfrę najmniej znaczącą oraz podstawę systemu liczbowego.
Oprócz tego występują funkcje mnożenia przez 10 "mul0()" oraz przez małą wartość "mula( int a)". Dołączyłem także konwersje między systemami niedziesiątkowymi "convert (int new_baze)".
Wykorzystałem najpierw standardowe mnożenie dla liczenia silni z liczby n dla sprawdzenia wyników:
Liczba a;
for( i=n; 0<i; i-- )
a.mula(i);
a.show();
Następnie konwersje, by uniknąć kłopotów rozbiłem je na trzy fazy:
- liczenie 9! małymi iloczynami - by uzyskać odpowiednią wartość początkową;
- przekształcenie wartości do liczby w systemie o podstawie n;
- reszta obliczeń, by wynik wyszedł w dziesiątkowym:
Liczba a = 9!;
a.baze( n );
a.mul0();
for( i=n-1; 9<i; i-- ) {
a.convert(i);
a.mul0();
};
a.show();
Wreszcie rozklad kanoniczny czyli mieszanka konwersji oraz mul0() w odpowiednich systemach. I tu się sypało, uzyskana wartość była znacznie za mała.
W pozostałych też były kłopoty. Okazało się, że zarówno przy mnożeniu mula(int), jak i przy konwersjach nie mogę sobie pozwolić na przechowywanie reszt w dodatkowej zmiennej przechodząc między węzłami cyfr. Należy je przekazać sąsiedniej cyfrze zaraz po ich zaobserwowaniu. Inaczej czasem miewałem błędy oraz uzyskana wartość była zawyżana.
A oto szczególy funkcji:
mul0() { // mnożenie przez 10 (dokładniej: przez baze)
link cyfr = t.add(); // nowy węzeł z kontenera;
cyfr.cyfra = 0;
value->next = cyfr;
cyfr->prev = value;
value = cyfr;
};
czyli zwykłe doczepienie węzła z zerem na końcu liczby i uchwycenie go jako liczby.
mula( int a ) {}
// pierwszy przebieg: mnożenie każdej cyfry liczby przez a
link b = value;
while( b ) { b->item *= a; b=b->prev; }
// przeniesienia wartości
b = value;
int s=0;
while( 1 ) {
s = b->cyfra;
b->cyfra = s% 10; // system dziesiątkowy
s /= 10;
if( s ) {
if( b-> prev ) b->prev->cyfra += s;
else {
link c=t.add();
c->cyfra = s;
c->next = b; b->prev = c; // przypięcie węzła cyfry najbardziej znaczącej
}
};
s=0;
if( b->prev ) b = b->prev; else break;
};
Konwersja też jest podzielona na dwa moduły, w pierwszym wymagana jest liczba dwucyfrowa oraz ustawienie węzła blokującego b na cyfrę poprzedzajacą najbardziej znaczącą. Drugi węzeł link c przebiega cyfry bardziej znaczące od b ze wzorem s = cyfra*r, której część całkowita zasila bieżącą cyfrę wskazywaną przez c, zaś reszta jest odkładana do cyfry mniej znaczącej c->next->cyfra. Podstawa baze maleje, zatem wartość liczby rośnie.
int r = baze->cyfra - new-baze;
int s=0;
// modyfikacja pól baze
link b = value;
while( b->prev ) b = b->prev;
while( 1 ) {
if( b->next ) b = b->next; else break;
c = b->prev;
while( 1 ) {
s = c->cyfra * r;
c->cyfra += s/new_baze;
c->next->cyfra += s % new_baze;
if( c->prev ) c = c->prev; else break;
};
c=b; ... // druga część
};
W drugiej części zmieniamy kierunek c=b oraz przenosimy nadmiary podobnie jak przy mnozeniu mula(int).
Potem przesuwamy b = b->next; aż przekształcane będą wszystkie cyfry liczby.
Obydwoma sposobami w przeciągu sekund wypisało mi wartość wszystkich 158 cyfr dziesiętnych silni 100!
03 grudnia 2019
Algorytm największego wspólnego dzielnika
Klasa największego wspólnego dzielnika.
Wiemy skąd inąd, że jeśli wartości zmniejszą się poniżej wartości zewnętrznej stop, liczby są względnie pierwsze.
Jak modna hermetyzacja, to proszę :) Bardziej zahermetyzować się już chyba nie da.
class Gcd {
private:
Liczba a, b;
Liczba( Liczba an, Liczba bn ) : a(an) b(bn) {};
Liczba ngcd();
friend Liczba nwd(Liczba a, Liczba b);
};
Liczba Gcd :: ngcd() {
if( a<b ) swap(a,b);
a = a%b;
if( !a ) return b;
if( a+a>b ) a = b-a;
if( a<stop ) return Liczba(1);
return ngcd();
};
Funkcja wywoławcza:
Liczba gcd( Liczba an, Liczba bn ) {
Nwd c(an,bn);
return c.ngcd();
};
Algorytm jest nieco szybszy niż klasyczny. Warunek a+a>b pozwala jeszcze raz zabrać b uzyskując wartość ujemną w a, do której w następnym kroku byśmy dodawaii. Mnożenie przez (-1) pozwala przywrócić wartość dodatnią, co odbywa się niejawnie.
Wartości funkcji są zewnętrzne do wywołania funkcji rekursywnej, dzięki czemu jest mniejsze zużycie stosu pamięci. Można pójść dalej, w funkcji gcd utworzyć petlę nieskończoną wywołującą c.ngcd(), która zwraca wartość np. -1 jak ma liczyć dalej, 0 jak względnie piersze lub 1 gdy zwracana Liczba jest już w b. Czy wtedy będzie jeszcze widać, że ta funkcja jest rekursywna?
Wiemy skąd inąd, że jeśli wartości zmniejszą się poniżej wartości zewnętrznej stop, liczby są względnie pierwsze.
Jak modna hermetyzacja, to proszę :) Bardziej zahermetyzować się już chyba nie da.
class Gcd {
private:
Liczba a, b;
Liczba( Liczba an, Liczba bn ) : a(an) b(bn) {};
Liczba ngcd();
friend Liczba nwd(Liczba a, Liczba b);
};
Liczba Gcd :: ngcd() {
if( a<b ) swap(a,b);
a = a%b;
if( !a ) return b;
if( a+a>b ) a = b-a;
if( a<stop ) return Liczba(1);
return ngcd();
};
Funkcja wywoławcza:
Liczba gcd( Liczba an, Liczba bn ) {
Nwd c(an,bn);
return c.ngcd();
};
Algorytm jest nieco szybszy niż klasyczny. Warunek a+a>b pozwala jeszcze raz zabrać b uzyskując wartość ujemną w a, do której w następnym kroku byśmy dodawaii. Mnożenie przez (-1) pozwala przywrócić wartość dodatnią, co odbywa się niejawnie.
Wartości funkcji są zewnętrzne do wywołania funkcji rekursywnej, dzięki czemu jest mniejsze zużycie stosu pamięci. Można pójść dalej, w funkcji gcd utworzyć petlę nieskończoną wywołującą c.ngcd(), która zwraca wartość np. -1 jak ma liczyć dalej, 0 jak względnie piersze lub 1 gdy zwracana Liczba jest już w b. Czy wtedy będzie jeszcze widać, że ta funkcja jest rekursywna?
Algorytm rozkładu z płaszczyzny uzyskanej z liczby
W połowie listopada podałem, jak z liczby n zrobić płat F(b,d)=c o niezmienniku
n = d^2+bd+c = d(b+d)+c
Okazało się, że zarówno dzielniki, jak i ich wielokrotności tworzą łatwo wykrywalne cięcia przy stałych d, z których łatwo znajdziemy dzielniki. Im mniejszy dzielnik, tym tych specyficznych cięć jest więcej, regularnie rozłożonych. Oznacza to, że możemy ograniczyć się tylko do badania liczb bliskich pierwiastowi kwadratowego z liczby rozkładanej.
Algorytm wygląda zatem następująco:
szukamy pierwiastka liczby sqrt n; jego wyraz wolny równy 0 wyznacza rozkład z pierwiastka;
obliczamy wartość modulo mała liczba stop z wyrażenia d(b+d)+c; możemy też teraz zwiększyć stop;
obliczamy największy wspólny dzielnik wyrazu wolnego c oraz podstawy d, co sprawdza przynależność do tego specyficznego cięcia;
przejście na sąsiednie cięcie płata F:
d--;
b+=2;
c+=b-1;
czasem tak uzyskana wartość c jest większa niż podstawa d, zmniejszamy ją w pętli o operacjach przypominających przeniesienie między cyframi liczby w systemie pozycyjnym
{ b++; c-=d; }
jeśli uzyskamy 0=c, poznamy dzielnik.
Kryterium stopu jest
stop > d
po spełnieniu którego wiemy, że liczba jest pierwsza.
Dochodzi kilka drobnych, lecz istotnych szczegółów. Możemy przyspieszyć wzrost wartości stop do kolejnych liczb niepodzielnych przez 3, 5, 7 (oczywiście większych niż 7, by ewentualny tak mały dzielnik nam nie umknął). Oznacza to, że stop staje się minimum z badanych wartości, co możemy uwzględnić w liczeniu największej wspólnej wielokrotności. Nachylenie tej krzywej dyskretnej stop(d) jest między 2d a 10d. Od dużych wartości jest ograniczone przez d, Zmniejsza to obszar poszukiwań pierwiastka.
Jeżeli iloraz dzielników liczby n=p*q, czyli p/q>1, napotkamy po drodze więcej niż jedno cięcie wskazujące dzielnik. Zatrzymujemy się na pierwszym. Na ogół wtedy znaleziony wspólny dzielnik jest iloczynem małej wartosci i dzielnika n. Może być parzysty, dlatego nie możemy wykluczyć parzystych wartości d. Potrzebne będzie wtedy jeszcze jedno liczenie znalezionego wspólnego dzielnika z liczbą rozkładaną n.
Kod zwiększania wartości stop jest następujący:
if( nie_podzielne(...) ) // test: stop | d(b+d)+c
else while(1) {
stop+=2;
if( 7<stop && (!(stop%3) || !(stop%5) || !(stop%7)) ) continue;
else break;
};
Kod obliczania dzielnika podam w kolejnym poście. Jest zbyt specyficzny i pozwoli zerknąć na nowe możliwości obliczania funkcji rekursywnych.
n = d^2+bd+c = d(b+d)+c
Okazało się, że zarówno dzielniki, jak i ich wielokrotności tworzą łatwo wykrywalne cięcia przy stałych d, z których łatwo znajdziemy dzielniki. Im mniejszy dzielnik, tym tych specyficznych cięć jest więcej, regularnie rozłożonych. Oznacza to, że możemy ograniczyć się tylko do badania liczb bliskich pierwiastowi kwadratowego z liczby rozkładanej.
Algorytm wygląda zatem następująco:
szukamy pierwiastka liczby sqrt n; jego wyraz wolny równy 0 wyznacza rozkład z pierwiastka;
obliczamy wartość modulo mała liczba stop z wyrażenia d(b+d)+c; możemy też teraz zwiększyć stop;
obliczamy największy wspólny dzielnik wyrazu wolnego c oraz podstawy d, co sprawdza przynależność do tego specyficznego cięcia;
przejście na sąsiednie cięcie płata F:
d--;
b+=2;
c+=b-1;
czasem tak uzyskana wartość c jest większa niż podstawa d, zmniejszamy ją w pętli o operacjach przypominających przeniesienie między cyframi liczby w systemie pozycyjnym
{ b++; c-=d; }
jeśli uzyskamy 0=c, poznamy dzielnik.
Kryterium stopu jest
stop > d
po spełnieniu którego wiemy, że liczba jest pierwsza.
Dochodzi kilka drobnych, lecz istotnych szczegółów. Możemy przyspieszyć wzrost wartości stop do kolejnych liczb niepodzielnych przez 3, 5, 7 (oczywiście większych niż 7, by ewentualny tak mały dzielnik nam nie umknął). Oznacza to, że stop staje się minimum z badanych wartości, co możemy uwzględnić w liczeniu największej wspólnej wielokrotności. Nachylenie tej krzywej dyskretnej stop(d) jest między 2d a 10d. Od dużych wartości jest ograniczone przez d, Zmniejsza to obszar poszukiwań pierwiastka.
Jeżeli iloraz dzielników liczby n=p*q, czyli p/q>1, napotkamy po drodze więcej niż jedno cięcie wskazujące dzielnik. Zatrzymujemy się na pierwszym. Na ogół wtedy znaleziony wspólny dzielnik jest iloczynem małej wartosci i dzielnika n. Może być parzysty, dlatego nie możemy wykluczyć parzystych wartości d. Potrzebne będzie wtedy jeszcze jedno liczenie znalezionego wspólnego dzielnika z liczbą rozkładaną n.
Kod zwiększania wartości stop jest następujący:
if( nie_podzielne(...) ) // test: stop | d(b+d)+c
else while(1) {
stop+=2;
if( 7<stop && (!(stop%3) || !(stop%5) || !(stop%7)) ) continue;
else break;
};
Kod obliczania dzielnika podam w kolejnym poście. Jest zbyt specyficzny i pozwoli zerknąć na nowe możliwości obliczania funkcji rekursywnych.
23 listopada 2019
Programowanie wskaźnikami, paradygmaty
Omijając kłopoty związane z obsługą wskaźników w C, na jeden biegun podążyli twórcy Javy - eliminacja wskaźników z widocznych obszarów (interfejs ma inne znaczenie). Ja postanowiłem podążyć na drugi bierun - eliminacja zmiennych.
Dane nie są trzymane w zmiennych, lecz w wskaźnikach.
Różnice w implementacji:
- zabroniona instrukcja * pointer = variable - uszkodzi system wpisując coś w obszar pamięci, który nie powinien być edytowany
- instrukcja pointer = &variable, wskaźniki inicjujemy w inny sposób, ten zwróci losowy fragment pamięci
- inicjowanie wskaźnika, pomocniczy wskaźnik zerowy pp, by uzyskać odpowiednią długość komórki pamięci, sizeof(char) = bajt,
const char * const pp=0;
oraz instrukcja pointer = pp+constans,
wtedy wskaźnik wskazuje obszar pamięci zastrzeżonej, może przechwycić dowolną klasę, liczbę całkowitą, w szczególności także znak, a nawet 4-znakową nazwę funkcji.
- zmiana wartości do dodanie, odjęcie czy inna operacja, ewentualnie po konwersji wskaźnika na int
- podstawienie, kod wygenerowany kompilatorem jest wystarczający, odpada tworzenie kopii zmiennej
W ten sposób cały program można zapisać tablicą, listą, drzewem klas.
Idę dalej - pierwszy bajt zawiera informację o danej klasie, w szczególności jej nazwę. Chodzi o poprawne zinterpretowanie pola, bo tu już typologia kompilatora może zawieść.
Możliwe pomyłki - nie przechwytujemy całej klasy, lecz jej składową. Wtedy program może się posypać, gdyż nie widzi pól klasy.
W dotychczasowych próbach nawet mimo krytycznego błędu program grzecznie ogranicza się tylko do zadanego obszaru pamięci, i może nawet zwrócić wartość 'wszystko zadziałało poprawnie' mimo fatalnych naruszeń obrabianych danych.
Ciąg dalszy nastąpi, kiedy dopracuję programowanie wielowątkowe wskaźnikami pod DOSa. Wtedy podam budowę podstawowych węzłów pamięci tego podejścia i sposób ich trzymania.
Dane nie są trzymane w zmiennych, lecz w wskaźnikach.
Różnice w implementacji:
- zabroniona instrukcja * pointer = variable - uszkodzi system wpisując coś w obszar pamięci, który nie powinien być edytowany
- instrukcja pointer = &variable, wskaźniki inicjujemy w inny sposób, ten zwróci losowy fragment pamięci
- inicjowanie wskaźnika, pomocniczy wskaźnik zerowy pp, by uzyskać odpowiednią długość komórki pamięci, sizeof(char) = bajt,
const char * const pp=0;
oraz instrukcja pointer = pp+constans,
wtedy wskaźnik wskazuje obszar pamięci zastrzeżonej, może przechwycić dowolną klasę, liczbę całkowitą, w szczególności także znak, a nawet 4-znakową nazwę funkcji.
- zmiana wartości do dodanie, odjęcie czy inna operacja, ewentualnie po konwersji wskaźnika na int
- podstawienie, kod wygenerowany kompilatorem jest wystarczający, odpada tworzenie kopii zmiennej
W ten sposób cały program można zapisać tablicą, listą, drzewem klas.
Idę dalej - pierwszy bajt zawiera informację o danej klasie, w szczególności jej nazwę. Chodzi o poprawne zinterpretowanie pola, bo tu już typologia kompilatora może zawieść.
Możliwe pomyłki - nie przechwytujemy całej klasy, lecz jej składową. Wtedy program może się posypać, gdyż nie widzi pól klasy.
W dotychczasowych próbach nawet mimo krytycznego błędu program grzecznie ogranicza się tylko do zadanego obszaru pamięci, i może nawet zwrócić wartość 'wszystko zadziałało poprawnie' mimo fatalnych naruszeń obrabianych danych.
Ciąg dalszy nastąpi, kiedy dopracuję programowanie wielowątkowe wskaźnikami pod DOSa. Wtedy podam budowę podstawowych węzłów pamięci tego podejścia i sposób ich trzymania.
18 listopada 2019
Funkcja z liczby i jej własności
Dowolnie duża wartość zapisana jako liczba trójcyfrowa... Idąc w tym kierunku uzyskałem dyskretną funkcję trójwymiarową o niezmienniku
n = d*d + b*d + c (1)
którą okazał się płat nad płaszczyzną (d x b) o wartościach c. W każdym punkcie tego płatu niezmiennik jest spełniony.
Dla dzielnika n wartość c=0, a pojawiły się dodatkowe własności. W sąsiedztwie dzielnika (sporym) przecięcia płatu płaszczyznami b=const, d=const powstaje wykres monotoniczny.
Dla przecięcia d=const każdy punkt jest wielokrotnością dzielnika, zależną od odległości od niego.
Dla b=const odpowiednie przecięcie ma przyrost zmienny, ale w okolicy dzielnika bliski sumie obu dzielników.
Poruszając się po płacie można skakać z pomocą niezmiennika, lub można znaleźć proste wzory na przechodzenie do sąsiedniego punktu kratowego. Z tych wzorów wyznacza się wspomniane własności. Jedne to zastosowanie konwersji dla d, drugie to przeniesienia z b do c, wreszcie istnieje prosty wzór na chodzenie po jednej z diagonali. Dla drugiej przekątnej wzór jest gorszy.
Oznacza to, że na tym płacie dzielnik jest lepiej widoczny, przez więcej niż jeden punkt. Widać też wzory skróconego mnożenia dla systemów sąsiednich dzielnikowi (wtedy d jest bliskie b).
Czy te informacje wystarczą, by można było stosować przeszukiwanie binarne do faktoryzacji?
n = d*d + b*d + c (1)
którą okazał się płat nad płaszczyzną (d x b) o wartościach c. W każdym punkcie tego płatu niezmiennik jest spełniony.
Dla dzielnika n wartość c=0, a pojawiły się dodatkowe własności. W sąsiedztwie dzielnika (sporym) przecięcia płatu płaszczyznami b=const, d=const powstaje wykres monotoniczny.
Dla przecięcia d=const każdy punkt jest wielokrotnością dzielnika, zależną od odległości od niego.
Dla b=const odpowiednie przecięcie ma przyrost zmienny, ale w okolicy dzielnika bliski sumie obu dzielników.
Poruszając się po płacie można skakać z pomocą niezmiennika, lub można znaleźć proste wzory na przechodzenie do sąsiedniego punktu kratowego. Z tych wzorów wyznacza się wspomniane własności. Jedne to zastosowanie konwersji dla d, drugie to przeniesienia z b do c, wreszcie istnieje prosty wzór na chodzenie po jednej z diagonali. Dla drugiej przekątnej wzór jest gorszy.
Oznacza to, że na tym płacie dzielnik jest lepiej widoczny, przez więcej niż jeden punkt. Widać też wzory skróconego mnożenia dla systemów sąsiednich dzielnikowi (wtedy d jest bliskie b).
Czy te informacje wystarczą, by można było stosować przeszukiwanie binarne do faktoryzacji?
12 listopada 2019
Dzielenie aproksymacjami
W matematyce wedyjskiej występuje szczególny przypadek dzielenia przez liczby np. 29, 39. Wykonuje się to dzieląc przez najbliższą dziesiątkę oraz dodanie poprawki.
Spróbowałem, czy sztuka taka uda się w ogólności. I udaje się.
Przedstawmy dzielnik w zapisie binarnym, oraz sprawdźmy, ile ma fragmentów złożonych z samych jedynek 1...1. Jeżeli tych jedynek jest więcej niż jedna, wykonamy dwa działania, na pozycji zera poprzedzającego oraz ostatniej jedynki. Gdy jedna, operacje wykonamy tylko dla tej pozycji. Potrzebujemy zmienną pomocniczą, z której liczymy kolejne poprawki, oraz je odejmujemy (przed, na jedynej) grupą jedynek, Poprawki dodajemy nad jedynką konczącą fragment. Zmienna ta przybliża się do ilorazu.
A jakie działania? Zamiast dzielnika rozważamy jego kolejne aproksymacje, i dzielimy zmienną pomocniczą właśnie przez te aproksymacje po odcięciu potęg dwójki. Uzyskamy wartość, o którą należy zmodyfikować zmienną pomocniczą. Należy jeszcze sprawdzić, gdyż trafiamy bardzo blisko wartości z dzielenia, ale czasem za daleko.
Zobaczmy na przykładach.
n/23 = 8934053 / 23
23 = 1 0111b, jedynka na pozycji 0x10, fragment trzech jedynek od pozycji ósemek do jedności, trzy obliczenia.
Dzielimy 8934053 = 558378 * 16 + 5
Zmienną roboczą jest 558378.
Fragment, początek, aproksymacja dzielnika to 3*8, obliczenie
558378 / 3 = 186126, które odejmujemy od zmiennej roboczej
558378 - 186126 = 372252
Sprawdzamy mnożąc 372252*3*8, blisko n, zostawiamy
koniec fragmentu ..111, tu już dzielimy przez cały dzielnik 23:
372252 / 23 = 16184
reszty z dzielania możemy ignorować, dodajemy
372252+16184 = 388436
Chybiamy z resztą, właściwy, poprawny iloraz jest tuż obok:
8934053 = 388437 * 23 + 2
8934053 / 27
27 = 1 1011b, dwa fragmenty
8934053 = 279189 * 32 + 5
zmienna robocza 279189 / 3 = 93063, bo aproksymacja to 3*8
279189 + 93063 = 372252
następny fragment zaczyna się dla aproksymacji 7*4:
372252 / 7 = 53178
oraz 372252 - 53178 = 319074
319074 / 27 = 11817
oraz 319074 + 11817 = 330891
Sprawdzamy i korygujemy: 8934053 = 330890*27+23
8934053 / 341
341 = 1 0101 0101b, najdłuższy obliczeniowo przypadek, bo nie ma dłuższych fragmentów. Zaczynamy od aproksymacji dzielnika 1*256
8934053 = 34898*256
i działania:
34898 - (34898 / 5) = 34898 - 6979 = 27919 poprawka na 27918*5*64+293
27918 - (27918 / 21) = 27918 - 1329 = 26589
26589 - (26589 / 85) = 26589 - 312 = 26277 poprawka
26276 - (26276 / 341) = 26276 - 77) = 26199
i finalnie 8934053 = 26199*341+194
Zamiast dzielić bądź odejmować, dzielimy przez coraz to większe kawałki dzielnika. Dzielenia początkowe można wykonać przesunięciami binarnymi. Staramy się, by uzyskać wartości iloczynów ze zmienną roboczą na początku fragmentu bliskie n, na końcu nieco mniejsze niż n.
Spróbowałem, czy sztuka taka uda się w ogólności. I udaje się.
Przedstawmy dzielnik w zapisie binarnym, oraz sprawdźmy, ile ma fragmentów złożonych z samych jedynek 1...1. Jeżeli tych jedynek jest więcej niż jedna, wykonamy dwa działania, na pozycji zera poprzedzającego oraz ostatniej jedynki. Gdy jedna, operacje wykonamy tylko dla tej pozycji. Potrzebujemy zmienną pomocniczą, z której liczymy kolejne poprawki, oraz je odejmujemy (przed, na jedynej) grupą jedynek, Poprawki dodajemy nad jedynką konczącą fragment. Zmienna ta przybliża się do ilorazu.
A jakie działania? Zamiast dzielnika rozważamy jego kolejne aproksymacje, i dzielimy zmienną pomocniczą właśnie przez te aproksymacje po odcięciu potęg dwójki. Uzyskamy wartość, o którą należy zmodyfikować zmienną pomocniczą. Należy jeszcze sprawdzić, gdyż trafiamy bardzo blisko wartości z dzielenia, ale czasem za daleko.
Zobaczmy na przykładach.
n/23 = 8934053 / 23
23 = 1 0111b, jedynka na pozycji 0x10, fragment trzech jedynek od pozycji ósemek do jedności, trzy obliczenia.
Dzielimy 8934053 = 558378 * 16 + 5
Zmienną roboczą jest 558378.
Fragment, początek, aproksymacja dzielnika to 3*8, obliczenie
558378 / 3 = 186126, które odejmujemy od zmiennej roboczej
558378 - 186126 = 372252
Sprawdzamy mnożąc 372252*3*8, blisko n, zostawiamy
koniec fragmentu ..111, tu już dzielimy przez cały dzielnik 23:
372252 / 23 = 16184
reszty z dzielania możemy ignorować, dodajemy
372252+16184 = 388436
Chybiamy z resztą, właściwy, poprawny iloraz jest tuż obok:
8934053 = 388437 * 23 + 2
8934053 / 27
27 = 1 1011b, dwa fragmenty
8934053 = 279189 * 32 + 5
zmienna robocza 279189 / 3 = 93063, bo aproksymacja to 3*8
279189 + 93063 = 372252
następny fragment zaczyna się dla aproksymacji 7*4:
372252 / 7 = 53178
oraz 372252 - 53178 = 319074
319074 / 27 = 11817
oraz 319074 + 11817 = 330891
Sprawdzamy i korygujemy: 8934053 = 330890*27+23
8934053 / 341
341 = 1 0101 0101b, najdłuższy obliczeniowo przypadek, bo nie ma dłuższych fragmentów. Zaczynamy od aproksymacji dzielnika 1*256
8934053 = 34898*256
i działania:
34898 - (34898 / 5) = 34898 - 6979 = 27919 poprawka na 27918*5*64+293
27918 - (27918 / 21) = 27918 - 1329 = 26589
26589 - (26589 / 85) = 26589 - 312 = 26277 poprawka
26276 - (26276 / 341) = 26276 - 77) = 26199
i finalnie 8934053 = 26199*341+194
Zamiast dzielić bądź odejmować, dzielimy przez coraz to większe kawałki dzielnika. Dzielenia początkowe można wykonać przesunięciami binarnymi. Staramy się, by uzyskać wartości iloczynów ze zmienną roboczą na początku fragmentu bliskie n, na końcu nieco mniejsze niż n.
04 listopada 2019
Nowy algorytm faktoryzacji? Tylko z początku,
Rozwijając algorytm rozkładu liczby N na podstawie gigantycznej stałej M (iloczyn małych wartości) w postaci
N = d(M+1) + k*M + r
gdzie d jest sprawdzanym dzielnikiem, k jest małą liczbą zaś r uzupełnia niezmiennik, doszedłem do spostrzeżenia:
r też potrafi być gigantyczne, mimo że może być kilka rzędów wielkości mniejsze niż N. Trudno jest przez dobór czynników N uczynić mniejszym, i nie zawsze w odpowiednim zakresie. Rozwiązaniem jest albo trzymanie tej reszty w systemie o podstawie d, albo dzielenie. W obu przypadkach pojawia się złożoność kwadratowa, którą spodziewałem się wyeliminować.
Ale budowa M nasuwa mi myśl, by r trzymać jako sumę iloczynów wartości dwu-, trójcyfrowych w systemie o podstawie d, i modyfikować razem z zawartością M. Więcej. Możemy przecież tak przedstawić całą liczbę N, co doprowadzi do nowego algorytmu rozkładu, z konwersjami małych wartości wewnątrz liczby!
Przykształcenia:
przyjmijmy ciąg rosnący małych liczb, mogą być kolejne lub np. kolejne pierwsze [3, 5, 7, 11, 13, 17, 19]. Liczba N jest wielomianem od tych coraz krótszych iloczynów. Ewentualny dodatkowy czynnik dołączymy do największego, lub pozostawimy, np. w drugim składniku 16 jest takim psującym dodatkiem
N = 8934053 = 3*5*7*11*15*17*19 + 3*5*7*11*15*17*16 + 3*5*7 + 3*5 + 8
Zapisujemy poszczególne czynniki w systemie o podstawie d, ale nie przejmujemy się wartościami ujemnymi, i tak preferujemy bliskie zeru. Aby znaleźć resztę, wystarczy obliczyć wartość wielomianu dla cyfr najmniej znaczących.
Tak dla d=3 zerujemy wszystkie składniki prócz 8, uzyskując resztę z dzielenia N przez 3 zapisanego jako [1 0].
Następnie jeśli jakaś wartość jest postaci [1 0] albo [1 -1], dołączamy ją do kolejnego najmniejszego czynnika, tworząc liczbę trójcyfrową, np. [1 0]*[1 2] = [1 2 0], albo [55 0]*[1 -1] = [55 -55 0]. Dalej stosujemy konwersje, które przerobią z wolna te czynniki w dwucyfrowe, ale nie dopuścimy do powstawania jednocyfrowych. Staramy się wykorzystać tylko liczby z ciągu, by jak najwięcej czynników było jednakowych. Jeśli ciąg liczył s pozycji, fakt ten zamiast konwersji w ogólności niemal s(s-1)/2 czynników pozwala zadowolić się około 2s-1 czynnikami. W przykładzie mamy ich mniej, 20 zamiast 8*7/2, ale już pierwsze zwiększenie d na 5 usuwa cztery z nich zastępując je piętnastką zapisaną 3*5 = [3 0]. Dalej upraszczają się zarówno czynniki, jak i składniki.
Kwestia składnika bez iloczynu. Zostawiamy go tymczasowo. Ale niech no tylko pojawi się drugi, połączymy je w jedną wartość. Tak już wkrótce przy wzroście d ostatnie trzy składniki złączą się w wartość równoważną 128.
I tak im większe d, tym wielomian staje się prostszy, choć obliczenia cyfr jedności czynników mogą być rzędu pierwiastka z N. Wreszcie przekraczamy z d wartość pierwiastka sześciennego N. I dostajemy, że wielomian upraszcza się do sumy dwu liczb trójcyfrowych. Po złączeniu uzyskujemy jedną liczbę trójcyfrową, a dalej jak w opublikowanym w 2014 roku w MJM artykule... Wzrost d o 2 jest równoważny konwersji o 2.
Ostatecznie pomysł sprowadził się do przeglądu zupełnego konwersjami. Jeden z pierwszych algorytmów, jaki uzyskałem badając systemy niedziesiątkowe. Potwierdza to, że dla bardzo dużych wartości przegląd zupełny polegający na konwersjach liczby trójcyfrowej jest asymptotycznie liniowy, przepraszam, nawet pracuje liniowo.
N = d(M+1) + k*M + r
gdzie d jest sprawdzanym dzielnikiem, k jest małą liczbą zaś r uzupełnia niezmiennik, doszedłem do spostrzeżenia:
r też potrafi być gigantyczne, mimo że może być kilka rzędów wielkości mniejsze niż N. Trudno jest przez dobór czynników N uczynić mniejszym, i nie zawsze w odpowiednim zakresie. Rozwiązaniem jest albo trzymanie tej reszty w systemie o podstawie d, albo dzielenie. W obu przypadkach pojawia się złożoność kwadratowa, którą spodziewałem się wyeliminować.
Ale budowa M nasuwa mi myśl, by r trzymać jako sumę iloczynów wartości dwu-, trójcyfrowych w systemie o podstawie d, i modyfikować razem z zawartością M. Więcej. Możemy przecież tak przedstawić całą liczbę N, co doprowadzi do nowego algorytmu rozkładu, z konwersjami małych wartości wewnątrz liczby!
Przykształcenia:
przyjmijmy ciąg rosnący małych liczb, mogą być kolejne lub np. kolejne pierwsze [3, 5, 7, 11, 13, 17, 19]. Liczba N jest wielomianem od tych coraz krótszych iloczynów. Ewentualny dodatkowy czynnik dołączymy do największego, lub pozostawimy, np. w drugim składniku 16 jest takim psującym dodatkiem
N = 8934053 = 3*5*7*11*15*17*19 + 3*5*7*11*15*17*16 + 3*5*7 + 3*5 + 8
Zapisujemy poszczególne czynniki w systemie o podstawie d, ale nie przejmujemy się wartościami ujemnymi, i tak preferujemy bliskie zeru. Aby znaleźć resztę, wystarczy obliczyć wartość wielomianu dla cyfr najmniej znaczących.
Tak dla d=3 zerujemy wszystkie składniki prócz 8, uzyskując resztę z dzielenia N przez 3 zapisanego jako [1 0].
Następnie jeśli jakaś wartość jest postaci [1 0] albo [1 -1], dołączamy ją do kolejnego najmniejszego czynnika, tworząc liczbę trójcyfrową, np. [1 0]*[1 2] = [1 2 0], albo [55 0]*[1 -1] = [55 -55 0]. Dalej stosujemy konwersje, które przerobią z wolna te czynniki w dwucyfrowe, ale nie dopuścimy do powstawania jednocyfrowych. Staramy się wykorzystać tylko liczby z ciągu, by jak najwięcej czynników było jednakowych. Jeśli ciąg liczył s pozycji, fakt ten zamiast konwersji w ogólności niemal s(s-1)/2 czynników pozwala zadowolić się około 2s-1 czynnikami. W przykładzie mamy ich mniej, 20 zamiast 8*7/2, ale już pierwsze zwiększenie d na 5 usuwa cztery z nich zastępując je piętnastką zapisaną 3*5 = [3 0]. Dalej upraszczają się zarówno czynniki, jak i składniki.
Kwestia składnika bez iloczynu. Zostawiamy go tymczasowo. Ale niech no tylko pojawi się drugi, połączymy je w jedną wartość. Tak już wkrótce przy wzroście d ostatnie trzy składniki złączą się w wartość równoważną 128.
I tak im większe d, tym wielomian staje się prostszy, choć obliczenia cyfr jedności czynników mogą być rzędu pierwiastka z N. Wreszcie przekraczamy z d wartość pierwiastka sześciennego N. I dostajemy, że wielomian upraszcza się do sumy dwu liczb trójcyfrowych. Po złączeniu uzyskujemy jedną liczbę trójcyfrową, a dalej jak w opublikowanym w 2014 roku w MJM artykule... Wzrost d o 2 jest równoważny konwersji o 2.
Ostatecznie pomysł sprowadził się do przeglądu zupełnego konwersjami. Jeden z pierwszych algorytmów, jaki uzyskałem badając systemy niedziesiątkowe. Potwierdza to, że dla bardzo dużych wartości przegląd zupełny polegający na konwersjach liczby trójcyfrowej jest asymptotycznie liniowy, przepraszam, nawet pracuje liniowo.
Subskrybuj:
Posty (Atom)