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.
algorytmy, pomysły na rozkład liczb i arytmetykę, także systemów niedziesiątkowych; elementy programowania pod DOSem
20 października 2019
09 października 2019
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.
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.
Subskrybuj:
Posty (Atom)