15 grudnia 2017

Dzielenie wykorzystujace dzielenie przez potęgę podstawy

Z poczatku myślałem, że znalazłem kolejny sposób na rozkład. Ale nie. Tym razem połączenie badanych własności spowodowało tylko znalezienie sposobu dzielenia, korzystającego z innego, prostszego.

Problem jest następujący. Chcemy podzielić przez jakąś dużą liczbę, ale w pobliżu, istnieje nieco większa liczba, przez którą dzielenie jest znacznie łatwiejsze. Zatem dzielimy przez tę większą liczbę, zaś wynik korygujemy.
Sposób ten występuje w matematyce zwanej 'Mental math', tam tylko dla wartości bliskich pełnych dziesiątek. Tu stosowany jest dla dużych wartości. Łatwo przechodzi w konwersję.

Przykład, chcemy podzielić
348 895 155 : 947
Dzielenie przez 947 jest raczej skomplikowane, łatwiej jest podzielić przez 950, albo nawet przez 1000.
Zatem zróbmy to, podzielimy przez 1000 uzyskując 348 895 *1000 + 155. Aby uzyskać prawidłowy iloraz oraz resztę, należy uwzględnić poprawkę 1000 = 947+53, czyli standardowo
348 895 * (947 + 53) + 155 = 348 895 * 947 + (348 895*53+155)
Reszta jest duża, dokładamy rekursję i zastępujemy mnożenie prostszym, np. przez 50.
Zatem mamy z 348 895 155 : 950, pojawia się różnica 1000-950 = 50
348 895 155  -> 348 895 *50 +155     iloraz 348 895
17 444 905  -> 17 444 *50 + 905        17 444
873 105  -> 873 *50 + 105                  873
43 755  -> 43 *50 + 755                      43
2 905  -> 2 *50 + 905 = 950+55         2+1
Suma 348 895 + 17 444 + 873 + 43 + 2 + 1 = 367258 jest ilorazem z dzielenia przez 950, 55 jest resztą. Zadziwiająca prostota uzyskania ilorazu. Co dla innych wartości?
Mamy
348 895 155 = 367 258 * 950 + 55
Ale chcemy znaleźć iloraz przez 947, a nie przez 950=947+3.
Zatem jest to 367 258*3 + 55
Liczba mniejsza, ale dalej duża. Możemy jednak kontynuować dzielenie przez 950 ilorazu przekształcając do postaci Hörnera, czyli liczba
348 895 155 = (386*950+558)*950+55
Teraz ręcznie zamieniamy 950 na 950-947=3, uzyskując dużo mniejszą wartość
(386*3+558)*3+55 = 5203
Można zastosować rekursję dla dzielenia przez 947, albo wprost podzielić uzyskując iloraz 4 i resztę 468.

Sposób ten nadaje się, gdy chcemy znajdować wartości kilku dużych ilorazów blisko siebie, w schemacie Hörnera mamy stałe współczynniki, zaś reszty uzyskujemy z wartości tegoż wielomianu przez różnice znanego dzielnika oraz szukanego.
Np. dzielenie przez 937=950-13: (386*13+558)*13+55
przez 931=950-19: (386*19+558)*19+55

Używałem tego przy systemie Fibonacciego. Zastanawiający jest sposób znajdowania ilorazu jako sumy początkowych cyfr uzyskiwanych liczb przy dzieleniu przez potęgę podstawy. Dla innych wartości ta prostota zanika.

19 października 2017

Faktoryzacja a liczby trójkątne

Rozwinąłem pomysł z 8 września, rozwijając dalej rekursję. Zatrzymuje się ona gdy mniejszy z czynników staje się zerem. Wtedy mnożenie staje się dodawaniem, w którym można wyodrębnić trzy liczby trójkątne.
Okazuje się, że te liczby trójkątne można przekształcić w jedną sumę, a wtedy mam twierdzenie:




TW.   Nieparzysta liczba złożona N=a*b jest sumą b kolejnych liczb.  

a*b = 2ab/2 = (a^2+2ab+b^2 +a+b - a^2 -a - b^2-b )/2 =
( (a+b)(a+b+1) - a(a+1) - b(b+1) )/2 =
[1+...+(a+b)] - [1+...+a] - [1+...+b]
skracając dwa pierwsze nawiasy pozostaje b składników (a+1)+...+(a+b), od których odejmujemy 1+...+b = b(b+1)/2.
Ponieważ b jest nieparzyste (co wynika z nieparzystości N), od składników a+i odejmujemy (b+1)/2 uzyskując tezę.

Nie jest to jedyna suma tak uzyskana, można wspomnieć
N = (N-1)/2 + ((N-1)/2+1),
np. 143 = 71+72. 
Ale suma z twierdzenia zawierają tyle składników jaką wartość ma dzielnik. Znając krotność, można wyznaczyć dzielniki. Trochę obliczeń doprowadziło do następującej heurystyki:

Niech c będzie nieparzystą liczbą taką, że
c(c+1) < N < (c+2)(c+3),
oznaczmy przez r różnicę
r = N - c(c+1)/2 ,
zaś przez d najmniejszą wartość sumy d=1.
Jeśli r>=c, zmniejszamy r=r-c, d++ (pobieramy z reszty liczność składników zwiększając każdy z nich o 1).
Dopóki d>1 powtarzamy: 
 r = r+2*d+1; // zabieramy dwa pierwsze składniki do reszty
 c = c-2; // zmniejszamy krotność składników o zabrane
 d = d+2+r/c; // 'przesuwa' lub zwiększa najmniejszy składnik sumy
 r = r%c; // zmniejszanie reszty o wartość przekazaną składnikom sumy
Jeśli 0=r, jest to szukana suma której długość c jest dzielnikiem N

Dzielenie jest początkowo bardzo rzadkie, około trzecia część przypadków wykorzystuje co najwyżej jednokrotną różnicę, taką jak przy inicjacji zmiennych.

Przykład: N=143
[1+2+3+4+5+6+7+8+9+10+11+12+13+14+15] + 23 = 143
r=23-15 = 8; c=15; d=1+1; po tej modyfikacji mamy
[2+3+4+...+16] + 8 = 143
iteracja, zabieramy 2+3, dokładając do reszty r = 8+2+3 = 13
[4+...+16]+13, ale mamy c = 15-2 = 13 składników, przerzucamy z reszty uzyskując
[5+...+17] = 143
elementów 13 i dzielnik 13.

Nie musimy, ale kontynuując mamy
143 = [7+...+17] + (5+6) = [8+...+18] + 0
Kolejny dzielnik 11.
[10+11+12+13+14+15+16+17+18] + (8+9) =
[11+12+13+14+15+16+17+18+19] + 8

08 września 2017

Kolejne kandydatki na wielomianowe argorytmy faktoryzacji

Rachowanie w systemie, w którym jest dużo cyfr jest tak skomplikowane, że oprócz tabliczki mnożenia należy wprowadzać także tabliczkę dodawania. Nie zawsze przewidzimy dokładnie postaci wyniku.
Zatem należy zmienić definicję działania. Dodawanie jest następujące dla naturalnych a,b:
a+0 = a,
a+b = max(a,b) + min(a,b);
a+b = (inc a) + (dec b);
Działania maksimum max, minimum min, incrementacji inc (zwiekszanie o jeden) i dekrementacji dec są klasyczne.
Odejmowanie można przedstawić rekursją:
a-0 = a,
a-b = (dec a) - (dec b). 

Mnożenie też jest zdefiniowane dla uporządkowanych malejąco wartości a, b:
a*0 = 0,
a*1 = a,
a*b = (inc a)*(dec b) + (a-b) + 1
Wynika to  faktu (a+1)(b-1) = ab-a+b-1.
Można odwrócić kierunek, a wtedy (inc a)*(dec b) = a*b-(a-b)-1.

Stosując przedstawione działanie do systemu dziesiętnego, oraz dołączając do  większej wartości nadmiar z reszty, uzyskamy np. dla  liczby 51:
51 =
25*2 +1 =
24*2 +3 =
23*2 +5 =
22*2 +7 =
21*2 +9 =
20*2 +11 =
19*2 +13 =
18*2 +15 =    oraz (17*3)-(17-3)-1= 17*3-15
17*3 = 
16*3 +3 =
15*3 +6 =
14*3 +9 =
13*3 +12 =
12*4 +3 =
11*4 +7 =
10*5 +1 =
9*5 +6 =
8*6 +3 =   
7*7 +2      

Widać, że dla większych wartości przechodzenie wymaga operacji liniowych lub stałych, reszty układają się we wzory, które można ominąć rozwiązując liniowe równanie aproksymacyjne zmiennej k, w którym pominiemy resztę
a-k = bk,
stąd k = a/(b+1). Tyle wyrażeń można pominąć, np. dla 25*2+1 pominiemy 25/3=8, a wtedy 25-8=17, b wzrośnie o 1, zaś c wzrastając o bk przybliży a.
Dla 9*5+6 mamy przeliczenie: 10*4+(9-5)+1+6 = 10*4+5+6, zaś ponieważ 5+6>10, zwiększamy a o jeszcze jeden.

Dochodzimy do algorytmów:
niech a = b = sqrt N.
inicjalizacja a*b+c = N
dopóki c<>0 lub 1<b powtarzaj
  c= c+(a-b)+1; inc a; dec b; if(c>a) {c-=a; inc a;}
return dzielniki a,b;

Drugi, zmieniający kierunek przebiegu  przebiega mniej więcej tak:
inicjalizacja a=floor{N/2}; b=2; c=N-a*b;
dopóki c<>0 lub a<b powtarzaj
  inc b; k=floor(a/b); a-=k-1; c=c+a-k*b;

Dla większych ilorazów a/b nie warto liczyć k, lecz wykorzystać bezpośrednio przekształcenie z definicji i porównać c z a, modyfikując je przy przenoszeniu.
Tłumienie wartości k jest wzmacniane, iloraz czynników a/b dąży do 1.

Algorytmy dla małych wartości są zbyt skomplikowane do użycia. Ale dla dużych liczb? Znów proste i szybkie działania stałe lub liniowe.

25 sierpnia 2017

Ile jest cyfr

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...

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.

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.

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.

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.

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...

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. 

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.