Na to pytanie, o ile ktoś nie myli cyfry z liczbą, mówi: jak to ile? Dziesięć. A oto one: 0, 1, 2, 3, 4, 5, 6, 7 , 8, 9.
W systemie binarnym występują tylko dwie cyfry: 0 i 1.
W szesnastkowym z kolei brakuje różnych cyfr. Uzupełniamy literami: A, B, C, D, E, F.
Są kolejne cyfry alfabetu, że można podać około 36 rozróżnialnych cyfr, od 0 do Z.
No dobrze, ale potrzebuję więcej cyfr, które mogę porównywać. Kilkaset, może parę tysięcy.
Kiedy zacząłem studia, korzystając z wyświetlacza cyfrowego (ma 4 pionowe kreski i 3 poziome, dodałem jeszcze ukośne / oraz \ ) wypisałem sobie kilkaset cyfr. Każda kolejna to była ściśle uporządkowana permutacja podzbioru kresek uporządkowanego rosnąco. Kilkaset cyfr.
Teraz, kiedy mam coraz mniejsze szansę na pracę, mogę wrócić do tego pomysłu. Ale ulepszę go. Dalej mam krawędzie komórki wyświetlacza cyfrowego, które porządkuję następujaco:
_3
1| _ | 2
4
/ to 5 oraz \ to 6.
Ale teraz inaczej grupuję. Podstawowy schemat to ciąg (134 oznacza obecność krawędzi o podanych numerach):
1 2 12 3 4 34 13 14 23 24 123 124 134 234 1234
Po wyczerpaniu możliwości dochodzą kolejno 5, 6, 56.
Tym razem oprócz rozróżnialności dołączam kryterium spójności, czyli wszystkie składowe kreski są złączone końcami. Dlatego nie będzie cyfrą 34 czyli =. Wydaje się mniej możliwości, lecz jest to złudzenie, gdyż teraz po osiągnięciu cyfry 123456 (dziesiętne 58) tworzę metaschemat, w którym ten sam mechanizm stosuję do grup kresek (górna).(dolna). Czyli dopiero teraz uzupełniam do klasycznego okienka wyświetlacza cyfrowego.
Czyli tworzą się rodziny ().1, ().2, ().12, schematy z ().3 się powtarzają wcześniej, zaś schematy ().4, ().34 nie są spójne, zatem są opuszczane.
Ze względu na rozróżnialność, jeśli mamy ().1, musi istnieć krawędź (krawędzie) 12 lub 4, gdyż 1.1 oraz 1 są nieodróżnialne. Podobnie nieodróżnialne są 13.1 oraz 13, gdyż dodatkowa krawędź ().1 jest przedłużeniem już istniejącej 1.(). Same przedłużenia występują, gdy istnieje nieprzedłużona równoległa krawędź.
Kiedy w tych dwu komórkach dojdziemy do postaci cyfrowego 8, dołączamy najpierw w komórce górnej 5, potem w dolnej 5, potem w obydwu 5. w górnej 6 (a potem 5, pojawia się m.in. cyfra > ), w dolnej 6, w obu 6, w górnej 56, w dolnej 56, w obu 56. W tych schematach jest mało powtórzeń oraz opuszczeń ze względu na niespójność.
Kiedy skończymy tę grupę, osiągając cyfrę 123456.12456 (4 z góry = 3 z dołu), następny megaschemat to poziome ()-(). Tym razem ignorujemy schematy, w których występuje 3-() bez 4-() lub 2-(), gdyż 2 pierwszej komórki jest 1 drugiej. I kolejne kilkaset cyfr gotowych.
Megaschematy łączymy wierzchołkami, nie krawędziami. Pojawia się dodatkowa możliwość łączenia po skosie, co jednak zignorujemy, bo prawie pusta komórka pierwsza megaschematu ()[.()]-() odpowiadającego 13 to wypełni.
Pozwala to wygenerować tysiące różnych cyfr, które możemy porównywać. Zaś przeliczaniem na system dziesiętny niech się zajmie komputer dużej mocy...
25 sierpnia 2017
03 sierpnia 2017
Związek systemu Fibonacciego z systemem trójkowym
Kiedy operuję konwersjami dzielącymi przez 3 i jej potęgi, działam tylko na nieparzystych cyfrach w systemie Fibonacciego. Pojawił się pomysł, aby zapisać liczbę wypisując tylko te cyfry z systemu Fibonacciego. Wtedy na pozycjach tych występują tylko 0, 1 i 2.
Kiedy przyglądałem się temu, zauważyłem niezwykłe podobieństwo do systemu trójkowego, Jest jednak drobna różnica. Przekształcam konwersjami postać:
0020200 = 0021001 = 0110001 = 1000001
Wypisuję co drugą cyfrę 0220 = 1001. I tu kryje się modyfikacja.
System Fibonacciego utożsamia ze sobą wszystkie postaci 220, 221, 222, 1000, 1001 systemu trójkowego. Gdy liczba kończy się na 22, ostatnie '01' jest ignorowane. Istotne tu są zwłaszcza te trzy z podciągiem '22', które praktycznie nie mają prawa wystąpić w systemie Fibonacciego.
Wyłączmy zatem n krotność 22_3=8d oraz iloczyn 5 z krotnością wystąpień '22x' dla wszystkich możliwych pozycji '22' w reprezentacji trójkowej.
Dodajmy do n te krotności i zapiszmy przybliżenie liczby w systemie trójkowym.
Np. 59 /8 = 7, 59/24*5 = 10, 59+7+10=76 = 2211_3;
74/8 = 9, 74/24*5 = 15, 74/72*5 = 5, 74+9+15+5 = 103 = 10211_3.
Rozpisując teraz uzyskane cyfry systemu trójkowego jako pary cyfr systemu Fibonacciego uzyskamy dosyć dobre przybliżenie wartości systemu Fibonacciego z nadmiarem, uzyskanego schematami z dzieleń [00300]=[100001]. Biorąc mnożnik 3 zamiast 5, uzyskamy przybliżenie z niedomiarem.
Jest to hipoteza, sprawdzona na kilku przypadkach.
Tak 2211_3 daje liczbę 2020101 = 62d przy wartości uzyskanej 59d=2020001;
10211_3 daje 100020101 = 75d przy wartości uzyskanej 74d=100020100.
Kiedy przyglądałem się temu, zauważyłem niezwykłe podobieństwo do systemu trójkowego, Jest jednak drobna różnica. Przekształcam konwersjami postać:
0020200 = 0021001 = 0110001 = 1000001
Wypisuję co drugą cyfrę 0220 = 1001. I tu kryje się modyfikacja.
System Fibonacciego utożsamia ze sobą wszystkie postaci 220, 221, 222, 1000, 1001 systemu trójkowego. Gdy liczba kończy się na 22, ostatnie '01' jest ignorowane. Istotne tu są zwłaszcza te trzy z podciągiem '22', które praktycznie nie mają prawa wystąpić w systemie Fibonacciego.
Wyłączmy zatem n krotność 22_3=8d oraz iloczyn 5 z krotnością wystąpień '22x' dla wszystkich możliwych pozycji '22' w reprezentacji trójkowej.
Dodajmy do n te krotności i zapiszmy przybliżenie liczby w systemie trójkowym.
Np. 59 /8 = 7, 59/24*5 = 10, 59+7+10=76 = 2211_3;
74/8 = 9, 74/24*5 = 15, 74/72*5 = 5, 74+9+15+5 = 103 = 10211_3.
Rozpisując teraz uzyskane cyfry systemu trójkowego jako pary cyfr systemu Fibonacciego uzyskamy dosyć dobre przybliżenie wartości systemu Fibonacciego z nadmiarem, uzyskanego schematami z dzieleń [00300]=[100001]. Biorąc mnożnik 3 zamiast 5, uzyskamy przybliżenie z niedomiarem.
Jest to hipoteza, sprawdzona na kilku przypadkach.
Tak 2211_3 daje liczbę 2020101 = 62d przy wartości uzyskanej 59d=2020001;
10211_3 daje 100020101 = 75d przy wartości uzyskanej 74d=100020100.
17 lipca 2017
Dzielenie z pomocą systemu Fibonacciego
Sprawdzając możliwości systemu Fibonacciego zauważyłem możliwość zmniejszenia wartości dzielnej podczas dzielenia nie tylko na poszczególnych cyfrach, ale i na pozycjach.
Przykładowo dla liczby Fibonacciego
N = 101 010010 000100 101010 100100 010101F
chcemy znaleźć resztę z dzielenia przez 1087.
Dotychczas chciałem doprowadzić do liczby f zapisanej w systemie Fibonacciego, by na każdej pozycji była wartość 0 lub 2048 za wyjątkiem pozycji jedności, a następnie obliczyć f*(2048-1087)+f[0].
Ale można inaczej - wyznaczam wagi pozycji, sumując dwie wcześniejsze cyfry modulo dzielnik, tu 1087.
Uzyskam wtedy ciąg
... 485x 524 1048x 563 485x 78 407 758x 736 22 714 395 319x 76 243 920x 410 510x 987 610x 377 233x 144 89 55x 34 21 13 8x 5 3x 2 1x
koniec do 987 pokrywa się z liczbami Fibonacciego, dalej 987+610 = 1597 = 510 (1087). Zaznaczone x są pozycje ustawione w wartości Fibonacciego liczby N.
Suma oznaczonych pozycji jest równa 5435.
Liczba N jest podzielna przez 1087 gdy tak powstała liczba jest podzielna przez 1087, i mamy 5435 = 5*1087. Przekształcenie z N/1087 = 8219 zrobiło 5.
Kontynuując rekursywnie, jeśli dzielimy przez dzielnik bliższy liczbie, np. 5435 : 1087 uzyskamy wartość 2174.
Zatem mamy niezwykle mocne zmniejszenie wartości:
Liczba N zapisana w postaci Fibonacciego dzielona przez d sprowadza się do dzielenia przez N sumy liczb mniejszych niż d, których jest nie więcej niż połowa (+1 w najgorszym przypadku 101..0101) jedynek w liczbie N. Jest to bliskie 0,8 lg N ze złotego stosunku, czyli ewentualne rekursywne odwołania są tłumione wykładniczo.
Przekształcenie N do systemu Fibonacciego może być wykonane liniowo, współczynniki ciągu do sumowania też wyliczamy liniowo, korzystając podczas sumowania z ustawionych bitów liczby Fibonacciego N. Pozostaje jedno dzielenie, które wymaga znacznie mniej operacji niż pierwotne.
Szacuję na złożoność tego dzielenia pesymistycznie O(n lg n). Praktycznie szybsze ze względu na mniejsze wartości sumowane.
Przykładowo dla liczby Fibonacciego
N = 101 010010 000100 101010 100100 010101F
chcemy znaleźć resztę z dzielenia przez 1087.
Dotychczas chciałem doprowadzić do liczby f zapisanej w systemie Fibonacciego, by na każdej pozycji była wartość 0 lub 2048 za wyjątkiem pozycji jedności, a następnie obliczyć f*(2048-1087)+f[0].
Ale można inaczej - wyznaczam wagi pozycji, sumując dwie wcześniejsze cyfry modulo dzielnik, tu 1087.
Uzyskam wtedy ciąg
... 485x 524 1048x 563 485x 78 407 758x 736 22 714 395 319x 76 243 920x 410 510x 987 610x 377 233x 144 89 55x 34 21 13 8x 5 3x 2 1x
koniec do 987 pokrywa się z liczbami Fibonacciego, dalej 987+610 = 1597 = 510 (1087). Zaznaczone x są pozycje ustawione w wartości Fibonacciego liczby N.
Suma oznaczonych pozycji jest równa 5435.
Liczba N jest podzielna przez 1087 gdy tak powstała liczba jest podzielna przez 1087, i mamy 5435 = 5*1087. Przekształcenie z N/1087 = 8219 zrobiło 5.
Kontynuując rekursywnie, jeśli dzielimy przez dzielnik bliższy liczbie, np. 5435 : 1087 uzyskamy wartość 2174.
Zatem mamy niezwykle mocne zmniejszenie wartości:
Liczba N zapisana w postaci Fibonacciego dzielona przez d sprowadza się do dzielenia przez N sumy liczb mniejszych niż d, których jest nie więcej niż połowa (+1 w najgorszym przypadku 101..0101) jedynek w liczbie N. Jest to bliskie 0,8 lg N ze złotego stosunku, czyli ewentualne rekursywne odwołania są tłumione wykładniczo.
Przekształcenie N do systemu Fibonacciego może być wykonane liniowo, współczynniki ciągu do sumowania też wyliczamy liniowo, korzystając podczas sumowania z ustawionych bitów liczby Fibonacciego N. Pozostaje jedno dzielenie, które wymaga znacznie mniej operacji niż pierwotne.
Szacuję na złożoność tego dzielenia pesymistycznie O(n lg n). Praktycznie szybsze ze względu na mniejsze wartości sumowane.
01 lipca 2017
Konwersja do systemu Fibonacciego
W poście z 12 czerwca
Faktoryzacja oraz reszty z dzielenia w systemie Fibonacciego
wspomniałem o konieczności zamieniania liczby dowolnego systemu na system Fibonacciego. Ale pokazałem też przebieg który zwiększa cyfry, wstawiając na odpowiednich pozycjach potęgi 2. Ten schemat można odwrócić!
Dołączmy jeszcze jeden schemat do podanych w tamtym poście:
[0 0 2 0 0] = [0 1 0 0 1];
[0 0 3 0 0] = [1 0 0 0 1];
[0 0 4 0 0] = [1 0 1 0 1];
pominę przypadki brzegowe.
Teraz algorytm rekursywny w bardzo szybkiej pętli zmniejsza N aż 4 razy. Wewnątrz ma wolniejszy przebieg, gdyż wykorzystując schematy 'naprawia' liczbę do postaci Fibonacciego.
Oto ten przebieg, wykorzystujący postać N w systemie czwórkowym:
IN N_4
i = 2^k, 2^k < N < 2^(k+2), czyli i<N<4i;
F_0+R = F_0+N%i, liczba Fibonacciego F_0 z resztą R (reszta zawiera cyfry N poza najbardziej znaczącą, te najbardziej znaczące dodajemy do postaci F_i)
powtarzaj dopóki i>1
i /= 4;
F_i = 4*F_i +HIGH(R); // dodajemy najbardziej znaczącą cyfrę R
napraw F_i do systemu Fibonacciego;
OUT liczba w systemie Fibonacciego
Pomijając przekształcenia naprawiające liczbę, jest tu bardzo szybkie zchodzenie.
Przykład: N = 8934053d = 202011022211_4
Mamy N = 2^23 + 2011022211_4 = 2*2^22 + 545445, i = 2^22
F_0 = 10F z resztą 545445
i/=4, czyli naprawiamy liczbę [4 0+0]F = 10000F
następna iteracji zaczyna się od 40002 i kończy na
100 00000F z resztą 11022211_4 = 21157
Teraz jeden schemat działający na 400 00000 dostarcza
10101 00000F z tą samą resztą.
Kolejna naprawa 40404 00001 przekształca się do
101 00010 00100F z resztą 1022211_4 = 4773
I dalej:
1 00101 01000 10000F z resztą 22211_4 = 677
1001 00010 10100 01001F z tą samą resztą
10 00101 00100 01010 10010F z resztą 2211_4=165
10001 00000 00100 10010 00100F z resztą 211_4=37
100 00010 10100 00010 10100 10001F z resztą 11_4 = 5
1 00000 00100 01001 00100 10000 10000F z resztą 1_4 = 1
i ostatnie, gdyż mamy już i=2^2=4
101 01001 00001 00101 01010 01000 10101F, co jest wartością Fibonacciego liczby N.
wspomniałem o konieczności zamieniania liczby dowolnego systemu na system Fibonacciego. Ale pokazałem też przebieg który zwiększa cyfry, wstawiając na odpowiednich pozycjach potęgi 2. Ten schemat można odwrócić!
Dołączmy jeszcze jeden schemat do podanych w tamtym poście:
[0 0 2 0 0] = [0 1 0 0 1];
[0 0 3 0 0] = [1 0 0 0 1];
[0 0 4 0 0] = [1 0 1 0 1];
pominę przypadki brzegowe.
Teraz algorytm rekursywny w bardzo szybkiej pętli zmniejsza N aż 4 razy. Wewnątrz ma wolniejszy przebieg, gdyż wykorzystując schematy 'naprawia' liczbę do postaci Fibonacciego.
Oto ten przebieg, wykorzystujący postać N w systemie czwórkowym:
IN N_4
i = 2^k, 2^k < N < 2^(k+2), czyli i<N<4i;
F_0+R = F_0+N%i, liczba Fibonacciego F_0 z resztą R (reszta zawiera cyfry N poza najbardziej znaczącą, te najbardziej znaczące dodajemy do postaci F_i)
powtarzaj dopóki i>1
i /= 4;
F_i = 4*F_i +HIGH(R); // dodajemy najbardziej znaczącą cyfrę R
napraw F_i do systemu Fibonacciego;
OUT liczba w systemie Fibonacciego
Pomijając przekształcenia naprawiające liczbę, jest tu bardzo szybkie zchodzenie.
Przykład: N = 8934053d = 202011022211_4
Mamy N = 2^23 + 2011022211_4 = 2*2^22 + 545445, i = 2^22
F_0 = 10F z resztą 545445
i/=4, czyli naprawiamy liczbę [4 0+0]F = 10000F
następna iteracji zaczyna się od 40002 i kończy na
100 00000F z resztą 11022211_4 = 21157
Teraz jeden schemat działający na 400 00000 dostarcza
10101 00000F z tą samą resztą.
Kolejna naprawa 40404 00001 przekształca się do
101 00010 00100F z resztą 1022211_4 = 4773
I dalej:
1 00101 01000 10000F z resztą 22211_4 = 677
1001 00010 10100 01001F z tą samą resztą
10 00101 00100 01010 10010F z resztą 2211_4=165
10001 00000 00100 10010 00100F z resztą 211_4=37
100 00010 10100 00010 10100 10001F z resztą 11_4 = 5
1 00000 00100 01001 00100 10000 10000F z resztą 1_4 = 1
i ostatnie, gdyż mamy już i=2^2=4
101 01001 00001 00101 01010 01000 10101F, co jest wartością Fibonacciego liczby N.
13 czerwca 2017
Mix dzielenia pisemnego i przez zmianę podstaw
Swego czasu opublikowałem dzielenie przez zmianę podstaw. Przypomnę przebieg na przykładzie
N = 8934053 : 8, 10-8=2, iloraz d[] z resztą r, val oznacza wyliczoną wartość
d_5 = n_6 = 8;
d_{n-1} = 2*val a_{n+1} + a_n, n=5..0,
d_{-1} = 2*d_0+a_0 = 8*k+r
d_0 = d_0+k
czyli
8 9 3 4 0 5 3
8 25 53 110 220 445 893 = 8*111+5
Wynik uzyskujemy przez dziesiętne dodawanie ww wartości i przesunięcie o jedną pozycję, czyli
cyfra jedności (445+111)%10 = 556%10 = 6
cyfra dziesiątek (220+55)%10 = 275%10 = 5 itd.
cyfra 'najbardziej znacząca' (8+3)%10 = 11%10, pojawiła się dodatkowa cyfra.
Duże wartości, wydaje się, że dzielenie pisemne jest prostsze, gdyż 8:8=1, podobnie 9.
Liczbę N można rozbić na dwie: 8832048 + 102005, oraz porachować osobno: 1104006 + 102005:8. Użyjemy tego pomysłu do mixu, dla kolejnych cyfr.
Mix dzieleń polega na połączeniu obu metod przy przebiegu. Dzielimy w cyfrze przez 8, dopiero resztę mnożoną przez 2 dodajemy do cyfry mniej znaczącej. Cyfry są przesunięte o jedną pozycję. Poprawkę stanowią współczynniki przy 8.
A oto dokładny przebieg:
d_6 = 8 = 1*8+0 => 0
d_5 = (2*0+9) = 1*8+1 => 0
d_4 = (2*1+3) = 5 = 0*8+5 => 1
d_3 = (2*5+4) = 14 = 1*8+6 => 5
d_2 = (2*6+0) = 12 = 1*8+4 => 6
d_1 = (2*4+5) = 13 = 1*8+5 => 4
d_0 = (2*5+3) = 13 = 1*8+5 => 5
odczytujemy wynik
0 0 1 5 6 4 5 , 5 cyfry i reszta
1 1 0 1 1 1 1 poprawki
sumujemy poprawki
1 1 1 6 7 5 6, reszta 5
Pamiętając o poszczególnych cyfrach i poprawkach, uzyskujemy bardzo małe wartości jak przy dzieleniu pisemnym, zachowując prostotę obliczeń dzielenia przez zmianę systemów.
Dla większych dzielników możemy zastosować dzielenie chłopów rosyjskich, dzięki czemu wartości obrabiane nie będą nigdy większe niż kwadrat dzielnika.
12 czerwca 2017
Faktoryzacja oraz reszty z dzielenia w systemie Fibonacciego
System Fibonacciego zawiera na pozycjach cyfr zamiast potęg np. 10 liczby Fibonacciego przesunięte o 3 pozycje. Pozwala to uzyskać system zawierający tylko 0 i 1 oraz spełniający schemat
1) [1 0 0] = [0 1 1].
Liczba jest sumą dwu poprzednich, z których pierwsze są 0 i 1. W tym systemie pozycja jedności F_3=1.
Np. 9 = [1 0 0 0 1] = 1*8+0*5+0*3+0*2+1*1.
Na potrzeby faktoryzacji ignoruję fakt, że na każdej pozycji jest tylko 1 albo 0, dopuszczam dowolną naturalną wartość z zerem włącznie. Wtedy liczba w systemie Fibonacciego jest podzielna przez a, gdy jej zapis w systemie Fibonacciego M składa się tylko z a oraz zer. Gdy liczba nie jest podzielna przez a, resztę można umieścić w cyfrze najmniej znaczącej, np.
[3 0 3 0 4] = 3*8+0*5+3*3+0*2+4 = 3(8+3+1)+1 = 37
Dodawanie w systemie Fibonacciego sprowadza się do orowania cyfr, zaś gdy obie są ustawione, do mnożenia przez 2.
Szczególne przypadki cyfr najmniej znaczących (z definicji cyfr systemu):
[. 1 0 1] = [. 0 2 0] = 4
[. 0 1 0] = [. 0 0 2] = 2
Dla pozostałych pozycji mamy schematy, które się dodaje do aktualnych cyfr
2) [1 0 0 1] = [0 2 0 0]
3) [1 0 0 0 1] = [0 0 3 0 0]
Dowody
[1 0 0 1] = [0 1 1 1] = [0 1+1 0 0] = [0 2 0 0];
[1 0 0 0 1] = [0 1 1 0 1] = [0 0 2 1 1] = [0 0 2+1 0 0] = [0 0 3 0 0].
Pierwszy pomysł na faktoryzację z systemu Fibonacciego. Zapisuję liczbę N w tym systemie jako M_{}, następnie za pomocą uogólnień schematów 1) i 2)
[a 0 0] = [0 a a];
4) [a 0 0 a] = [0 2a 0 0]
przekształcam by uzyskać odpowiednią ustaloną wartość zamiast jedynek. np.
z liczby
[1 0 0 0 1 0 1 0 0 1]
można zrobić wartość podzielną przez 2
[0 0 3 0 0 0 0 2 0 0] = [3 0 0 0 0 2 0 0], przeniesienie reszty do cyfry jedności
[3 0 0 0 0 2 0 0] = [2 1 1 0 0 2 0 0] = [2 0 2 1 0 2 0 0] = [2 0 2 0 1 3 0 0] =
[2 0 2 0 0 4 1 0] = [2 0 2 0 0 2 3 2] = [2 0 2 0 0+2 0 1 2] = [2 0 2 0 2 0 0 4] =
[2 0 2 0 2 0 2 0]
lub przez 3:
[3 0 0 0 0 2 0 0] = [3 0 0 0 0 0 2 2] = [3 0 0 0 0 0 3 0]
Ale jak widać w przykładzie, występują nawroty. Zwłaszcza kłopotliwe są fragmenty [. a b 0 a .]
Zatem drugi pomysł. Chcąc uzyskać resztę z przedziału (2^(i-1), 2^i], przekształcamy liczbę do postaci Fibonacciego M_i tak, by zamiast jedynek były liczby 2^i, podwajając cyfry z pomocą 4)
[1 0 0 0 1 0 1 0 0 1] = [0 1 1 0 1 0 1 0 0 1] = [0 0 2+1 0 0 0 1 0 0 1] =
[2 1 1 0 1 0 0 1] = [2 0 2+1 0 0 0 0 1] = [2 0 2 1 1 0 0 1] = [2 0 2 0 2 1 0 1] =
[2 0 2 0 2 0 1 2] = [2 0 2 0 2 0 2 0] = (M_1)
[2 0 0 2 4 0 2 0] = [0 4 0 0 4 0 2 0] = [4 0 0 4 0 0 4] = (M_2)
[0 8 0 0 0 0 4] (M_3)
Jest to liniowe i nie ma nawrotów.
Jeśli teraz chcemy znaleźć resztę przez d<2^i, jest ona równa iloczynowi postaci
M_i *(2^i - d) + r ,
gdzie r jest resztą (cyfra jedności M_i lub M_i-2^i, gdy M_i ma ustawioną tę cyfrę ).
Ten drugi sposób jest dowodem na cechę podzielności przez d w systemie.
I znowu, działania na dużej liczbie zostały zastąpione działaniami na znacznie mniejszych, gdyż M_{i+1} ma co najmniej dwie cyfry mniej niż M_i, 2^i-d<2^{i-1), zaś reszta też jest mniejsza niż 2^{i-1}.
Pozostaje sposób konwersji N na postać Fibonacciego M_0. Chyba najbardziej opłacalny jest klasyczny szukania największej liczby Fibonacciego F_k nie większej niż N i odejmowanie. Jeśli chcemy zmniejszać N wcześniej, możemy odejmować kolejne liczby Fibonacciego, a kiedy F_k >N-\sum{F_{i<k}}, odejmujemy jeszcze 2, razem zostało odjęte F_{k+2}.
Wynika to z przekształceń
[1 1 . . . 1 1] = [1 0 1 . . . 0 1 0 0] lub [1 0 1 . . . 1 0 0 1]
w zależności od liczności jedynek. Uzyskane ciągi mają dokładnie jedną pozycję więcej. Brakuje dokładnie 2, by cały ten ciąg używając 1) stał się kolejną liczbą Fibonacciego, zyskując dodatkową pozycję. Z programowania dynamicznego lub rekursji ustawiamy kolejne jedynki M_0.
1) [1 0 0] = [0 1 1].
Liczba jest sumą dwu poprzednich, z których pierwsze są 0 i 1. W tym systemie pozycja jedności F_3=1.
Np. 9 = [1 0 0 0 1] = 1*8+0*5+0*3+0*2+1*1.
Na potrzeby faktoryzacji ignoruję fakt, że na każdej pozycji jest tylko 1 albo 0, dopuszczam dowolną naturalną wartość z zerem włącznie. Wtedy liczba w systemie Fibonacciego jest podzielna przez a, gdy jej zapis w systemie Fibonacciego M składa się tylko z a oraz zer. Gdy liczba nie jest podzielna przez a, resztę można umieścić w cyfrze najmniej znaczącej, np.
[3 0 3 0 4] = 3*8+0*5+3*3+0*2+4 = 3(8+3+1)+1 = 37
Dodawanie w systemie Fibonacciego sprowadza się do orowania cyfr, zaś gdy obie są ustawione, do mnożenia przez 2.
Szczególne przypadki cyfr najmniej znaczących (z definicji cyfr systemu):
[. 1 0 1] = [. 0 2 0] = 4
[. 0 1 0] = [. 0 0 2] = 2
Dla pozostałych pozycji mamy schematy, które się dodaje do aktualnych cyfr
2) [1 0 0 1] = [0 2 0 0]
3) [1 0 0 0 1] = [0 0 3 0 0]
Dowody
[1 0 0 1] = [0 1 1 1] = [0 1+1 0 0] = [0 2 0 0];
[1 0 0 0 1] = [0 1 1 0 1] = [0 0 2 1 1] = [0 0 2+1 0 0] = [0 0 3 0 0].
Pierwszy pomysł na faktoryzację z systemu Fibonacciego. Zapisuję liczbę N w tym systemie jako M_{}, następnie za pomocą uogólnień schematów 1) i 2)
[a 0 0] = [0 a a];
4) [a 0 0 a] = [0 2a 0 0]
przekształcam by uzyskać odpowiednią ustaloną wartość zamiast jedynek. np.
z liczby
[1 0 0 0 1 0 1 0 0 1]
można zrobić wartość podzielną przez 2
[0 0 3 0 0 0 0 2 0 0] = [3 0 0 0 0 2 0 0], przeniesienie reszty do cyfry jedności
[3 0 0 0 0 2 0 0] = [2 1 1 0 0 2 0 0] = [2 0 2 1 0 2 0 0] = [2 0 2 0 1 3 0 0] =
[2 0 2 0 0 4 1 0] = [2 0 2 0 0 2 3 2] = [2 0 2 0 0+2 0 1 2] = [2 0 2 0 2 0 0 4] =
[2 0 2 0 2 0 2 0]
lub przez 3:
[3 0 0 0 0 2 0 0] = [3 0 0 0 0 0 2 2] = [3 0 0 0 0 0 3 0]
Ale jak widać w przykładzie, występują nawroty. Zwłaszcza kłopotliwe są fragmenty [. a b 0 a .]
Zatem drugi pomysł. Chcąc uzyskać resztę z przedziału (2^(i-1), 2^i], przekształcamy liczbę do postaci Fibonacciego M_i tak, by zamiast jedynek były liczby 2^i, podwajając cyfry z pomocą 4)
[1 0 0 0 1 0 1 0 0 1] = [0 1 1 0 1 0 1 0 0 1] = [0 0 2+1 0 0 0 1 0 0 1] =
[2 1 1 0 1 0 0 1] = [2 0 2+1 0 0 0 0 1] = [2 0 2 1 1 0 0 1] = [2 0 2 0 2 1 0 1] =
[2 0 2 0 2 0 1 2] = [2 0 2 0 2 0 2 0] = (M_1)
[2 0 0 2 4 0 2 0] = [0 4 0 0 4 0 2 0] = [4 0 0 4 0 0 4] = (M_2)
[0 8 0 0 0 0 4] (M_3)
Jest to liniowe i nie ma nawrotów.
Jeśli teraz chcemy znaleźć resztę przez d<2^i, jest ona równa iloczynowi postaci
M_i *(2^i - d) + r ,
gdzie r jest resztą (cyfra jedności M_i lub M_i-2^i, gdy M_i ma ustawioną tę cyfrę ).
Ten drugi sposób jest dowodem na cechę podzielności przez d w systemie.
I znowu, działania na dużej liczbie zostały zastąpione działaniami na znacznie mniejszych, gdyż M_{i+1} ma co najmniej dwie cyfry mniej niż M_i, 2^i-d<2^{i-1), zaś reszta też jest mniejsza niż 2^{i-1}.
Pozostaje sposób konwersji N na postać Fibonacciego M_0. Chyba najbardziej opłacalny jest klasyczny szukania największej liczby Fibonacciego F_k nie większej niż N i odejmowanie. Jeśli chcemy zmniejszać N wcześniej, możemy odejmować kolejne liczby Fibonacciego, a kiedy F_k >N-\sum{F_{i<k}}, odejmujemy jeszcze 2, razem zostało odjęte F_{k+2}.
Wynika to z przekształceń
[1 1 . . . 1 1] = [1 0 1 . . . 0 1 0 0] lub [1 0 1 . . . 1 0 0 1]
w zależności od liczności jedynek. Uzyskane ciągi mają dokładnie jedną pozycję więcej. Brakuje dokładnie 2, by cały ten ciąg używając 1) stał się kolejną liczbą Fibonacciego, zyskując dodatkową pozycję. Z programowania dynamicznego lub rekursji ustawiamy kolejne jedynki M_0.
13 maja 2017
Reszta z dzielenia wstecz - poprawka
Opisałem przekształcenie przekształcające postacie binarne, a okazało się, że zastosowanie zwykłego odejmowania jest równie proste i skuteczne.
Chciałem uzyskać binarny wynik z dzielenia przez liczbę. W tym celu potrzebowałem binarnej postaci dzielenia przez pobliską liczbę - nie jest ona potrzebna.
Aby uzyskać binarną postać ilorazu liczb nieparzystych przy dzieleniu wstecz a/p wystarczy odjąć dzielnik i podzielić przez 2. Wpisujemy 1. Jeśli uzyskana wartość jest parzysta wpisujemy 0 i znów dzielimy przez 2. Kończymy gdy wartość
b= (a-p)/2 or a/2
jest mniejsza niż dzielnik. Postać ta sama: b*2^m, gdzie m jest bliska krotności cyfr binarnych dzielnika
Ciąg zer i jedynek w odwrotnej kolejności jest ilorazem z dzielenia wstecz, o ile zadziała. W przeciwnym razie daje mniejszą wartość.
Na razie nie widzę, czy reszta przy dzieleniu wstecz zachowuje się w sposób równie przewidywalny jak reszta z dzielenia zwykłego, na pewno nie dla małych i średnich wartości, chociaż występuje tendencja do zmniejszania wartości binarnych, niestety, ciągle zasilana z reszty odbudowującej się blisko potęg 2.
Jeśli chcę uzyskać wynik w innym systemie liczenia, z tabliczki mnożenia szukam cyfry c, by
a%p = c*p (p)
oraz od liczby a odejmuję c*p wypisując cyfrę c, np. w dziesiątkowym 323 : 17, c=9, bo 9*7 = 3 (10), odejmujemy 9*17 = 153.
Najlepiej to robić w systemach z jednoznacznie wyznaczoną cyfrą, np. jedenastkowym. Zwykła rzecz przy dzieleniu wstecz...
Chciałem uzyskać binarny wynik z dzielenia przez liczbę. W tym celu potrzebowałem binarnej postaci dzielenia przez pobliską liczbę - nie jest ona potrzebna.
Aby uzyskać binarną postać ilorazu liczb nieparzystych przy dzieleniu wstecz a/p wystarczy odjąć dzielnik i podzielić przez 2. Wpisujemy 1. Jeśli uzyskana wartość jest parzysta wpisujemy 0 i znów dzielimy przez 2. Kończymy gdy wartość
b= (a-p)/2 or a/2
jest mniejsza niż dzielnik. Postać ta sama: b*2^m, gdzie m jest bliska krotności cyfr binarnych dzielnika
Ciąg zer i jedynek w odwrotnej kolejności jest ilorazem z dzielenia wstecz, o ile zadziała. W przeciwnym razie daje mniejszą wartość.
Na razie nie widzę, czy reszta przy dzieleniu wstecz zachowuje się w sposób równie przewidywalny jak reszta z dzielenia zwykłego, na pewno nie dla małych i średnich wartości, chociaż występuje tendencja do zmniejszania wartości binarnych, niestety, ciągle zasilana z reszty odbudowującej się blisko potęg 2.
Jeśli chcę uzyskać wynik w innym systemie liczenia, z tabliczki mnożenia szukam cyfry c, by
a%p = c*p (p)
oraz od liczby a odejmuję c*p wypisując cyfrę c, np. w dziesiątkowym 323 : 17, c=9, bo 9*7 = 3 (10), odejmujemy 9*17 = 153.
Najlepiej to robić w systemach z jednoznacznie wyznaczoną cyfrą, np. jedenastkowym. Zwykła rzecz przy dzieleniu wstecz...
22 kwietnia 2017
Reszta z dzielenia wstecz
Ostatnie kilka miesięcy poświęciłem na sposoby usuwania nieoznaczoności przy znajdywaniu dzielników. Zmiany systemów pozwalają znajdować dokładnie cyfry, o ile uda nam się w jakiś sposób znaleźć krotność cyfr dzielników. W przeciwnym razie pojawia się nieoznaczoność. Sprawdzanie zapisów liczb w różnych systemach do pewnego miejsca działa dobrze, ale nie wiadomo, jak długo.
Zwłaszcza występujące przeniesienia wartości między kolejnymi cyframi bardzo przeszkadzają.
Wróciłem do trial division, tym razem jednak zdecydowałem, że reszta z dzielenia przez p będzie przy cyfrze najbardziej znaczącej. Budowa reszty w systemie binarnym jest następująca:
r = a*2^m
gdzie m+1 jest krotnością cyfr kandydata na dzielnik b, czyli
N = r + b*p, log_2 b = m+1
Używam dzielenia wstecz, rzadko działającego, w którym iloraz znajdujemy od cyfr najmniej znaczących.
Przekształcenie badane przechodzi między dzielnikami nieparzystymi p i q za pomocą przeniesień. Dodatkowo, znaleziony sposób jest liniowy, w którym występują dodawania, odejmowania i czasem mnożenie przez 2 lub 3. Zatem przekształcenie jest liniowe. Co więcej, w odróżnieniu od opublikowanego już algorytmu zmiany podstaw, przekształcenie pozostaje liniowe dla q-p<p.
Czynnością generującą najwięcej pomyłek obliczeniowych dla człowieka jest dbanie o poprawność przeniesień. Reszta to proste działania.
Przykład N = 8934053, reszta z dzielenia przez 59 jest (hexadecymalnie)
N = 38*2^16 + 59*0x1AA9F
Znalezione przekształcenie modyfikuje 0x1AA9F próbując pobrać przy ustawionym bicie i*59 wartość 61, a następnie zależnie od parzystości wyniku albo zeruje, albo ustawia bit i w ilorazie N / 61. Możemy to traktować jako liczbę binarną, stosując dodatkową zmienną interpretującą ustawione bity jako 59, które parzyste przenoszą wcześniej połowę wartości, zaś nieparzyste wykorzystując pożyczki odejmują 61 od wartości też przenosząc wcześniej połowę parzystej różnicy. Reszta nie może być traktowana jako iloczyn 59*i, ale dla przebiegu to i tak ma niewielkie znaczenie. Uzyskujemy nową resztę 69*2^16, zaś postać liczby ulega zmianie do
69*2^16 + 61*0x11A89
Powstała postać binarna jest najlepiej dopasowana do nowej wartości, co dzieje się automatycznie.
Jak to przebiega szczegółowo. Końcówka
1 1 1 1 oznacza 59 59 59 59.
Chcemy zabrać 61 od ostatniego 59, ale nie można. Zatem pożyczamy 1 1 = 0 3 uzyskując postać
1 1 0 3 czyli 59 59 0 183
Od 183 odejmujemy 61 i dzielimy przez 2 uzyskując 58. Wartość parzysta zeruje bit w tablicy ? ? 0 1. Przenosząc na kolejną wcześniejszą pozycję mamy
58/2+1*59 = 88.
Kolejna pozycja to 88/2+59 = 103, nieparzysta, stąd dla tabeli przy 61 mamy ostatnie bity 1 0 0 1.
Jeśli na danej pozycji wartość nieparzysta jest mniejsza niż q, pożyczamy.
Końcówka, na pozycji 2^16 mamy 59+38, z przeniesień dodajemy 33 uzyskując 61+69. Wartość 61 to bit w tablicy ewentualnego dzielnika, zaś 69 reszta.
Z dzielnikiem mamy do czynienia, gdy reszta jest równa 0.
Jeśli poprawnie uda się pobierać pożyczki z binarnych cyfr wcześniejszych, możemy zapamiętując tylko wielokrotność a, tablicę (liczba binarna) ewentualnego ilorazu i dzielnej p, przekształcając je liniowo.
Wtedy algorytm faktoryzacji szacuję na O() = n log n.
Zwłaszcza występujące przeniesienia wartości między kolejnymi cyframi bardzo przeszkadzają.
Wróciłem do trial division, tym razem jednak zdecydowałem, że reszta z dzielenia przez p będzie przy cyfrze najbardziej znaczącej. Budowa reszty w systemie binarnym jest następująca:
r = a*2^m
gdzie m+1 jest krotnością cyfr kandydata na dzielnik b, czyli
N = r + b*p, log_2 b = m+1
Używam dzielenia wstecz, rzadko działającego, w którym iloraz znajdujemy od cyfr najmniej znaczących.
Przekształcenie badane przechodzi między dzielnikami nieparzystymi p i q za pomocą przeniesień. Dodatkowo, znaleziony sposób jest liniowy, w którym występują dodawania, odejmowania i czasem mnożenie przez 2 lub 3. Zatem przekształcenie jest liniowe. Co więcej, w odróżnieniu od opublikowanego już algorytmu zmiany podstaw, przekształcenie pozostaje liniowe dla q-p<p.
Czynnością generującą najwięcej pomyłek obliczeniowych dla człowieka jest dbanie o poprawność przeniesień. Reszta to proste działania.
Przykład N = 8934053, reszta z dzielenia przez 59 jest (hexadecymalnie)
N = 38*2^16 + 59*0x1AA9F
Znalezione przekształcenie modyfikuje 0x1AA9F próbując pobrać przy ustawionym bicie i*59 wartość 61, a następnie zależnie od parzystości wyniku albo zeruje, albo ustawia bit i w ilorazie N / 61. Możemy to traktować jako liczbę binarną, stosując dodatkową zmienną interpretującą ustawione bity jako 59, które parzyste przenoszą wcześniej połowę wartości, zaś nieparzyste wykorzystując pożyczki odejmują 61 od wartości też przenosząc wcześniej połowę parzystej różnicy. Reszta nie może być traktowana jako iloczyn 59*i, ale dla przebiegu to i tak ma niewielkie znaczenie. Uzyskujemy nową resztę 69*2^16, zaś postać liczby ulega zmianie do
69*2^16 + 61*0x11A89
Powstała postać binarna jest najlepiej dopasowana do nowej wartości, co dzieje się automatycznie.
Jak to przebiega szczegółowo. Końcówka
1 1 1 1 oznacza 59 59 59 59.
Chcemy zabrać 61 od ostatniego 59, ale nie można. Zatem pożyczamy 1 1 = 0 3 uzyskując postać
1 1 0 3 czyli 59 59 0 183
Od 183 odejmujemy 61 i dzielimy przez 2 uzyskując 58. Wartość parzysta zeruje bit w tablicy ? ? 0 1. Przenosząc na kolejną wcześniejszą pozycję mamy
58/2+1*59 = 88.
Kolejna pozycja to 88/2+59 = 103, nieparzysta, stąd dla tabeli przy 61 mamy ostatnie bity 1 0 0 1.
Jeśli na danej pozycji wartość nieparzysta jest mniejsza niż q, pożyczamy.
Końcówka, na pozycji 2^16 mamy 59+38, z przeniesień dodajemy 33 uzyskując 61+69. Wartość 61 to bit w tablicy ewentualnego dzielnika, zaś 69 reszta.
Z dzielnikiem mamy do czynienia, gdy reszta jest równa 0.
Jeśli poprawnie uda się pobierać pożyczki z binarnych cyfr wcześniejszych, możemy zapamiętując tylko wielokrotność a, tablicę (liczba binarna) ewentualnego ilorazu i dzielnej p, przekształcając je liniowo.
Wtedy algorytm faktoryzacji szacuję na O() = n log n.
04 stycznia 2017
Przekształcenie np. z systemu binarnego na dziesiątkowy i odwrotnie
Konwersje z systemu o podstawie p na p*q generują proste przekształcenia, które można zastosować np. na przekształcenie z systemu binarnego na dziesiątkowy i odwrotnie. Wykorzystywana jest konwersja
a_n(p^n q^n) + ... + a_1 (p*q) + a_0 = q^n a_n * p^n + ... + q a_1 *p + a_0 .
Czyli potęgi q są w podstawie, a po drugiej stronie w 'cyfrach'.
Korzystamy cały czas z założenia, że tymczasowo na miejscu cyfr stoją liczby. Następnie przeniesieniami 'naprawiamy' liczbę.
Mając liczbę [a_n ... a_0] w systemie o podstawie p, z każdej cyfry a_i wyłączamy wielokrotność q
a_i = b_i*q+c
wstawiając w miejsce a_i wartość b_i (dzieląc po prostu zmodyfikowaną wartość a_i przez q). Resztę c przy i dodatnim przenosimy do 'cyfry' mniej znaczącej
a_{i-1} = a_{i-1}+p*c.
Dla i=0 zostawiamy - jest to cyfra w systemie o podstawie p*q.
Do 'liczby' [b_n ... b_1] stosujemy rekursję. Cyfra najmniej znacząca nie jest brana pod uwagę aż do powrotu z rekursji.
Przykład. Przedstawić 1000 0010b w dziesiątkowym.
Mamy p=2, q=5, zatem przy przenoszeniu pozostawiamy piątki. Bardzo szczegółowo:
2 0 0 0 0 1 0
4 0 0 0 1 0
5+3 0 0 1 0
5 5+1 0 1 0
5 5 2 1 0
5 5 0 5 0
5 5 0 5 0
cyfra najmniej znacząca 0, liczbę b = [1 1 0 1] poddajemy rekursji:
1 1 0 1
5 3
Następną cyfrą jest 3, i uzyskujemy ciąg jednoelementowy, który daje najbardziej znaczącą cyfrę 1.
Wracamy uzyskując 1000 0010b = 130.
Jeśli chcemy liczbę z systemu o podstawie p*q przedstawić w systemie o podstawie p, odcinamy cyfrę najmniej znaczącą, po czym mnożymy przez q. Następnie stosujemy rekursję do wyniku póki liczba nie 'zniknie' i 'naprawiamy'.
Przykład. przedstawić dziesiątkowe 128 w piątkowym.
Ponieważ 10=2*5, mnożymy cyfry przez 2 po odcięciu cyfry najmniej znaczącej 8:
2 4
Rekursja po odcięciu 4:
4
Powrót: 4 4 8
Naprawa: 4 4 8 => 1 0 0 3, czyli 128 = 1003_5. Zgadza się, 128 = 5^3+3.
Przekształcenia te mogą być pomocne przy moim ostatnim pomyśle na faktoryzację, w którym znajduję własności dzielników liczby nie znając tychże. Na razie go nie upubliczniam, w metodzie porównuję zbiory rozwiązań bardzo prostych kongruencji nieliniowych.
a_n(p^n q^n) + ... + a_1 (p*q) + a_0 = q^n a_n * p^n + ... + q a_1 *p + a_0 .
Czyli potęgi q są w podstawie, a po drugiej stronie w 'cyfrach'.
Korzystamy cały czas z założenia, że tymczasowo na miejscu cyfr stoją liczby. Następnie przeniesieniami 'naprawiamy' liczbę.
Mając liczbę [a_n ... a_0] w systemie o podstawie p, z każdej cyfry a_i wyłączamy wielokrotność q
a_i = b_i*q+c
wstawiając w miejsce a_i wartość b_i (dzieląc po prostu zmodyfikowaną wartość a_i przez q). Resztę c przy i dodatnim przenosimy do 'cyfry' mniej znaczącej
a_{i-1} = a_{i-1}+p*c.
Dla i=0 zostawiamy - jest to cyfra w systemie o podstawie p*q.
Do 'liczby' [b_n ... b_1] stosujemy rekursję. Cyfra najmniej znacząca nie jest brana pod uwagę aż do powrotu z rekursji.
Przykład. Przedstawić 1000 0010b w dziesiątkowym.
Mamy p=2, q=5, zatem przy przenoszeniu pozostawiamy piątki. Bardzo szczegółowo:
2 0 0 0 0 1 0
4 0 0 0 1 0
5+3 0 0 1 0
5 5+1 0 1 0
5 5 2 1 0
5 5 0 5 0
5 5 0 5 0
cyfra najmniej znacząca 0, liczbę b = [1 1 0 1] poddajemy rekursji:
1 1 0 1
5 3
Następną cyfrą jest 3, i uzyskujemy ciąg jednoelementowy, który daje najbardziej znaczącą cyfrę 1.
Wracamy uzyskując 1000 0010b = 130.
Jeśli chcemy liczbę z systemu o podstawie p*q przedstawić w systemie o podstawie p, odcinamy cyfrę najmniej znaczącą, po czym mnożymy przez q. Następnie stosujemy rekursję do wyniku póki liczba nie 'zniknie' i 'naprawiamy'.
Przykład. przedstawić dziesiątkowe 128 w piątkowym.
Ponieważ 10=2*5, mnożymy cyfry przez 2 po odcięciu cyfry najmniej znaczącej 8:
2 4
Rekursja po odcięciu 4:
4
Powrót: 4 4 8
Naprawa: 4 4 8 => 1 0 0 3, czyli 128 = 1003_5. Zgadza się, 128 = 5^3+3.
Przekształcenia te mogą być pomocne przy moim ostatnim pomyśle na faktoryzację, w którym znajduję własności dzielników liczby nie znając tychże. Na razie go nie upubliczniam, w metodzie porównuję zbiory rozwiązań bardzo prostych kongruencji nieliniowych.
11 listopada 2016
'trial division' algorytm w jeszcze innej odsłonie
Tym razem, po długiej przerwie, kolejny algorytm 'trial division' na rozkład liczby N na czynniki. Jak moje najnowsze podejścia, znów jest prosty dla bardzo dużych wartości, zaś daje w kość dla małych dzielników.
Przedstawiam liczbę N w postaci iloczynu dwu wartości p, q i reszty r:
N = p*q + r,
gdzie p>q są liczbami nieparzystymi, r jest liczbą nieujemną, zmniejszaną by nie przekraczała podwojonego q.
Podstawowym przekształceniem jest
(p+k)*(q-k) = pq + k(q-p) - k^2 (1) ,
albo w używanej postaci szczególnej
(p+2)*(q-2) = pq - 2(p-q) - 4 (2) .
Inicjacja następuje dla nieparzystych p = q < sqrt(N) lub p < sqrt N < q = p+2 gdy sqrt N jest parzyste. Liczba
r = N - pq
jest parzysta.
W kolejnych iteracjach wykorzystujemy stary iloczyn pq by dostać nowe r następująco:
p = p+2;
q = q-2;
s = r + 2(p-q) + 4;
r = s (mod 2q); // s można zapamiętać by mniej liczyć
p = p+ floor( s/ 2q );
jeśli r =0, dzielnikami są p i q.
niezmienniki: p, q nieparzyste, z r zabierana parzysta wielokrotność q, która jest dodawana do p.
W ten sposób p rośnie wykładniczo, zwłaszcza dla małych q, q maleje liniowo. Zmiany są bardzo małe, zwłaszcza dla q mniejszych niż pierwiastek sześcienny z 2N. Z kolei dla q mniejszych efekt wykładniczy modyfikuje p bardzo silnie.
W praktyce przeważająca krotność przypadków przypada na małe zmiany.
Do tego stopnia zmiany są małe, że dla dużych q możemy korzystać ze cech podzielności dla q i korzystając z (1) przeskakiwać nie po kolejnych nieparzystych, ale wybierać te, które nie mają dzielników 3, 5. Podobna zakusa istnieje też dla p, ale tylko dla tak dużych wartości, by p/q <2.
Przykład: fragment
sqrt 8934053 jest bliskie 2988
p = 2989, q = 2987, r = 5910
różnica 2(p-q)+4 = 8, zatem
p = 2991, q = 2985, r = 5918
jeszcze dwa razy i mamy
p = 2997, q = 2979, r = 5990 = 2*2979+32,
za duże r, dochodzi do głosu dzielenie r/ 2q , zatem uzyskujemy zwiększenie p:
p = 2999, q = 2979, r = 32
przy kolejnym zmniejszaniu q przenoszenia do p występują coraz częściej, aż od
p = 4169+2, q = 2141, r = 2*2141+3942
stają się powszechne
dochodzimy w pobliże dzielnika,
p = 8189+14 = 8203, q = 1089, r = 14*1089+986
p = 8205+14 = 8219, q = 1087, r = 14*1087
p = 8221+12 = 8233, q = 1085, r = 12*1085+1248
poczynając od wartości
p = 33971+258, q = 261, r = 258*261+284
lepiej zmienić algorytm. Tu już q jest stosunkowo bardzo małe względem p.
Przedstawiam liczbę N w postaci iloczynu dwu wartości p, q i reszty r:
N = p*q + r,
gdzie p>q są liczbami nieparzystymi, r jest liczbą nieujemną, zmniejszaną by nie przekraczała podwojonego q.
Podstawowym przekształceniem jest
(p+k)*(q-k) = pq + k(q-p) - k^2 (1) ,
albo w używanej postaci szczególnej
(p+2)*(q-2) = pq - 2(p-q) - 4 (2) .
Inicjacja następuje dla nieparzystych p = q < sqrt(N) lub p < sqrt N < q = p+2 gdy sqrt N jest parzyste. Liczba
r = N - pq
jest parzysta.
W kolejnych iteracjach wykorzystujemy stary iloczyn pq by dostać nowe r następująco:
p = p+2;
q = q-2;
s = r + 2(p-q) + 4;
r = s (mod 2q); // s można zapamiętać by mniej liczyć
p = p+ floor( s/ 2q );
jeśli r =0, dzielnikami są p i q.
niezmienniki: p, q nieparzyste, z r zabierana parzysta wielokrotność q, która jest dodawana do p.
W ten sposób p rośnie wykładniczo, zwłaszcza dla małych q, q maleje liniowo. Zmiany są bardzo małe, zwłaszcza dla q mniejszych niż pierwiastek sześcienny z 2N. Z kolei dla q mniejszych efekt wykładniczy modyfikuje p bardzo silnie.
W praktyce przeważająca krotność przypadków przypada na małe zmiany.
Do tego stopnia zmiany są małe, że dla dużych q możemy korzystać ze cech podzielności dla q i korzystając z (1) przeskakiwać nie po kolejnych nieparzystych, ale wybierać te, które nie mają dzielników 3, 5. Podobna zakusa istnieje też dla p, ale tylko dla tak dużych wartości, by p/q <2.
Przykład: fragment
sqrt 8934053 jest bliskie 2988
p = 2989, q = 2987, r = 5910
różnica 2(p-q)+4 = 8, zatem
p = 2991, q = 2985, r = 5918
jeszcze dwa razy i mamy
p = 2997, q = 2979, r = 5990 = 2*2979+32,
za duże r, dochodzi do głosu dzielenie r/ 2q , zatem uzyskujemy zwiększenie p:
p = 2999, q = 2979, r = 32
przy kolejnym zmniejszaniu q przenoszenia do p występują coraz częściej, aż od
p = 4169+2, q = 2141, r = 2*2141+3942
stają się powszechne
dochodzimy w pobliże dzielnika,
p = 8189+14 = 8203, q = 1089, r = 14*1089+986
p = 8205+14 = 8219, q = 1087, r = 14*1087
p = 8221+12 = 8233, q = 1085, r = 12*1085+1248
poczynając od wartości
p = 33971+258, q = 261, r = 258*261+284
lepiej zmienić algorytm. Tu już q jest stosunkowo bardzo małe względem p.
27 czerwca 2016
Czy istnieje logarytmiczny sposób rozkładu liczb
Czy istnieje sposób rozkładu liczb, w którym kolejne obliczenia wyznaczają kolejne cyfry dzielników?
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
Wydaje się to niemożliwe dzięki przeniesieniom.
Lecz testuję pewien sposób dzielenia, który w dziesiątkowym działa w znikomej krotności przypadków, i on jest w stanie to ominąć.
Według jednego z pomysłów należałoby zbadać wykładniczą liczność przypadków dopasowania cyfr. Badane dzielenie wyłuskuje prostą zależność między cyframi dzielników, które ogranicza tę liczność. Dodatkowy test wyznacza konkretne cyfry, zwłaszcza kiedy w trakcie przebiegu zostanie złamana symetria.
Występuje nieoznaczoność, gdyż teoretycznie dostaję 2 wartości dla liczb pierwszych, co najmniej 4 dla złożonych. Są one symetryczne, i ta symetria nie pozwala przewidywać dokładnie. Jednak większość przypadków po złamaniu symetrii jestem w stanie wyznaczać jednoznacznie. Łamanie symetrii następuje tuż po pierwszym wystąpieniu pary różnych cyfr.
Dla wygody rachuję w binarnym. Wtedy dzielenie zwraca wielomian postaci np.
a+b+[0]^*+[1]^* = 1
z dwoma niewiadomymi. Zapis [0]^* oznacza, że dodawane jest kilka zer, ale nie muszą wystąpić. Po uproszczeniu mamy a+b=1 lub a+b=0, gdzie a i b są cyframi binarnymi, dopisywanymi do kandydatów na dzielniki.
Drugi z testów jest związany z parzystością różnicy liczby rozkładanej i iloczynu cząstkowego znajdowanych kandydatów na dzielniki.
29 maja 2016
Zmniejszenie krotności przypadków dla bardzo dużych liczb, poprawka
Wspomniany w styczniu sposób zmniejszania krotności nie jest tak dobry, jak początkowo uważałem.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
Przetestowałem kilka sposobów dla postaci
N = ap^2 + bp +c
1) trzymam jak najwięcej w a, dopasowuję skok k by c-bk > p
mamy pierwiastek sześcienny przypadków, a początkowo błyskawicznie maleje, po przekroczeniu p > root[3] N wartość a zmniejsza się o 1 na każde obliczenie.
Jednak istnieje duże ryzyko chybienia dzielników. Podczas testu wykryłem dzielnik tylko dlatego, że go znałem, i w odpowiednim miejscu zastosowałem cechę podzielności. Było bardzo blisko.
2) Jak największe b, a=1
Nie różni się licznością przypadków od 'trial division' przez kolejne liczby nieparzyste.
3) c jest kwadratem dużych wartości, bez nawrotów przy zmniejszaniu a (by zastosować (sqrt a *p+c)^2 +/- bp )
Szybkie zmniejszanie a i c, ale wartość w c za szybko stała się na tyle mała, że sposób przekształcił się w standardowe konwersje o 2.
Myślałem, że jest możliwość sprawdzania równocześnie małych i dużych dzielników, ale do tego trzeba nawrotów, tzn. przenoszenia wartości z a do c i obliczanie kolejny raz dużych kwadratów.
Wnioski. Dla dzielników mniejszych niż pierwiastek sześcienny root[3] {6N} i tak się stosuje konwersje o 2. Dla dzielników większych, a jest na tyle małe, że b zaczyna dominować nad zmianami c. Duże b pociąga znów konwersję o 2.
Zmiany c przy ustalonych a, b i wolno rosnącym p to funkcja kwadratowa z wierzchołkiem w środku przedziału, zatem trudno jest dopasować skoki poza zboczem rosnącym.
Zatem nie uda się zmniejszyć liczności przypadków sprawdzanych do pierwiastka sześciennego.
25 stycznia 2016
Zmniejszenie krotności przypadków rozkładu dla bardzo dużych liczb
Ten pomysł nie jest najlepszy obliczeniowo, ale w pobliżu pierwiastka z liczby rzadko natrafia się na dzielniki. Znalazłem sposób zmniejszenia krotności przypadków, szacuję, że nawet do pierwiastka sześciennego z rozkładanej liczby. Ale koszt jest duży.
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];
Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k.
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.
Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1) tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p.
W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.
Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087 dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];
Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k.
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.
Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1) tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p.
W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.
Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087 dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7
05 stycznia 2016
Podnoszenie do kwadratu lub mnożenie
Podobny sposób, który był użyty do znajdowania pierwiastka kwadratowego w ostatnim poście, może też być użyty do podnoszenia liczby do kwadratu.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.
Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat.
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.
Subskrybuj:
Posty (Atom)