Programowanie wskaźnikami, wydobycie ukrytej stałej

Oto krótki programik w C++
1. #include <cstdio>
2. const char * const pp=0;
3. const char * pwsk[8];

4. void tekst() {
5.   char s[6] = "Hello";
6.   pwsk[0] = pp+6;
7.   for( int i=0; i<6; i++ ) pwsk[i+1] = pp+s[i];
8.   s[0] = 0;
    };

9. void main( void ) {
10.  tekst();
11.  //printf("%s\n\r", s);
12.   int j = (int) pwsk[0];
13.   for( int i=1; i<j+1; i++ ) printf("%c", pwsk[i]);
14.   printf(" (!)\n\r");
    };

Czy on coś robi? I jest zaskoczenie. Robi! Linia 11. podkreśla, że napis s jest niedostępny, jak powinno być. W końcu jest zmienną (stałą) prywatną funkcji. Tylko dziwnie zachowuje się tablica wskaźników w liniach 7 oraz 13. Nie powinno się tak odkładać zmiennych. Raczej
pwsk[i] = &s[i];
w linii 7 oraz
printf("%c", *pwsk[i])
w linii 13.
W podejściu wskaźnikami właśnie te instrukcje prowadzą do błędów, groźnych błędów, wskaźniki tak zainicjowane jak w 6, 7 wskazują newralgiczne miejsca pamięci, zmiana może spowodować zwis systemu. Dlatego jest zakaz zmian w linii 3. I po co ta dodatkowa stała pp?
Otóż stała pp omija zabezpieczenia kompilatora, dzięki którym ten kod jest przyjęty bez kłopotów. Zwróćmy także uwagę na kasowanie napisu w 8.

Jest tylko jedno rzutowanie w 12. Kompilator nie chce mieć zakresu zmiennej ograniczonej wskaźnikiem. Jest przesunięcie, gdyż pierwszy wskaźnik trzyma długość, jak AnsiString w Pascalu.
I chętni mogą skompilować oraz zobaczyć, że tablica wskaźników pwsk przechwyciła długość napisu i sam napis, by móc go wypisać na monitorze. Będą śmieci? Otóż nie...


Kto nie wierzy, niech sprawdzi... Sprawdzone w GCC pod DOSem.

Faktoryzacja z użyciem systemu Fibonacciego i złożonością asymptotyczną

Połączenie kilku pomysłów: sposób przedstawiania liczb za pomocą systemu Fibonacciego, liczba złożona n=d*m zawierająca tylko cyfry 0 oraz m wartości d pozwoliły na opracowanie sposobu faktoryzacji, który w pętli głównej zawiera trzy proste modyfikacje. Najbardziej kosztowne jest liczenie wartości iloczynu
  k*F[2m]+r modulo p,
w którym k jest licznikiem stale dążącym do zera, r jest resztą stale rosnącą o stałą, zaś F[2m] jest stałą liczbą Fibonacciego dla danych k oraz r.

Od czasu do czasu następuje ponowne przeliczenie k oraz r, korzystając z następujących własności. W tym miejscu k jest zerem lub jedynką. Z liczby postaci
  d*(F[2m]+...+F[2]+F[0]) = d*(F[2m+1]-1)
zabieramy 'cyfrę najbardziej znaczącą F[2m], dodajemy doń aktualne k oraz r oraz dzielimy z resztą przez F[2m-1]. Część całkowita zwiększona o jeden to nowe k, zaś r jest największą ujemną wartością spełniajacą wyrażenie
  d*(F[2m-2]-1) + k*F[2m-1] + r = n    (1)
W tym wyrażeniu modyfikujemy tylko k oraz r. Jest to niezmiennik. Dla wygody przesuwamy też indeks m cyfry Fibonacciego.

Ta część powtarza się tylko tyle razy, ile z zapisie liczby n systemem Fibonacciego jest pozycji parzystych większych od większego z dzielników. Czyli na ogól mało, poniżej log n.

W głównej części są następujące działania:
d+=2;
k-=2;
r+=2;
oraz spradzenie, czy wyrażenie k*F[]+r dzieli d. W przypadku podzielności, mamy liczbę n rozbitą na dwa składniki, oba podzielne przed d.

Zapis Fibonacciego liczby n zawiera tylko cyfry na pozycjach parzystych, zatem przy inicjacji liczba może mieć jako cyfry jedynki, dwójki i zera. Pisząc co drugą pozycję mamy np.
8934053
= 101 010010 000100 101010 100100 010101 _Fib
= 0101 010001 020000 020101 010000 010101 // tylko pozycje parzyste
= 11 101 200 211 100 111 // zapis dla faktoryzacji

Ze względu na występującą dwójkę, lepiej jest uniknąć F[2m+1]-1 -r = n postaci
9227465-1 - 293411 = n
i pzejść od razu na postać z poprzedzającą liczbą Fibonacciego przy d=3
3*3524577 + 0*3524578-1639678 =
d*(F[2m+1]-1) + k*F[2m+1]+r
Czasem są same zera i jedynki, np dla 77, wtedy dzielnik można znależć ze wspólnego dzielnika n oraz (F[2m+1]-1).

Przerzucanie wartości odbywa się coraz rzadziej, dominujące stają się obliczenia
n = d*F[]-s = 9*514228  + (9*514229 - 322060), s=5 (mod 9)
n = 11*514228 + (7*514229 - 322058)
n = 13*514228 + (5*514229 - 322056)

n = 313*10945 + (504*10946 - 8516)
n = 315*10945 + (502*10946 - 8514)

I działania są na coraz mniejszych wartościach.
Myślę o trzykaniu wartości k, F[2m] oraz r w systemie o podstawie d zamiast zwykłego dzielenia modulo. W obu przypadkach asymptotyczna złożoność to O(N log^2 n), gdzie M to mniejsza z wartości n/2 (liczba pierwsza), dzielnik n.


Okazało się, że zastosowany chwyt na cyfrze Fibonacciego działa na dowolnych liczbach. Jedyny warunek to dM<n.
Można zatem zamiast F dobrać sobie M będącą iloczynem liczb nieco większych niż d, np. pierwszych. Jako konsekwencje można przejąć kontrolę nad szukaniem dzielników przedziałami. Chcemy zmniejszać r? Niezmiennik jest postaci d(M+1)+kM+r=n. Chcemy mieć iloczyny w zakresie do 50? M=(d+2)(d+100). Można też ograniczyć sobie przedział poszukiwań dobierając odpowiednio k, M ~ n/(d+k) .

Dzielenie równoczesne przez kilka liczb - pierwsze podejście

Jeśli program najpierw przekształca, potem liczy możliwe jest dzielenie przez kilka różnych liczb równocześnie. Związane są z tym pewne kłopoty.

Mianowicie bardzo trudno o odpowiedni zapis. Następnie niezmienniki. Obmyśliłem, żeby cechę charakterystyczną był fakt, że cyfry nie mniejsze niż dana były podzielne. Następnie delikatnie przesuwam dzielnik, jak przy standardowym dzieleniu pisemnym. Nie można tego zrobić bez wsparcia lub odstępu między kolejnymi dzielnikami.

Ale powstał prototyp. Przypomina zamek błyskawiczny, działający na cyfrach liczby. Cyfry liczby stanowią jedną listę, lista kolejnych dzielników drugi. Listy łączą się ze sobą na co drugiej pozycji cyfry.

Weźmy którąś cyfrę a[i], do której doczepiony jest dzielnik d[k]. Liczba utworzona z cyfr nie mniejszych niż a[i] ma być podzielna przez d[k]. Jeśli nie jest, korzystamy z przeniesień z/do cyfry a[i-1]. Niezbędny jest tu odstęp, bo wartość pozycji i-1 zmienia się. Jest to zarazem jedna z wewnętrzych operacji dzielenia. Wartość liczby cyfr nie mniejszych niż dana jest podzielna przez d[k], co się nie zmienia, kiedy przenoszę wartości pomiędzy cyframi.

Następnie przesuwamy listę dzielników o jedną pozycję. Teraz wartość cyfry a[i] może być modyfikowana resztą uzyskaną, kiedy cyfrę a[i+1] przekształcamy w podzielną przez d[k+1]. Kiedy już się ustabilizuje, możemy kontynuować.
Kolejne przesunięcie listy dzielników, oraz cyfra a[i] ma stać się podzielna przez d[k+1].
Preferowane obliczenia zwiększają cyfry a[i] kosztem wartości a[i-1], ale pozostawiają je nieujemnymi. Zmniejszanie zbyt szybko by wrzuciło gigantyczną wartość na pozycje mniej znaczące. I tak wartości na miejscach cyfr szybko rosną, mimo ograniczeń narzucanych przez d[k].  

Dzielniki d[k] wędrują po liście od cyfr najbardziej znaczących do najmniej znaczących. Przekształcenia są lokalne, czyli mogą być wykonywane równolegle. Kiedy dzielnik d[k] dojdzie do cyfry najmniej znaczącej a[0], powinna być ona resztą z dzielenia przez d[k].

Tyle teoria. W praktyce człowiek ciągle popełnia błędy, gdyż mylą się pozycje z przypisanymi wędrującymi dzielnikami. To nie jest robota dla człowieka. Z kolei wątki ograniczone do danych cyfr traktowanych jako ulotne, powinny się sprawdzić. Na razie zaplątanie się jest mocne.

Przykład zachowania: podzielność przez [..., 7, 5, 3] liczby dziesiętnej o fragmencie [... 8 27 9 ...]
Rozpatrujemy a[i]=27, co jest podzielne przez 3.
Przesuwamy listę dzielników, sprawdzając podzielność: a[i+1]=8=10-2, a[i-1]=9=3*3. Przenosimy dwójkę uzyskując fragment [... 10 7 9 ...] o tej samej wartości, oraz spełnianych podzielnościach cyfr sąsiednich przez 5, 3 odpowiednio.
Kolejne przesunięcie dzielników, teraz a[i]=7 ma być podzielne przez 5. Zwiększenie do 10 spowoduje powstanie wartości ujemnej na pozycji a[i-1], zatem zmniejszamy do 5. Równocześnie modyfikowana jest pozycja a[i+1], by a[i+2] była podzielna przez 7. Uzyskujemy fragment [... 10x+10 5 29 ...]
I tak dalej.

Parę dodatkowych faktów wynikających z konwersji

Nabieram wprawy w stosowaniu konwersji - ręcznie. A co jeśli ktoś zacznie obliczać je programowo?

Przecież najmniej znacząca cyfra w konwersji jest równoważna jednej z najbardziej podstawowych cech podzielności! Jako wielomian reszt modulo.

Albo logarytmy dyskretne, stosowane w stosowanym protokole kryptograficznym dla wygonerowania tajnego klucza dla szyfrowania symetrycznego. Liczba
b = q^a modulo p
jest równoważna konwersji liczby 10...0 z systemu o podstawie q do systemu o podstawie p. Jeśli cyfrą jedności będzie b, liczność użytych zer będzie wartością logarytmu dyskretnego a.Zaś twersja rekursywna konwersji nadaje sie do tego wprost idealnie.

Jak szybkie są takie obliczenia na współczesnych maszynach?

Druga róznica przy konwersji na podstawy będące kolejnymi liczbami

Zastanawiało mnie, czy można wykorzystać fakt, że przy przechodzeniu na kolejne systemy, liczba złożona w pewnym momencie zmienia długości swoich dzielników, czyli krotność cyfr.
Na przykład, liczba w pewnym systemie liczenia jest trójcyfrowa. Czy jest ona iloczynem dwu liczb dwucyfrowych, jak np. 11*13 = 143. A może jest iloczynem liczby jednocyfrowej przez dwucyfrową, jak 61*7 = 427.
Punkt graniczny, liczba 10 z iloczynem a*10= [a,0]_p jest przypadkiem granicznym, przy okazji dzielnikiem. 
Już widać na tych przykładach, że wielkość liczby złożonej nie jest wyróżnikiem.

Pomyślałem o niezmienniku - druga różnica cyfry jedności, oczywiście odpowiednio dostosowanej. Czyli dla podstaw rosnących p, p+1, p+2 cyfra jedności ma tworzyć ciąg lokalnie monotoniczny malejący, co uzyskamy przenosząc jedynkę z cyfry dziesiątek. Warto też zadbać o to, by cyfra setek a była taka sama. 

Sprawdzam na przykładzie, i rzeczywiście, dla podstaw odpowiednio małych liczba będąca iloczynem dwu liczb 'dwucyfrowych' daje drugą róznicę minimalnie większą od 2a. Zaś dla podstaw na tyle dużych, by była iloczynem liczby jednocyfrowej, jest nieco mniejsza. Ale to przykład, należy zgeneralizować.
Z teorii, druga róznica przy tak dopasowanym ciągu jest zawsze równa podwójcej cyfrze setek 2a, z wyjatkiem skokowych zmian towarzyszących przenoszeniom z udziałem cyfry dziesiątki. Ale szczegółowy obraz pokazuje coś innego. Owszem, jest tendencja . do zmniejszania się przyrostu wraz ze wzrostem podstawy. Ale ten przyrost jest na tyle mały, że nie widzę możliwości zastosowania go praktycznie.

Dodatkowo, przy niektórych wartościach następuje 'rozchwianie' monotoniczności lokalnie generowanych ciągów. I to akurat także w pobliżu szukanej wartości.Może się opłacać tylko przy zgrubnym szukaniu dzielników: 'tam daleko wydaje się istnieć'.

Czy istnieje jakiś sposób oszacowania, kiedy liczba trójcyfrowa złożona jest  iloczynem dwu liczb dwucyfrowych?
Wykluczamy znajomość dzielników i przegląd...

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.

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"