Szykowanie jednego z ostatnich algorytmów do implementacji

Piątego maja 2019 roku w poście opublikowałem algorytm faktoryzacji w Pythonie.

Stosuje on przegląd zupełny kandydatów na dzielniki d korzystając ze wzoru
N = a(a+1)/2 - b(b+1)/2
a właściwe rozwinięcie tego wzoru na różnicę liczb trójkątnych. We wspomnianym poście pokazuję sposób przekształcania wartości.
Przejście do kolejnego kandydata to zmniejszenie a, b i reszty r, by różnica była jak najbliżej liczby rozkładanej N.
Dla małych dzielników można pominąć bardzo dużo przypadków, ich liczność uzyskuje się z dzielenia (b+r)/d.
Okazuje się, że to dzielenie można wyeliminować. Co więcej, w implementacji także a jest niepotrzebne. Wystarczy przechowywać b w systemie o podstawie d, Wtedy reszta r to automatycznie cyfra jedności sumy b+k, która zmienia rzadko coś więcej niż najmniej znaczącą cyfrę. Krotność opuszczanych przypadków to wartość (b+r)/d, czyli wszystko poza przeniesioną do r cyfrą. Do testów następnej wartości d niezbędna jest konwersja na kolejny system, o podstawie d+1.
Zaś a i b wyglądają niemal identycznie, przy czym a jest większe od b o wartość d, najczęściej zmiana jednej cyfry wyznaczy a. Nie trzeba tego trzymać w pamięci. Konwersja na sąsiedni system staje się najbardziej pracochłonną czynnością algorytmu. Złożoność i tak pozostaje bez zmian.

Zatem algorytm ten wygląda teraz następująco:
b = -1+(N-1)/2  zapisane w systemie trójkowym,
r=0;
d=2

krok iteracji:
d++; 
c = b+r;
b--; 
r=c[0];
b = b-(c-r)/d;  zapis w systemie o podstawie d, różnica ta zastępuje dzielenie
konwersja b_{d} na b_{d+1} przygotowanie do następnego kroku

wyjścia:
r=0 ponowne, dzielnikami N są nieparzyste dzielniki od wartości d, 2b+d+1
b=0 lub d> sqrt N, liczba pierwsza

Sprawdziłem obie możliwości konwersji: rekursywną (od początkowych bardziej znaczących cyfr odejmuję poprzedzającą), oraz iteracyjną (jak w konwersji dwuprzebiegowej, wyrażeniem jest kombinacja liniowa cyfr poprzedzających z symbolami dwumianu Newtona, z różnicą 1, czyli dominujące dla małych wartości b[i+1] są dwumiany \sum_{k>i} (-1)^{k+1} b[k] \binom {k} {i}).
Dla małych wartości d jest dużo cyfr liczby b, czyli symbole Newtona stają się duże. Kłopoty sprawiają też przeniesienia między poszczególnymi cyframi. Jest znacznie lepiej niż wtedy gdy konwersja przyrost co najmniej 2 ale dalej mogą pojawiać się stosunkowo duże liczby.
Rekursja ma przewagę nad iteracją.
Jeśli nie testować niezmiennika 2N=(b+d)(b+d+1) - b(b+1), obliczenia są na małych wartościach. Tłumienie wyglądu wartości b jest nie tylko związane z konwersjami, ale także z czymś bardzo przypominającym dzielenie przez 11 lub mnożenie przez 9 w dziesiątkowym, sposobem matematyki wedyjskiej. 

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.