Kiedy opisywałem faktoryzację korzystając z podstaw parzystych, wspomniałem o konwersji o większą wartość. Przykładowo przechodzenie na system o 8 więcej, o 16 więcej itp.
Kiedyś proponowałem coś takiego: mając liczbę [a, b] konwersja o 8 polega na przekształcceniu [a, b-8a], po czym naprawa powstałych cyfr za pomocą przeniesień.Wartości przechodzą na cyfrę mniej znaczącą, potem wracają na początkowe miejsce.
Okazuje się, że istnieje możliwość takiego przekształcenia, że do cyfry mniej znaczącej trafia tylko reszta. Nawet mocniej. Nie zawsze musimy mnożyć przez różnicę podstaw docelowej i początkowej.
Pokażę to na przykładzie konwersji z podstawy 20 na 28. Różnica podstaw 8. Ale największy wspólny dzielnik podstaw to 4. Możemy niejawnie 'przejść' na system 20/4 =5, przeliczyć nową wartość różnicy jak dla 8/4=2, oraz 'wrócić z powstałego' siódemkowego. Te przechodzenia zawierają przekształcenia przeciwne, czyli wzajemnie się niwelują. Pozostaje mnożenie przez 2 cyfry w dwudziestkowym, oraz reszta dla cyfry mniej znaczącej jest mnożona przez 4.
Więcej, możemy od razu oszacować wartość w nowym systemie, dobierając resztę tak, by nie mieć nadmiaru bądź niedomiaru w cyfrze.
Przykład: przeliczyć [17 14] _20 na system o podstawie 28
największy wspólny dzielnik systemów to 4, oraz 28/4=7. Jest to wielokrotność, która pozostaje przy cyfrze.
2*17/7 daje modyfikatory 4 i resztę 6, ale możemy być 'sprytniejsi' i weżmiemy 5 oraz resztę -1. Wtedy zamiast odejmować 6*4 od 14 dodamy doń 1*4.
Teraz odejmiemy znaleziony modyfikator od cyfry dziesiątek, resztę od cyfry jedności:
[17-5, 14-(-1)*4] = [12, 18] _ 28
Cyfry najmniej znaczącej nie przekształcamy. Otrzymujemy poprawną wartość cyfr w nowym systemie!
Modyfikatory odejmujemy dopiero po użyciu cyfr. Obliczenia są tak łatwe, że przy odrobinie wprawy wiemy kiedy brać nieco więcej, oraz rzadko kiedy potrzebne są dodatkowe przeniesienia między cyframi.
Przypominam, że konwersja polega na iteracyjnym dołączeniu cyfry od liczby, przekształceniu wszystkich cyfr uzyskanego podciągu.
Fragment takich obliczeń (dołączamy kolejną cyfrę 21):
z systemu 28 na system 36 (wspólny dzielnik 4), zmodyfikowana podstawa to 36/4=9
[4, 13, 11, 21] _28 podciąg cyfr podczas konwersji, ((4*36+13)*36+11)*28+21
[8, 26, 22, ] podwojone cyfry
[1*9-1, 3*9-1, 2*9+4, ] wyłuskanie modyfikatorów - wielokrotności 9 i reszt
[4-1, 13-3, 11-2, 21] uwzględnienie modyfikatorów
[4-1, 13-3+4, 11-2+4, 21-16] uwzględnienie poczwórnych reszt
[3, 14, 13, 5] _ 36 nowa wartość podciągu ((3*36+14)*36+13)*36+5
Jeśli największy wspólny dzielnik podstaw to 1, nie możemy skorzystać z tego sposobu.
29 kwietnia 2019
08 kwietnia 2019
Faktoryzacja liczbami parzystym, inna wersja trial division
Zastanawiałem się, czy opublikować pierwotną znalezioną wersję faktoryzacji liczbami parzystymi, kiedy naprowadziła już ona na heurystykę opisaną w poprzednim poście.Okazuje się, że ten przegląd zupełny ma nieco większą złożoność, i nie nadaje się do komputerów, tylko dla ludzi.
Ale niech tam. Przynajmniej pokażę, jak rozumowałem.
Przy faktoryzacji przebiegam jakieś 2^(lg n) reszt (trochę mniej - do pierwiastka) kwadratowego z n) dla kolejnych podstaw p. Klasycznie połowę, wystarczy brać p nieparzyste. I to jest standardowa metoda trial division, pozostaje kwestia czy stosowane jest dzielenie, czy konwersje o 2, ale to szczegół techniczny.
Przechodząc na podstawę parzystą, nie trafiam w dzielnik, ale tuż obok. Wtedy suma cyfr przystaje do zera modulo (p-1), albo naprzemienna suma (alternate sum) przystaje do zera modulo (p+1). Analogicznie jak cechy podzielności przez 9, 11 odpowiednio. Dla kolejnych wartości parzystych ta sama wartość np. 43 jest sprawdzana dwukrotnie, z obu stron 42 oraz 44. Mogę zatem zmniejszyć stałą M złożoności algorytmu trial division O(M log^2 n), biorąc co czwartą wartość i te cechy. Pokryją wartości nieparzyste oraz rozpatruję połowę M. Miłe.
Może jeszcze uda się zmniejszyć M? Przyjrzyjmy się wykładnikom przy potęgach liczby d dla kolejnych wielokrotności d w postaci kanonicznej (iloczyn kolejnych liczb pierwszych):
1 2 1 3 1 2 1 4 1 ...
Proszę porównać dla d=2 (kolejne liczby parzyste):
2 2^2 2*3 2^3 2*5 2^2*3 2*7 2^4 2*9 ...
Specyficzny ciąg. Jeśli zainicjować A=1, potem niech w A wartością maksymalną jest k, to tworzy się grzebień postaci
A (k+1) A
Ale są luki, jednak trzeba brać pod uwagę wszystkie wielokrotności 4.
Lecz możemy przeksztalcać liczbę nieco inaczej. Bardziej wielowątkowo.
Całka Riemanna pokrywa pole pod funkcją prostokątami pionowymi. Całka Lebesque'a 'prostokątami' poziomymi. W podobny sposób zmieniam kolejność obliczeń, przez co pojawią się wątki.
Pierwszy watek to podstawy będące wszystkimi nieparzystymi wielokrotnościami 4, drugi tworzą nieparzyste wielokrotności 8. Pokrywają przedział z lukami, kolejna luka zaczyna się od 2*8=16. Jest to kolejny wątek. I tak dalej.
Wątki inicjowane są kolejnymi potęgami 2: k= 4, 8, 16, 32,..., zaś w danym wątku kN liczone są postacie liczby n dla kolejnych podstaw 2pk. Postacie liczby, nie reszty z dzielenia.
Są to konwersje o podwojony najmniejszy wspólny dzielnik danego wątku.
Czyli podstawy przekształcanych systemów dla danej liczby tworzą ciągi:
4, 12, 20, 28, 36, 44, ...
8, 24, 40, ...
16, 48, ...
32, ...
...
Wygląd modyfikowanej liczby szybko się zmniejsza, obliczanie sum, naprzemiennych sum jest prosty, ale konwersje nie są już tak miłe. Pogarszają złożoność o kolejny log n.
Dla człowieka widać na pierwszy rzut oka na cyfry, czy warto liczyć sumy, dla komputera niezbyt bez dodatkowego kodu.
Ale przecież człowiek nie będzie rozkładać dużej liczby bez wsparcia komputera! Niech ten przebieg faktoryzacji pozostanie ciekawostką.
Ale niech tam. Przynajmniej pokażę, jak rozumowałem.
Przy faktoryzacji przebiegam jakieś 2^(lg n) reszt (trochę mniej - do pierwiastka) kwadratowego z n) dla kolejnych podstaw p. Klasycznie połowę, wystarczy brać p nieparzyste. I to jest standardowa metoda trial division, pozostaje kwestia czy stosowane jest dzielenie, czy konwersje o 2, ale to szczegół techniczny.
Przechodząc na podstawę parzystą, nie trafiam w dzielnik, ale tuż obok. Wtedy suma cyfr przystaje do zera modulo (p-1), albo naprzemienna suma (alternate sum) przystaje do zera modulo (p+1). Analogicznie jak cechy podzielności przez 9, 11 odpowiednio. Dla kolejnych wartości parzystych ta sama wartość np. 43 jest sprawdzana dwukrotnie, z obu stron 42 oraz 44. Mogę zatem zmniejszyć stałą M złożoności algorytmu trial division O(M log^2 n), biorąc co czwartą wartość i te cechy. Pokryją wartości nieparzyste oraz rozpatruję połowę M. Miłe.
Może jeszcze uda się zmniejszyć M? Przyjrzyjmy się wykładnikom przy potęgach liczby d dla kolejnych wielokrotności d w postaci kanonicznej (iloczyn kolejnych liczb pierwszych):
1 2 1 3 1 2 1 4 1 ...
Proszę porównać dla d=2 (kolejne liczby parzyste):
2 2^2 2*3 2^3 2*5 2^2*3 2*7 2^4 2*9 ...
Specyficzny ciąg. Jeśli zainicjować A=1, potem niech w A wartością maksymalną jest k, to tworzy się grzebień postaci
A (k+1) A
Ale są luki, jednak trzeba brać pod uwagę wszystkie wielokrotności 4.
Lecz możemy przeksztalcać liczbę nieco inaczej. Bardziej wielowątkowo.
Całka Riemanna pokrywa pole pod funkcją prostokątami pionowymi. Całka Lebesque'a 'prostokątami' poziomymi. W podobny sposób zmieniam kolejność obliczeń, przez co pojawią się wątki.
Pierwszy watek to podstawy będące wszystkimi nieparzystymi wielokrotnościami 4, drugi tworzą nieparzyste wielokrotności 8. Pokrywają przedział z lukami, kolejna luka zaczyna się od 2*8=16. Jest to kolejny wątek. I tak dalej.
Wątki inicjowane są kolejnymi potęgami 2: k= 4, 8, 16, 32,..., zaś w danym wątku kN liczone są postacie liczby n dla kolejnych podstaw 2pk. Postacie liczby, nie reszty z dzielenia.
Są to konwersje o podwojony najmniejszy wspólny dzielnik danego wątku.
Czyli podstawy przekształcanych systemów dla danej liczby tworzą ciągi:
4, 12, 20, 28, 36, 44, ...
8, 24, 40, ...
16, 48, ...
32, ...
...
Wygląd modyfikowanej liczby szybko się zmniejsza, obliczanie sum, naprzemiennych sum jest prosty, ale konwersje nie są już tak miłe. Pogarszają złożoność o kolejny log n.
Dla człowieka widać na pierwszy rzut oka na cyfry, czy warto liczyć sumy, dla komputera niezbyt bez dodatkowego kodu.
Ale przecież człowiek nie będzie rozkładać dużej liczby bez wsparcia komputera! Niech ten przebieg faktoryzacji pozostanie ciekawostką.
06 kwietnia 2019
Faktoryzacja liczbami parzystymi
Zapiszmy liczbę rozkładaną n jako
a*p+b = n
gdzie a jest bliskie b, zaś p jest parzyste. W przypadku a=b mamy rozkład:
n = a*p+a = a*(p+1)
Potraktuję to wyrażenie jako zapis w systemie o podstawie p, co pozwala używać konwersji i przeniesień. Wtedy heurystyka rozkładu sprowadza się do zastosowania następujących przekształceń:
n = a*2+b = a*2+(a+1)
gdy a jest nieparzyste, przenosimy jedynkę dodając p do b (np. (a-1)*p + (p+b)).
dalej rozważamy dwa wyrażenia:
[a',b',p'] = [a/2 , b, 2p]
oraz
[a/2, b-a, 2(p+1)]
Przenosimy wartości między pierwszą a drugą pozycją, by były jak najbliższe. Jest to związane z dzieleniem przez p+1, gdyż gdy a>b przenosimy k:
a-k = b+pk, stąd a-b=(1+p)k;
oraz przy a<b
a+k = b-pk, stąd a-b=-(1+p)k;
Jeśli różnica |a-b|<p-1, odcinamy ten ciąg przekształceń. Gdy a=b kończymy zwracając rozkład. Prodedura zawsze się zakończy, gdyż każdą liczbę n przedstawimy jako 1*(n-1)+1. Liczby pierwsze mają jedynie to przedstawienie. Nie można użyć |a-b|<p, co będzie pokazane w przykładzie dalej.
Uzyskamy w ten sposób kolejne wyrażenia, których wydaje się wykładnicza liczność. To się tylko wydaje. Na początku owszem, potem przycinianie bierze górę.
Przedstawić wszystkie możliwe przedstawienia dla rozkładu liczby 133.
p=2, a=44, b=45 (44*2+45 z dzielenia 133/3), czyli
[44, 45, 2]
kolejne trójki to:
[22, 45, 4] oraz [22, 45-44, 2(2+1)] = [22, 1, 6]
po poprzenoszeniu nadmiarów, by przybliżyć a do b mamy:
[26, 29, 4] oraz [19, 19, 6], które już wskazuje poszukiwane przedstawienie 19*(6+1). Cięcie.
Teraz z [26, 29, 4] uzyskujemy
[13, 29, 8] oraz [13, 3, 10]
Z tego drugiego przenosimy, np. do [12, 13, 10]. Kolejna iteracja da trójki [6, 13, 20] oraz [6, 1, 22]. W obu różnica |a-b| da 7, 5 odpowiednio, obie mniejsze niż p>19. Tniemy, choć z [6, 1, 22] mozemy uzyskać ostatnie przedstawienie [1, 1, 132] korzystając z konwersji na system o potrojonej podstawie.
Wracamy do [13, 29, 8], przenosimy jedynkę, tym razem zwiększając a - i tak zaraz dzielimy przez 2. Mamy [14, 21, 8].
Zauważmy, że różnica b-a=7 jest podzielna zarówno przez 7, jak i 14, i jest mniejsza niż p=8. Jest ochota na przycięcie, co zgubi kolejne przedstawienia.
Oto kolejne trójki: [7, 21, 16], oraz [7, 7, 18], z drugiej wynika kolejne przedstawienie 7*(18+1).
Pierwszą modyfikujemy do [8, 5, 16]. Co prawda teraz a>b, ale jest parzyste, zaraz się zmniejszy. Teraz podaję już tylko trójki nie spełniające warunku przycinania: [4, 5, 32], [2, 1, 66] i ostatecznie ucinane [1, 1, 132].
Znalezione trzy przedstawienia dla rozkładu 133 = 19*(6+1) = 7*(18+1) = 1*(132+1).
Teraz tylko zaimplementować...
a*p+b = n
gdzie a jest bliskie b, zaś p jest parzyste. W przypadku a=b mamy rozkład:
n = a*p+a = a*(p+1)
Potraktuję to wyrażenie jako zapis w systemie o podstawie p, co pozwala używać konwersji i przeniesień. Wtedy heurystyka rozkładu sprowadza się do zastosowania następujących przekształceń:
n = a*2+b = a*2+(a+1)
gdy a jest nieparzyste, przenosimy jedynkę dodając p do b (np. (a-1)*p + (p+b)).
dalej rozważamy dwa wyrażenia:
[a',b',p'] = [a/2 , b, 2p]
oraz
[a/2, b-a, 2(p+1)]
Przenosimy wartości między pierwszą a drugą pozycją, by były jak najbliższe. Jest to związane z dzieleniem przez p+1, gdyż gdy a>b przenosimy k:
a-k = b+pk, stąd a-b=(1+p)k;
oraz przy a<b
a+k = b-pk, stąd a-b=-(1+p)k;
Jeśli różnica |a-b|<p-1, odcinamy ten ciąg przekształceń. Gdy a=b kończymy zwracając rozkład. Prodedura zawsze się zakończy, gdyż każdą liczbę n przedstawimy jako 1*(n-1)+1. Liczby pierwsze mają jedynie to przedstawienie. Nie można użyć |a-b|<p, co będzie pokazane w przykładzie dalej.
Uzyskamy w ten sposób kolejne wyrażenia, których wydaje się wykładnicza liczność. To się tylko wydaje. Na początku owszem, potem przycinianie bierze górę.
Przedstawić wszystkie możliwe przedstawienia dla rozkładu liczby 133.
p=2, a=44, b=45 (44*2+45 z dzielenia 133/3), czyli
[44, 45, 2]
kolejne trójki to:
[22, 45, 4] oraz [22, 45-44, 2(2+1)] = [22, 1, 6]
po poprzenoszeniu nadmiarów, by przybliżyć a do b mamy:
[26, 29, 4] oraz [19, 19, 6], które już wskazuje poszukiwane przedstawienie 19*(6+1). Cięcie.
Teraz z [26, 29, 4] uzyskujemy
[13, 29, 8] oraz [13, 3, 10]
Z tego drugiego przenosimy, np. do [12, 13, 10]. Kolejna iteracja da trójki [6, 13, 20] oraz [6, 1, 22]. W obu różnica |a-b| da 7, 5 odpowiednio, obie mniejsze niż p>19. Tniemy, choć z [6, 1, 22] mozemy uzyskać ostatnie przedstawienie [1, 1, 132] korzystając z konwersji na system o potrojonej podstawie.
Wracamy do [13, 29, 8], przenosimy jedynkę, tym razem zwiększając a - i tak zaraz dzielimy przez 2. Mamy [14, 21, 8].
Zauważmy, że różnica b-a=7 jest podzielna zarówno przez 7, jak i 14, i jest mniejsza niż p=8. Jest ochota na przycięcie, co zgubi kolejne przedstawienia.
Oto kolejne trójki: [7, 21, 16], oraz [7, 7, 18], z drugiej wynika kolejne przedstawienie 7*(18+1).
Pierwszą modyfikujemy do [8, 5, 16]. Co prawda teraz a>b, ale jest parzyste, zaraz się zmniejszy. Teraz podaję już tylko trójki nie spełniające warunku przycinania: [4, 5, 32], [2, 1, 66] i ostatecznie ucinane [1, 1, 132].
Znalezione trzy przedstawienia dla rozkładu 133 = 19*(6+1) = 7*(18+1) = 1*(132+1).
Teraz tylko zaimplementować...
Subskrybuj:
Posty (Atom)