25 maja 2019

Konwersja dwuprzebiegowa

Opisałem pod koniec kwietnia konwersję dla większych przyrostów liczb w poście 'szczegolny przypadek konwersji'
Postanowiłem zastosować ten sposób do bardzo starej definicji, z którą zaczynałem zabawę z systemami niedziesiętkowymi.
Mianowicie p^n = \sum _{i=0} ^{n} \binom (n, i) (p-1)^i = ((p-1)+1)^n
Rozpisanie ze wzoru skróconego mnożenia jest automatyczną konwersją z systemu o podstawie p na system o podstawie p-1, ogólniej:
p^n = ((p-r)+r)^n
Związane są z tym potęgi przyrostu r oraz wzory na kombinacje. Kiedyś uważałem, że te duże wartości pojawiajace się we wzorze sprawią, że obliczanie będzie nieefektywne. I tak jest, dopóki znaleziona konwersja nie uwidoczniła mi, że te, skąd inąd potencjalnie ogromne wartości mogą się wzajemnie skracać. Wystarczy więcej przekształcać niż obliczać.

Każda cyfra przy konwersji wpływa na wszystkie cyfry mniej znaczące. Inaczej, każda cyfra zależy od pewnego wyrażenia od wszystkich cyfr bardziej znaczących.
Przekształcenie dla przyrostu r okazało się następujące dla cyfry i-tej:
a_i += 1/(p+r) (sum _{j>i} (-r)^{j-i} \binom (j, i) a_{j-1} )
dla cyfry na danej pozycji, reszta z dzielenia przechodzi bez żadnych modyfikacji do cyfry mniej znaczącej. Cyfra najmniej znacząca nie bierze udziału w przekształceniach, jest tylko modyfikowana resztą z pozycji dziesiątek.

W ten sposób bozbyliśmy się rekursji przy konwersji, pozostają dwa przebiegi. Główny liczony wielowątkowo oraz drobna korekta związana z naprawą cyfr.

Przykład: Mamy liczbę w 548321 w systemie dziewiątkowym. Należy podać tę liczbę w dziesiątkowym.
Nie będę pisał symboli Newtona \binom (n, i) = n! / (i! * (n-i)! ), od razu skrócone iloczyny - wartości trójkąta Pascala widać przy współczynnikach po przekątnych; 
5 + (- 5*5)/10 = 5-2 = 3  reszta -5
4 + (-4* 4 + 5* 2*5)/10 = 4+3 = 7 reszta 4
8 + (-8* 3 + 4* 2*3 - 5* 2*5)/10 = 8-5 = 3 reszta 0
3 + (-3* 2 + 8* 3 - 4* 4 + 5* 5)/10 = 3+2 = 5 reszta 7
2 + (-2 +3 -8 +4 -5)/10 = 2+0 = 2 reszta -8 albo lepiej 1 reszta 2
1
Drugi przebieg, korygujemy resztami uzyskując wynik:
3 (-5+7) (3+4) (0+5) (7+1) (2+1) = 327583
Jest to prawidłowa wartość tej liczby w systemie dziesiętnym.

05 maja 2019

kolejny sposób faktoryzacji z prostszym dzieleniem albo i bez

Aby sprawdzić, czy liczba jest pierwsza wprost, wystarczy 7+4(n-sqrt n) operacji porównywania, dodawania lub odejmowania.

Inicjowanie: a=(n-1)/2, po czym b=a-1, a++, r=2. Łącznie 7 operacji (z przypisaniami włącznie).
Uzyskamy a=(n-1)/2+1; b=(n-1)/2-1; r=2, które jest specjalnym rozwiązaniem pewnej tożsamości, o niej dalej.  
Teraz pętla, w której wykonujemy przekształcenia:
r-=a; a--;
albo
r+=b; b--;
oraz warunki wyjścia z pętli:
if( 0==r ) dla liczb złożonych
if( 0==b ) dla liczby n pierwszej
Pętla wykonuje się n-sqrt n razy, gdyż albo zwiększamy r, albo je zmniejszamy.

Dlaczego akurat tyle, i dlaczego to działa?

Każdą liczbę naturalną można przedstawić jako różnicę sum
1+2+...+k = k(k+1)/2 = H(k),
chociażby w trywialny sposób H(n+1)-H(n). Ale są też inne możliwości, związane z dzielnikami.
Weżmy taką tożsamość dla podwojonej liczby n, by zlikwidować dzielenie we wzorach na H(k), jest to zarazem niezmiennik pętli równy r.
2n = H(a)-H(b) = a(a+1) - b(b+1) = (a-b)(a+b+1) .
Zauważmy, że ostatnie dwa czynniki różnią się parzystością. Podwojenie było niezbędne.

Niech n będzie parzyste, wtedy 2n = 1*(n+(n-1)+1). Wystarczy wziąć a=n, b=n-1.
Niech n będzie nieparzyste, wtedy 2n = 2*(((n-1)/2 +1)+ ((n-1)/2 - 1) + 1).
To są właśnie startowe wartości dla inicjacji.

Zmniejszamy długości H(k) zabierając ostatni składnik sumy, starając się trzymać blisko wartości n.
W sposobie faktoryzacji r jest różnicą między n oraz różnicą (H(a)-H(b)). Jeśli r będzie zerem, trafimy na tożsamość, z której dzielniki wyznaczymy jako nieparzyste trywialne dzielniki liczb (a-b) oraz (a-b+1).
Dla liczb pierwszych oraz b nieujemnych startujemy od najmniejszej takiej tożsamości. Zatem żadnej innej już nie znajdziemy. Dla liczb zlożonych występują mniejsze, po dwa dla iloczynu.

Działa ładnie, lecz wolno. Do tej pory jest to algorytm złożoności arytmetycznej liniowej O(n), złożoności stosowanej dla dużych liczb O(N log n).


Warto to usprawnić. Patrząc na przebieg, z początku co trochę dodajemy b, a zaraz odejmujemy a. Można połączyć tworząc nowe przekształcenie
a--; b--; r-=(a-b);
Różnica a-b jest stała! Pozwala to jeszcze bardziej uprościć, opuszczając r/(a-b) przekształceń. Tu wkracza dzielenie.
Już na samym początku widać, że po zwiększeniu r do około n/2, mamy trzecią część z n/2 do opuszczenia, czyli 2n/6 przypadków, by r znów sprowadzić w pobliże zera.
Później róznica wzrasta do 4, oraz po zwiększeniu r o b opuszczamy czwartą część pozostałych przypadków. To są ogromne liczby, dla których nie musimy nic robić.
Ciekawym , jak będzie działał program faktoryzujący tym sposobem.

Oto kilka przykładowych tożsamości stosowanych w sposobie faktoryzacji:
n=127: a=64, b=62, r=0, bo 64*65-62*63 = 2*127

n=51:
a=26, b=24,  bo 26*27 - 24*25 = 2*51
a=18, b=15,  bo 18*19 - 15*16 = 2*51,  18-15=3, 18+15+1=2*17
a=11, b=5,   bo 11*12 - 5*6 = 2*51, 11-5=2*3, 11+5+1 = 17



Znając dzielniki, łatwo wyznaczymy te tożsamości.

A oto i kod w Pythonie (spr. online, tutorialspoints.com):
n = ...# nieparzysta dodatnia
a= 1+(n-1)/2
b= a-2
d=2
r=0
e=2
#print "wstepnie a=",a, " b=",b, " r=",r
while (1<e):
  r+=b
  d=d+1
  k = r/d
  r = r%d
  a=a-k
  b=b-k-1
  if (0==r):
      e=0
  if (1>b):
      e=1
  #print "a=",a, " b=",b, " r=",r
if( 0==e ) :
  print "Dzielniki",n,": "   
  if( 0==(a-b)%2 ) : print (a-b)/2, a+b+1
  else : print a-b, (a+b+1)/2
else : print "Pierwsza"


01 maja 2019

Mnożenie pisemne inaczej

Zastosowałem nowo znalezione przekształcenie konwersji do mnożenia.

Przypomnę sposób mnożenia a*b z użyciem konwersji. Konwertujemy oba czynniki do podstawy b. Wtedy b jest zapisane jako '10', zaś mnożenie sprowadza się do
a' * 10 = a' 0
w systemie o podstawie b. Teraz następuje powrót na system dziesiątkowy, w którym konwersje parują użyte poprzednio do przekształcania. Pozostaje niesparowana tylko jedna. Ostatnia przy powrocie.
Dokładniej, niech k=a-b, finalnie każda cyfra a[i] liczby
a = a[n]...a[1] a[0]
na pozycji mniej znaczącej modyfikuje się:
a[i-1] = a[i-1]+k*a[i] .
Wymagane poprawki przez przenoszenie.

Dla rozważanego przekształcenia mamy zmianę na pozycji i-tej:
a[i] += a[i]*k/10
z resztą przechodzącą na pozycję a[i-1]. Praktycznie można przesunąć to wyrażenie o jedną pozycję, i kończyć na i=0.
Kiedy na przykładzie przyjrzałem się rezultatowi, okazało się to rownoważne mnożeniu pisemnego, w którym obliczanie następuje od drugiej strony. Zamiast mnożyć a*[b0], potem a*b[1] i tak wracając ku pozycjom bardziej znaczącym, tworzy mi się lista 'cyfr'
[a[n]*b, a[n-1]*b, ..., a[1]*b, a[0]*b ]
Standardowe mnożenie pisemne, w którym wymienione zostały czynniki, oraz początek jest od strony cyfr bardziej znaczących.
Dodatkowo dodanie / odjęcie 10 od przyrostu skutkuje odjęciem / dodaniem cyfry danej pozycji. Po przesunięciu jest to liczba dziesiątek.

Przykład: 82 * 37
uzyskanym mnożeniem pisemnym dostaję listę cyfr
  82
*37
 296   // 8*37
+  74 // 2*37
 3034
czyli
[8*37, 2*37] równe [296, 74] = [2, 9, 6+7, 4] = 3034
chociaż liczyłem, po uwzględnieniu przesunięcia konwersji (różnica 37-10 to 27) następująco:
[8*27/10+8, 2*27/10+2, 0] => [216+80, 54+20] = 3034
Najpierw wyrażenia z cyframi, potem nanoszone poprawki od cyfr oraz przeniesienia.
Oznacza to zmianę kieunku liczenia, co podobno jest wygodniejsze dla człowieka wg Mental Maths. Oraz mamy możliwość mnożenia przez wygodniejsze czynniki.

Matematycznie złożoność się nie zmienia. Jednak dla niektórych wartości liczymy szybciej niż dla innych.