Na początku grudnia opublikowałem zarys algorytmu, w którym podstawową ideą jest utworzenie płaszczyzny z liczby, oraz szukanie śladu dzielników dla dużych wartości.
Na razie coś mnie blokuje przed napisaniem tego w C++, ale jest już wersja w Pythonie.
Miałem kłopoty, jak szybko ominąć część kodu po znalezieniu małego dzielnika. Zdecydowałem się na pętlę.
[code python]
def nwd(a,b,s):
if( 0==b ):
return a
if( a<b ): #swap(a,b)
c=a
a=b
b=c
while( 1 ): # zmniejszamy b, bo wiemy, ze sa one wzglednie pierwsze
if( 0==b%2 ):
b/=2
continue
if( 0==b%3 ):
b/=3
continue
if( 0==b%5 ):
b/=5
continue
if( 0==b%7 ):
b/=7
continue
break
if( 0==a%b ):
return b
a = a%b
if( a+a>b ) :
a = b-a
if( s>a ): #zatrzyma: wiemy ze nie ma tak malych dzielnikow
return 1
return nwd(b,a,s)
def modstop(s):
# zwieksza s do najblizszej liczby nieparzystej nie podzielnej przez 3, 5, 7
while( 1 ):
s+=2
if( 0==s%3 ):
continue
if( 0==s%5 ):
continue
if( 0==s%7 ):
continue
#break
return s
s=7 # lub wiecej, jesli jestesmy pewni
n= duza liczba
a=int (sqrt n) # jak to policzyc na liczbach calkowitych?
#a=int (n**(0.5)) # blad w liczeniu pozniejszych operacji
b= 1+(n-a*a)//a
c= n-(a+b)*a # w algorytmie c<0, trzymamy je jako ujemna wartosc
print a,b,c, (a+b)*a+c # sprawdzenie niezmiennika (a+b)*a+c = n
while( 1 ):
if( 0==n%2 ): # male dzielniki
n /=2
print "Dzielnik 2"
break
if( 0==n%3 ):
n/=3
print "Dzielnik 3"
break
if( 0==n%5 ):
n/=5
print "Dzielnik 5"
break
if( 0==n%7 ):
n/=7
print "Dzielnik 7"
break
while ( 1 ):
f = a%s # obliczenie (a+b)*a+c modulo s czyli spr. male dzielniki
e = ((f+b)*f+c)%s
if( 0==e ):
print "Dzielnik z modulo ",s
break
s = modstop(s) # zwiekszenie s
e = nwd(a,-c,s) # nwd wyrazu wolnego i podstawy systemu
if( 1<e ):
print "Dzielnik ze sladu ",e
break;
a-=1 # pelni role podstawy systemu, zmniejszamy o 1
b+=2 # wyrugowanie wplywu podstawy na wyraz wolny
c+=b-1 # modyfikacja wyrazu wolnego
if( 0==c ) :
print "Dzielnik z wyrazu wolnego ",a
break
if( 0<c ) : // wyraz wolny wiekszy niz podstawa a
b+=1
c-=a
#mozna wypisac - dla testow
#print "liczba (1*",a,"+",b,")*",a,c," stop = ",s
if( s>a ) : # duze lub male dzielniki nie znalezione, brak mozliwosci innych
print "Liczba pierwsza ",n
break
break
[\code python]
Dla malych wartosci dziala. Dla liczby 90-bitowej po dobie liczenia iloraz wartosci do sprawdzenia do oszacowania dzielnika z dołu jest mniejszy niż 2000, następnego dnia poniżej 1000. Sprawdzane są równocześnie małe i duże kandydaci, dlatego zakres możliwości się zmniejsza z obu stron.
Drugiego dnia zostało sprawdzone około 0,1% wszystkich możliwości, zastosowany wzór: iloraz różnicy podstawy a i minimalnej możliwej liczby pierwszej s przez liczność początkową (a-s)/(sqrt n). Można zatem spróbować oszacować czas przebiegu na tej maszynie na kilkaset dni. Choć podejrzewam istnienie przedziałów, w których po wejściu do nwd nastąpi od razu wyjście ( bo |c|<s ).
Mam jeszcze jeden pomysł związany z tą płaszczyzną, choć będzie wymagał sporo pamieci i moze być nieefektywny. Przechowywanie podstawy w postaci docelowo kanonicznej... Jako skutek uboczny pojawi się tablica liczb pierwszych.
18 grudnia 2019
09 grudnia 2019
Obliczanie silni większych liczb
Spróbowałem kilkoma sposobami obliczyć silnię ze 100.
W tym celu należy dobrze przygotować strukturę. Liczbę trzymam na liście dwukierunkowej o węzłach link postaci:
[int cyfra, link prev, link next, int flaga]
Okazało się, że same wskaźniki na sąsiednie cyfry prev oraz next nie wystarczą. Aby dobrze zaalokować liczbę na liście potrzebna była flaga, gdyż w przeciwnym przypadku były kłopoty z jednocyfrową liczbą 0. Nie była ona odróżniana od węzła pustego. Ponieważ węzły należały do dużego kontenera, szukanie w tym kontenerze wolnego miejsca na kolejną cyfrę wskazywało taką liczbę jako puste miejsce i nadpisywało...
Sama liczba ma dwa pola: link value oraz link baze. Składa się z cyfr dziesiętnych (docelowo), chwyconych za cyfrę najmniej znaczącą oraz podstawę systemu liczbowego.
Oprócz tego występują funkcje mnożenia przez 10 "mul0()" oraz przez małą wartość "mula( int a)". Dołączyłem także konwersje między systemami niedziesiątkowymi "convert (int new_baze)".
Wykorzystałem najpierw standardowe mnożenie dla liczenia silni z liczby n dla sprawdzenia wyników:
Liczba a;
for( i=n; 0<i; i-- )
a.mula(i);
a.show();
Następnie konwersje, by uniknąć kłopotów rozbiłem je na trzy fazy:
- liczenie 9! małymi iloczynami - by uzyskać odpowiednią wartość początkową;
- przekształcenie wartości do liczby w systemie o podstawie n;
- reszta obliczeń, by wynik wyszedł w dziesiątkowym:
Liczba a = 9!;
a.baze( n );
a.mul0();
for( i=n-1; 9<i; i-- ) {
a.convert(i);
a.mul0();
};
a.show();
Wreszcie rozklad kanoniczny czyli mieszanka konwersji oraz mul0() w odpowiednich systemach. I tu się sypało, uzyskana wartość była znacznie za mała.
W pozostałych też były kłopoty. Okazało się, że zarówno przy mnożeniu mula(int), jak i przy konwersjach nie mogę sobie pozwolić na przechowywanie reszt w dodatkowej zmiennej przechodząc między węzłami cyfr. Należy je przekazać sąsiedniej cyfrze zaraz po ich zaobserwowaniu. Inaczej czasem miewałem błędy oraz uzyskana wartość była zawyżana.
A oto szczególy funkcji:
mul0() { // mnożenie przez 10 (dokładniej: przez baze)
link cyfr = t.add(); // nowy węzeł z kontenera;
cyfr.cyfra = 0;
value->next = cyfr;
cyfr->prev = value;
value = cyfr;
};
czyli zwykłe doczepienie węzła z zerem na końcu liczby i uchwycenie go jako liczby.
mula( int a ) {}
// pierwszy przebieg: mnożenie każdej cyfry liczby przez a
link b = value;
while( b ) { b->item *= a; b=b->prev; }
// przeniesienia wartości
b = value;
int s=0;
while( 1 ) {
s = b->cyfra;
b->cyfra = s% 10; // system dziesiątkowy
s /= 10;
if( s ) {
if( b-> prev ) b->prev->cyfra += s;
else {
link c=t.add();
c->cyfra = s;
c->next = b; b->prev = c; // przypięcie węzła cyfry najbardziej znaczącej
}
};
s=0;
if( b->prev ) b = b->prev; else break;
};
Konwersja też jest podzielona na dwa moduły, w pierwszym wymagana jest liczba dwucyfrowa oraz ustawienie węzła blokującego b na cyfrę poprzedzajacą najbardziej znaczącą. Drugi węzeł link c przebiega cyfry bardziej znaczące od b ze wzorem s = cyfra*r, której część całkowita zasila bieżącą cyfrę wskazywaną przez c, zaś reszta jest odkładana do cyfry mniej znaczącej c->next->cyfra. Podstawa baze maleje, zatem wartość liczby rośnie.
int r = baze->cyfra - new-baze;
int s=0;
// modyfikacja pól baze
link b = value;
while( b->prev ) b = b->prev;
while( 1 ) {
if( b->next ) b = b->next; else break;
c = b->prev;
while( 1 ) {
s = c->cyfra * r;
c->cyfra += s/new_baze;
c->next->cyfra += s % new_baze;
if( c->prev ) c = c->prev; else break;
};
c=b; ... // druga część
};
W drugiej części zmieniamy kierunek c=b oraz przenosimy nadmiary podobnie jak przy mnozeniu mula(int).
Potem przesuwamy b = b->next; aż przekształcane będą wszystkie cyfry liczby.
Obydwoma sposobami w przeciągu sekund wypisało mi wartość wszystkich 158 cyfr dziesiętnych silni 100!
W tym celu należy dobrze przygotować strukturę. Liczbę trzymam na liście dwukierunkowej o węzłach link postaci:
[int cyfra, link prev, link next, int flaga]
Okazało się, że same wskaźniki na sąsiednie cyfry prev oraz next nie wystarczą. Aby dobrze zaalokować liczbę na liście potrzebna była flaga, gdyż w przeciwnym przypadku były kłopoty z jednocyfrową liczbą 0. Nie była ona odróżniana od węzła pustego. Ponieważ węzły należały do dużego kontenera, szukanie w tym kontenerze wolnego miejsca na kolejną cyfrę wskazywało taką liczbę jako puste miejsce i nadpisywało...
Sama liczba ma dwa pola: link value oraz link baze. Składa się z cyfr dziesiętnych (docelowo), chwyconych za cyfrę najmniej znaczącą oraz podstawę systemu liczbowego.
Oprócz tego występują funkcje mnożenia przez 10 "mul0()" oraz przez małą wartość "mula( int a)". Dołączyłem także konwersje między systemami niedziesiątkowymi "convert (int new_baze)".
Wykorzystałem najpierw standardowe mnożenie dla liczenia silni z liczby n dla sprawdzenia wyników:
Liczba a;
for( i=n; 0<i; i-- )
a.mula(i);
a.show();
Następnie konwersje, by uniknąć kłopotów rozbiłem je na trzy fazy:
- liczenie 9! małymi iloczynami - by uzyskać odpowiednią wartość początkową;
- przekształcenie wartości do liczby w systemie o podstawie n;
- reszta obliczeń, by wynik wyszedł w dziesiątkowym:
Liczba a = 9!;
a.baze( n );
a.mul0();
for( i=n-1; 9<i; i-- ) {
a.convert(i);
a.mul0();
};
a.show();
Wreszcie rozklad kanoniczny czyli mieszanka konwersji oraz mul0() w odpowiednich systemach. I tu się sypało, uzyskana wartość była znacznie za mała.
W pozostałych też były kłopoty. Okazało się, że zarówno przy mnożeniu mula(int), jak i przy konwersjach nie mogę sobie pozwolić na przechowywanie reszt w dodatkowej zmiennej przechodząc między węzłami cyfr. Należy je przekazać sąsiedniej cyfrze zaraz po ich zaobserwowaniu. Inaczej czasem miewałem błędy oraz uzyskana wartość była zawyżana.
A oto szczególy funkcji:
mul0() { // mnożenie przez 10 (dokładniej: przez baze)
link cyfr = t.add(); // nowy węzeł z kontenera;
cyfr.cyfra = 0;
value->next = cyfr;
cyfr->prev = value;
value = cyfr;
};
czyli zwykłe doczepienie węzła z zerem na końcu liczby i uchwycenie go jako liczby.
mula( int a ) {}
// pierwszy przebieg: mnożenie każdej cyfry liczby przez a
link b = value;
while( b ) { b->item *= a; b=b->prev; }
// przeniesienia wartości
b = value;
int s=0;
while( 1 ) {
s = b->cyfra;
b->cyfra = s% 10; // system dziesiątkowy
s /= 10;
if( s ) {
if( b-> prev ) b->prev->cyfra += s;
else {
link c=t.add();
c->cyfra = s;
c->next = b; b->prev = c; // przypięcie węzła cyfry najbardziej znaczącej
}
};
s=0;
if( b->prev ) b = b->prev; else break;
};
Konwersja też jest podzielona na dwa moduły, w pierwszym wymagana jest liczba dwucyfrowa oraz ustawienie węzła blokującego b na cyfrę poprzedzajacą najbardziej znaczącą. Drugi węzeł link c przebiega cyfry bardziej znaczące od b ze wzorem s = cyfra*r, której część całkowita zasila bieżącą cyfrę wskazywaną przez c, zaś reszta jest odkładana do cyfry mniej znaczącej c->next->cyfra. Podstawa baze maleje, zatem wartość liczby rośnie.
int r = baze->cyfra - new-baze;
int s=0;
// modyfikacja pól baze
link b = value;
while( b->prev ) b = b->prev;
while( 1 ) {
if( b->next ) b = b->next; else break;
c = b->prev;
while( 1 ) {
s = c->cyfra * r;
c->cyfra += s/new_baze;
c->next->cyfra += s % new_baze;
if( c->prev ) c = c->prev; else break;
};
c=b; ... // druga część
};
W drugiej części zmieniamy kierunek c=b oraz przenosimy nadmiary podobnie jak przy mnozeniu mula(int).
Potem przesuwamy b = b->next; aż przekształcane będą wszystkie cyfry liczby.
Obydwoma sposobami w przeciągu sekund wypisało mi wartość wszystkich 158 cyfr dziesiętnych silni 100!
03 grudnia 2019
Algorytm największego wspólnego dzielnika
Klasa największego wspólnego dzielnika.
Wiemy skąd inąd, że jeśli wartości zmniejszą się poniżej wartości zewnętrznej stop, liczby są względnie pierwsze.
Jak modna hermetyzacja, to proszę :) Bardziej zahermetyzować się już chyba nie da.
class Gcd {
private:
Liczba a, b;
Liczba( Liczba an, Liczba bn ) : a(an) b(bn) {};
Liczba ngcd();
friend Liczba nwd(Liczba a, Liczba b);
};
Liczba Gcd :: ngcd() {
if( a<b ) swap(a,b);
a = a%b;
if( !a ) return b;
if( a+a>b ) a = b-a;
if( a<stop ) return Liczba(1);
return ngcd();
};
Funkcja wywoławcza:
Liczba gcd( Liczba an, Liczba bn ) {
Nwd c(an,bn);
return c.ngcd();
};
Algorytm jest nieco szybszy niż klasyczny. Warunek a+a>b pozwala jeszcze raz zabrać b uzyskując wartość ujemną w a, do której w następnym kroku byśmy dodawaii. Mnożenie przez (-1) pozwala przywrócić wartość dodatnią, co odbywa się niejawnie.
Wartości funkcji są zewnętrzne do wywołania funkcji rekursywnej, dzięki czemu jest mniejsze zużycie stosu pamięci. Można pójść dalej, w funkcji gcd utworzyć petlę nieskończoną wywołującą c.ngcd(), która zwraca wartość np. -1 jak ma liczyć dalej, 0 jak względnie piersze lub 1 gdy zwracana Liczba jest już w b. Czy wtedy będzie jeszcze widać, że ta funkcja jest rekursywna?
Wiemy skąd inąd, że jeśli wartości zmniejszą się poniżej wartości zewnętrznej stop, liczby są względnie pierwsze.
Jak modna hermetyzacja, to proszę :) Bardziej zahermetyzować się już chyba nie da.
class Gcd {
private:
Liczba a, b;
Liczba( Liczba an, Liczba bn ) : a(an) b(bn) {};
Liczba ngcd();
friend Liczba nwd(Liczba a, Liczba b);
};
Liczba Gcd :: ngcd() {
if( a<b ) swap(a,b);
a = a%b;
if( !a ) return b;
if( a+a>b ) a = b-a;
if( a<stop ) return Liczba(1);
return ngcd();
};
Funkcja wywoławcza:
Liczba gcd( Liczba an, Liczba bn ) {
Nwd c(an,bn);
return c.ngcd();
};
Algorytm jest nieco szybszy niż klasyczny. Warunek a+a>b pozwala jeszcze raz zabrać b uzyskując wartość ujemną w a, do której w następnym kroku byśmy dodawaii. Mnożenie przez (-1) pozwala przywrócić wartość dodatnią, co odbywa się niejawnie.
Wartości funkcji są zewnętrzne do wywołania funkcji rekursywnej, dzięki czemu jest mniejsze zużycie stosu pamięci. Można pójść dalej, w funkcji gcd utworzyć petlę nieskończoną wywołującą c.ngcd(), która zwraca wartość np. -1 jak ma liczyć dalej, 0 jak względnie piersze lub 1 gdy zwracana Liczba jest już w b. Czy wtedy będzie jeszcze widać, że ta funkcja jest rekursywna?
Algorytm rozkładu z płaszczyzny uzyskanej z liczby
W połowie listopada podałem, jak z liczby n zrobić płat F(b,d)=c o niezmienniku
n = d^2+bd+c = d(b+d)+c
Okazało się, że zarówno dzielniki, jak i ich wielokrotności tworzą łatwo wykrywalne cięcia przy stałych d, z których łatwo znajdziemy dzielniki. Im mniejszy dzielnik, tym tych specyficznych cięć jest więcej, regularnie rozłożonych. Oznacza to, że możemy ograniczyć się tylko do badania liczb bliskich pierwiastowi kwadratowego z liczby rozkładanej.
Algorytm wygląda zatem następująco:
szukamy pierwiastka liczby sqrt n; jego wyraz wolny równy 0 wyznacza rozkład z pierwiastka;
obliczamy wartość modulo mała liczba stop z wyrażenia d(b+d)+c; możemy też teraz zwiększyć stop;
obliczamy największy wspólny dzielnik wyrazu wolnego c oraz podstawy d, co sprawdza przynależność do tego specyficznego cięcia;
przejście na sąsiednie cięcie płata F:
d--;
b+=2;
c+=b-1;
czasem tak uzyskana wartość c jest większa niż podstawa d, zmniejszamy ją w pętli o operacjach przypominających przeniesienie między cyframi liczby w systemie pozycyjnym
{ b++; c-=d; }
jeśli uzyskamy 0=c, poznamy dzielnik.
Kryterium stopu jest
stop > d
po spełnieniu którego wiemy, że liczba jest pierwsza.
Dochodzi kilka drobnych, lecz istotnych szczegółów. Możemy przyspieszyć wzrost wartości stop do kolejnych liczb niepodzielnych przez 3, 5, 7 (oczywiście większych niż 7, by ewentualny tak mały dzielnik nam nie umknął). Oznacza to, że stop staje się minimum z badanych wartości, co możemy uwzględnić w liczeniu największej wspólnej wielokrotności. Nachylenie tej krzywej dyskretnej stop(d) jest między 2d a 10d. Od dużych wartości jest ograniczone przez d, Zmniejsza to obszar poszukiwań pierwiastka.
Jeżeli iloraz dzielników liczby n=p*q, czyli p/q>1, napotkamy po drodze więcej niż jedno cięcie wskazujące dzielnik. Zatrzymujemy się na pierwszym. Na ogół wtedy znaleziony wspólny dzielnik jest iloczynem małej wartosci i dzielnika n. Może być parzysty, dlatego nie możemy wykluczyć parzystych wartości d. Potrzebne będzie wtedy jeszcze jedno liczenie znalezionego wspólnego dzielnika z liczbą rozkładaną n.
Kod zwiększania wartości stop jest następujący:
if( nie_podzielne(...) ) // test: stop | d(b+d)+c
else while(1) {
stop+=2;
if( 7<stop && (!(stop%3) || !(stop%5) || !(stop%7)) ) continue;
else break;
};
Kod obliczania dzielnika podam w kolejnym poście. Jest zbyt specyficzny i pozwoli zerknąć na nowe możliwości obliczania funkcji rekursywnych.
n = d^2+bd+c = d(b+d)+c
Okazało się, że zarówno dzielniki, jak i ich wielokrotności tworzą łatwo wykrywalne cięcia przy stałych d, z których łatwo znajdziemy dzielniki. Im mniejszy dzielnik, tym tych specyficznych cięć jest więcej, regularnie rozłożonych. Oznacza to, że możemy ograniczyć się tylko do badania liczb bliskich pierwiastowi kwadratowego z liczby rozkładanej.
Algorytm wygląda zatem następująco:
szukamy pierwiastka liczby sqrt n; jego wyraz wolny równy 0 wyznacza rozkład z pierwiastka;
obliczamy wartość modulo mała liczba stop z wyrażenia d(b+d)+c; możemy też teraz zwiększyć stop;
obliczamy największy wspólny dzielnik wyrazu wolnego c oraz podstawy d, co sprawdza przynależność do tego specyficznego cięcia;
przejście na sąsiednie cięcie płata F:
d--;
b+=2;
c+=b-1;
czasem tak uzyskana wartość c jest większa niż podstawa d, zmniejszamy ją w pętli o operacjach przypominających przeniesienie między cyframi liczby w systemie pozycyjnym
{ b++; c-=d; }
jeśli uzyskamy 0=c, poznamy dzielnik.
Kryterium stopu jest
stop > d
po spełnieniu którego wiemy, że liczba jest pierwsza.
Dochodzi kilka drobnych, lecz istotnych szczegółów. Możemy przyspieszyć wzrost wartości stop do kolejnych liczb niepodzielnych przez 3, 5, 7 (oczywiście większych niż 7, by ewentualny tak mały dzielnik nam nie umknął). Oznacza to, że stop staje się minimum z badanych wartości, co możemy uwzględnić w liczeniu największej wspólnej wielokrotności. Nachylenie tej krzywej dyskretnej stop(d) jest między 2d a 10d. Od dużych wartości jest ograniczone przez d, Zmniejsza to obszar poszukiwań pierwiastka.
Jeżeli iloraz dzielników liczby n=p*q, czyli p/q>1, napotkamy po drodze więcej niż jedno cięcie wskazujące dzielnik. Zatrzymujemy się na pierwszym. Na ogół wtedy znaleziony wspólny dzielnik jest iloczynem małej wartosci i dzielnika n. Może być parzysty, dlatego nie możemy wykluczyć parzystych wartości d. Potrzebne będzie wtedy jeszcze jedno liczenie znalezionego wspólnego dzielnika z liczbą rozkładaną n.
Kod zwiększania wartości stop jest następujący:
if( nie_podzielne(...) ) // test: stop | d(b+d)+c
else while(1) {
stop+=2;
if( 7<stop && (!(stop%3) || !(stop%5) || !(stop%7)) ) continue;
else break;
};
Kod obliczania dzielnika podam w kolejnym poście. Jest zbyt specyficzny i pozwoli zerknąć na nowe możliwości obliczania funkcji rekursywnych.
23 listopada 2019
Programowanie wskaźnikami, paradygmaty
Omijając kłopoty związane z obsługą wskaźników w C, na jeden biegun podążyli twórcy Javy - eliminacja wskaźników z widocznych obszarów (interfejs ma inne znaczenie). Ja postanowiłem podążyć na drugi bierun - eliminacja zmiennych.
Dane nie są trzymane w zmiennych, lecz w wskaźnikach.
Różnice w implementacji:
- zabroniona instrukcja * pointer = variable - uszkodzi system wpisując coś w obszar pamięci, który nie powinien być edytowany
- instrukcja pointer = &variable, wskaźniki inicjujemy w inny sposób, ten zwróci losowy fragment pamięci
- inicjowanie wskaźnika, pomocniczy wskaźnik zerowy pp, by uzyskać odpowiednią długość komórki pamięci, sizeof(char) = bajt,
const char * const pp=0;
oraz instrukcja pointer = pp+constans,
wtedy wskaźnik wskazuje obszar pamięci zastrzeżonej, może przechwycić dowolną klasę, liczbę całkowitą, w szczególności także znak, a nawet 4-znakową nazwę funkcji.
- zmiana wartości do dodanie, odjęcie czy inna operacja, ewentualnie po konwersji wskaźnika na int
- podstawienie, kod wygenerowany kompilatorem jest wystarczający, odpada tworzenie kopii zmiennej
W ten sposób cały program można zapisać tablicą, listą, drzewem klas.
Idę dalej - pierwszy bajt zawiera informację o danej klasie, w szczególności jej nazwę. Chodzi o poprawne zinterpretowanie pola, bo tu już typologia kompilatora może zawieść.
Możliwe pomyłki - nie przechwytujemy całej klasy, lecz jej składową. Wtedy program może się posypać, gdyż nie widzi pól klasy.
W dotychczasowych próbach nawet mimo krytycznego błędu program grzecznie ogranicza się tylko do zadanego obszaru pamięci, i może nawet zwrócić wartość 'wszystko zadziałało poprawnie' mimo fatalnych naruszeń obrabianych danych.
Ciąg dalszy nastąpi, kiedy dopracuję programowanie wielowątkowe wskaźnikami pod DOSa. Wtedy podam budowę podstawowych węzłów pamięci tego podejścia i sposób ich trzymania.
Dane nie są trzymane w zmiennych, lecz w wskaźnikach.
Różnice w implementacji:
- zabroniona instrukcja * pointer = variable - uszkodzi system wpisując coś w obszar pamięci, który nie powinien być edytowany
- instrukcja pointer = &variable, wskaźniki inicjujemy w inny sposób, ten zwróci losowy fragment pamięci
- inicjowanie wskaźnika, pomocniczy wskaźnik zerowy pp, by uzyskać odpowiednią długość komórki pamięci, sizeof(char) = bajt,
const char * const pp=0;
oraz instrukcja pointer = pp+constans,
wtedy wskaźnik wskazuje obszar pamięci zastrzeżonej, może przechwycić dowolną klasę, liczbę całkowitą, w szczególności także znak, a nawet 4-znakową nazwę funkcji.
- zmiana wartości do dodanie, odjęcie czy inna operacja, ewentualnie po konwersji wskaźnika na int
- podstawienie, kod wygenerowany kompilatorem jest wystarczający, odpada tworzenie kopii zmiennej
W ten sposób cały program można zapisać tablicą, listą, drzewem klas.
Idę dalej - pierwszy bajt zawiera informację o danej klasie, w szczególności jej nazwę. Chodzi o poprawne zinterpretowanie pola, bo tu już typologia kompilatora może zawieść.
Możliwe pomyłki - nie przechwytujemy całej klasy, lecz jej składową. Wtedy program może się posypać, gdyż nie widzi pól klasy.
W dotychczasowych próbach nawet mimo krytycznego błędu program grzecznie ogranicza się tylko do zadanego obszaru pamięci, i może nawet zwrócić wartość 'wszystko zadziałało poprawnie' mimo fatalnych naruszeń obrabianych danych.
Ciąg dalszy nastąpi, kiedy dopracuję programowanie wielowątkowe wskaźnikami pod DOSa. Wtedy podam budowę podstawowych węzłów pamięci tego podejścia i sposób ich trzymania.
18 listopada 2019
Funkcja z liczby i jej własności
Dowolnie duża wartość zapisana jako liczba trójcyfrowa... Idąc w tym kierunku uzyskałem dyskretną funkcję trójwymiarową o niezmienniku
n = d*d + b*d + c (1)
którą okazał się płat nad płaszczyzną (d x b) o wartościach c. W każdym punkcie tego płatu niezmiennik jest spełniony.
Dla dzielnika n wartość c=0, a pojawiły się dodatkowe własności. W sąsiedztwie dzielnika (sporym) przecięcia płatu płaszczyznami b=const, d=const powstaje wykres monotoniczny.
Dla przecięcia d=const każdy punkt jest wielokrotnością dzielnika, zależną od odległości od niego.
Dla b=const odpowiednie przecięcie ma przyrost zmienny, ale w okolicy dzielnika bliski sumie obu dzielników.
Poruszając się po płacie można skakać z pomocą niezmiennika, lub można znaleźć proste wzory na przechodzenie do sąsiedniego punktu kratowego. Z tych wzorów wyznacza się wspomniane własności. Jedne to zastosowanie konwersji dla d, drugie to przeniesienia z b do c, wreszcie istnieje prosty wzór na chodzenie po jednej z diagonali. Dla drugiej przekątnej wzór jest gorszy.
Oznacza to, że na tym płacie dzielnik jest lepiej widoczny, przez więcej niż jeden punkt. Widać też wzory skróconego mnożenia dla systemów sąsiednich dzielnikowi (wtedy d jest bliskie b).
Czy te informacje wystarczą, by można było stosować przeszukiwanie binarne do faktoryzacji?
n = d*d + b*d + c (1)
którą okazał się płat nad płaszczyzną (d x b) o wartościach c. W każdym punkcie tego płatu niezmiennik jest spełniony.
Dla dzielnika n wartość c=0, a pojawiły się dodatkowe własności. W sąsiedztwie dzielnika (sporym) przecięcia płatu płaszczyznami b=const, d=const powstaje wykres monotoniczny.
Dla przecięcia d=const każdy punkt jest wielokrotnością dzielnika, zależną od odległości od niego.
Dla b=const odpowiednie przecięcie ma przyrost zmienny, ale w okolicy dzielnika bliski sumie obu dzielników.
Poruszając się po płacie można skakać z pomocą niezmiennika, lub można znaleźć proste wzory na przechodzenie do sąsiedniego punktu kratowego. Z tych wzorów wyznacza się wspomniane własności. Jedne to zastosowanie konwersji dla d, drugie to przeniesienia z b do c, wreszcie istnieje prosty wzór na chodzenie po jednej z diagonali. Dla drugiej przekątnej wzór jest gorszy.
Oznacza to, że na tym płacie dzielnik jest lepiej widoczny, przez więcej niż jeden punkt. Widać też wzory skróconego mnożenia dla systemów sąsiednich dzielnikowi (wtedy d jest bliskie b).
Czy te informacje wystarczą, by można było stosować przeszukiwanie binarne do faktoryzacji?
12 listopada 2019
Dzielenie aproksymacjami
W matematyce wedyjskiej występuje szczególny przypadek dzielenia przez liczby np. 29, 39. Wykonuje się to dzieląc przez najbliższą dziesiątkę oraz dodanie poprawki.
Spróbowałem, czy sztuka taka uda się w ogólności. I udaje się.
Przedstawmy dzielnik w zapisie binarnym, oraz sprawdźmy, ile ma fragmentów złożonych z samych jedynek 1...1. Jeżeli tych jedynek jest więcej niż jedna, wykonamy dwa działania, na pozycji zera poprzedzającego oraz ostatniej jedynki. Gdy jedna, operacje wykonamy tylko dla tej pozycji. Potrzebujemy zmienną pomocniczą, z której liczymy kolejne poprawki, oraz je odejmujemy (przed, na jedynej) grupą jedynek, Poprawki dodajemy nad jedynką konczącą fragment. Zmienna ta przybliża się do ilorazu.
A jakie działania? Zamiast dzielnika rozważamy jego kolejne aproksymacje, i dzielimy zmienną pomocniczą właśnie przez te aproksymacje po odcięciu potęg dwójki. Uzyskamy wartość, o którą należy zmodyfikować zmienną pomocniczą. Należy jeszcze sprawdzić, gdyż trafiamy bardzo blisko wartości z dzielenia, ale czasem za daleko.
Zobaczmy na przykładach.
n/23 = 8934053 / 23
23 = 1 0111b, jedynka na pozycji 0x10, fragment trzech jedynek od pozycji ósemek do jedności, trzy obliczenia.
Dzielimy 8934053 = 558378 * 16 + 5
Zmienną roboczą jest 558378.
Fragment, początek, aproksymacja dzielnika to 3*8, obliczenie
558378 / 3 = 186126, które odejmujemy od zmiennej roboczej
558378 - 186126 = 372252
Sprawdzamy mnożąc 372252*3*8, blisko n, zostawiamy
koniec fragmentu ..111, tu już dzielimy przez cały dzielnik 23:
372252 / 23 = 16184
reszty z dzielania możemy ignorować, dodajemy
372252+16184 = 388436
Chybiamy z resztą, właściwy, poprawny iloraz jest tuż obok:
8934053 = 388437 * 23 + 2
8934053 / 27
27 = 1 1011b, dwa fragmenty
8934053 = 279189 * 32 + 5
zmienna robocza 279189 / 3 = 93063, bo aproksymacja to 3*8
279189 + 93063 = 372252
następny fragment zaczyna się dla aproksymacji 7*4:
372252 / 7 = 53178
oraz 372252 - 53178 = 319074
319074 / 27 = 11817
oraz 319074 + 11817 = 330891
Sprawdzamy i korygujemy: 8934053 = 330890*27+23
8934053 / 341
341 = 1 0101 0101b, najdłuższy obliczeniowo przypadek, bo nie ma dłuższych fragmentów. Zaczynamy od aproksymacji dzielnika 1*256
8934053 = 34898*256
i działania:
34898 - (34898 / 5) = 34898 - 6979 = 27919 poprawka na 27918*5*64+293
27918 - (27918 / 21) = 27918 - 1329 = 26589
26589 - (26589 / 85) = 26589 - 312 = 26277 poprawka
26276 - (26276 / 341) = 26276 - 77) = 26199
i finalnie 8934053 = 26199*341+194
Zamiast dzielić bądź odejmować, dzielimy przez coraz to większe kawałki dzielnika. Dzielenia początkowe można wykonać przesunięciami binarnymi. Staramy się, by uzyskać wartości iloczynów ze zmienną roboczą na początku fragmentu bliskie n, na końcu nieco mniejsze niż n.
Spróbowałem, czy sztuka taka uda się w ogólności. I udaje się.
Przedstawmy dzielnik w zapisie binarnym, oraz sprawdźmy, ile ma fragmentów złożonych z samych jedynek 1...1. Jeżeli tych jedynek jest więcej niż jedna, wykonamy dwa działania, na pozycji zera poprzedzającego oraz ostatniej jedynki. Gdy jedna, operacje wykonamy tylko dla tej pozycji. Potrzebujemy zmienną pomocniczą, z której liczymy kolejne poprawki, oraz je odejmujemy (przed, na jedynej) grupą jedynek, Poprawki dodajemy nad jedynką konczącą fragment. Zmienna ta przybliża się do ilorazu.
A jakie działania? Zamiast dzielnika rozważamy jego kolejne aproksymacje, i dzielimy zmienną pomocniczą właśnie przez te aproksymacje po odcięciu potęg dwójki. Uzyskamy wartość, o którą należy zmodyfikować zmienną pomocniczą. Należy jeszcze sprawdzić, gdyż trafiamy bardzo blisko wartości z dzielenia, ale czasem za daleko.
Zobaczmy na przykładach.
n/23 = 8934053 / 23
23 = 1 0111b, jedynka na pozycji 0x10, fragment trzech jedynek od pozycji ósemek do jedności, trzy obliczenia.
Dzielimy 8934053 = 558378 * 16 + 5
Zmienną roboczą jest 558378.
Fragment, początek, aproksymacja dzielnika to 3*8, obliczenie
558378 / 3 = 186126, które odejmujemy od zmiennej roboczej
558378 - 186126 = 372252
Sprawdzamy mnożąc 372252*3*8, blisko n, zostawiamy
koniec fragmentu ..111, tu już dzielimy przez cały dzielnik 23:
372252 / 23 = 16184
reszty z dzielania możemy ignorować, dodajemy
372252+16184 = 388436
Chybiamy z resztą, właściwy, poprawny iloraz jest tuż obok:
8934053 = 388437 * 23 + 2
8934053 / 27
27 = 1 1011b, dwa fragmenty
8934053 = 279189 * 32 + 5
zmienna robocza 279189 / 3 = 93063, bo aproksymacja to 3*8
279189 + 93063 = 372252
następny fragment zaczyna się dla aproksymacji 7*4:
372252 / 7 = 53178
oraz 372252 - 53178 = 319074
319074 / 27 = 11817
oraz 319074 + 11817 = 330891
Sprawdzamy i korygujemy: 8934053 = 330890*27+23
8934053 / 341
341 = 1 0101 0101b, najdłuższy obliczeniowo przypadek, bo nie ma dłuższych fragmentów. Zaczynamy od aproksymacji dzielnika 1*256
8934053 = 34898*256
i działania:
34898 - (34898 / 5) = 34898 - 6979 = 27919 poprawka na 27918*5*64+293
27918 - (27918 / 21) = 27918 - 1329 = 26589
26589 - (26589 / 85) = 26589 - 312 = 26277 poprawka
26276 - (26276 / 341) = 26276 - 77) = 26199
i finalnie 8934053 = 26199*341+194
Zamiast dzielić bądź odejmować, dzielimy przez coraz to większe kawałki dzielnika. Dzielenia początkowe można wykonać przesunięciami binarnymi. Staramy się, by uzyskać wartości iloczynów ze zmienną roboczą na początku fragmentu bliskie n, na końcu nieco mniejsze niż n.
04 listopada 2019
Nowy algorytm faktoryzacji? Tylko z początku,
Rozwijając algorytm rozkładu liczby N na podstawie gigantycznej stałej M (iloczyn małych wartości) w postaci
N = d(M+1) + k*M + r
gdzie d jest sprawdzanym dzielnikiem, k jest małą liczbą zaś r uzupełnia niezmiennik, doszedłem do spostrzeżenia:
r też potrafi być gigantyczne, mimo że może być kilka rzędów wielkości mniejsze niż N. Trudno jest przez dobór czynników N uczynić mniejszym, i nie zawsze w odpowiednim zakresie. Rozwiązaniem jest albo trzymanie tej reszty w systemie o podstawie d, albo dzielenie. W obu przypadkach pojawia się złożoność kwadratowa, którą spodziewałem się wyeliminować.
Ale budowa M nasuwa mi myśl, by r trzymać jako sumę iloczynów wartości dwu-, trójcyfrowych w systemie o podstawie d, i modyfikować razem z zawartością M. Więcej. Możemy przecież tak przedstawić całą liczbę N, co doprowadzi do nowego algorytmu rozkładu, z konwersjami małych wartości wewnątrz liczby!
Przykształcenia:
przyjmijmy ciąg rosnący małych liczb, mogą być kolejne lub np. kolejne pierwsze [3, 5, 7, 11, 13, 17, 19]. Liczba N jest wielomianem od tych coraz krótszych iloczynów. Ewentualny dodatkowy czynnik dołączymy do największego, lub pozostawimy, np. w drugim składniku 16 jest takim psującym dodatkiem
N = 8934053 = 3*5*7*11*15*17*19 + 3*5*7*11*15*17*16 + 3*5*7 + 3*5 + 8
Zapisujemy poszczególne czynniki w systemie o podstawie d, ale nie przejmujemy się wartościami ujemnymi, i tak preferujemy bliskie zeru. Aby znaleźć resztę, wystarczy obliczyć wartość wielomianu dla cyfr najmniej znaczących.
Tak dla d=3 zerujemy wszystkie składniki prócz 8, uzyskując resztę z dzielenia N przez 3 zapisanego jako [1 0].
Następnie jeśli jakaś wartość jest postaci [1 0] albo [1 -1], dołączamy ją do kolejnego najmniejszego czynnika, tworząc liczbę trójcyfrową, np. [1 0]*[1 2] = [1 2 0], albo [55 0]*[1 -1] = [55 -55 0]. Dalej stosujemy konwersje, które przerobią z wolna te czynniki w dwucyfrowe, ale nie dopuścimy do powstawania jednocyfrowych. Staramy się wykorzystać tylko liczby z ciągu, by jak najwięcej czynników było jednakowych. Jeśli ciąg liczył s pozycji, fakt ten zamiast konwersji w ogólności niemal s(s-1)/2 czynników pozwala zadowolić się około 2s-1 czynnikami. W przykładzie mamy ich mniej, 20 zamiast 8*7/2, ale już pierwsze zwiększenie d na 5 usuwa cztery z nich zastępując je piętnastką zapisaną 3*5 = [3 0]. Dalej upraszczają się zarówno czynniki, jak i składniki.
Kwestia składnika bez iloczynu. Zostawiamy go tymczasowo. Ale niech no tylko pojawi się drugi, połączymy je w jedną wartość. Tak już wkrótce przy wzroście d ostatnie trzy składniki złączą się w wartość równoważną 128.
I tak im większe d, tym wielomian staje się prostszy, choć obliczenia cyfr jedności czynników mogą być rzędu pierwiastka z N. Wreszcie przekraczamy z d wartość pierwiastka sześciennego N. I dostajemy, że wielomian upraszcza się do sumy dwu liczb trójcyfrowych. Po złączeniu uzyskujemy jedną liczbę trójcyfrową, a dalej jak w opublikowanym w 2014 roku w MJM artykule... Wzrost d o 2 jest równoważny konwersji o 2.
Ostatecznie pomysł sprowadził się do przeglądu zupełnego konwersjami. Jeden z pierwszych algorytmów, jaki uzyskałem badając systemy niedziesiątkowe. Potwierdza to, że dla bardzo dużych wartości przegląd zupełny polegający na konwersjach liczby trójcyfrowej jest asymptotycznie liniowy, przepraszam, nawet pracuje liniowo.
N = d(M+1) + k*M + r
gdzie d jest sprawdzanym dzielnikiem, k jest małą liczbą zaś r uzupełnia niezmiennik, doszedłem do spostrzeżenia:
r też potrafi być gigantyczne, mimo że może być kilka rzędów wielkości mniejsze niż N. Trudno jest przez dobór czynników N uczynić mniejszym, i nie zawsze w odpowiednim zakresie. Rozwiązaniem jest albo trzymanie tej reszty w systemie o podstawie d, albo dzielenie. W obu przypadkach pojawia się złożoność kwadratowa, którą spodziewałem się wyeliminować.
Ale budowa M nasuwa mi myśl, by r trzymać jako sumę iloczynów wartości dwu-, trójcyfrowych w systemie o podstawie d, i modyfikować razem z zawartością M. Więcej. Możemy przecież tak przedstawić całą liczbę N, co doprowadzi do nowego algorytmu rozkładu, z konwersjami małych wartości wewnątrz liczby!
Przykształcenia:
przyjmijmy ciąg rosnący małych liczb, mogą być kolejne lub np. kolejne pierwsze [3, 5, 7, 11, 13, 17, 19]. Liczba N jest wielomianem od tych coraz krótszych iloczynów. Ewentualny dodatkowy czynnik dołączymy do największego, lub pozostawimy, np. w drugim składniku 16 jest takim psującym dodatkiem
N = 8934053 = 3*5*7*11*15*17*19 + 3*5*7*11*15*17*16 + 3*5*7 + 3*5 + 8
Zapisujemy poszczególne czynniki w systemie o podstawie d, ale nie przejmujemy się wartościami ujemnymi, i tak preferujemy bliskie zeru. Aby znaleźć resztę, wystarczy obliczyć wartość wielomianu dla cyfr najmniej znaczących.
Tak dla d=3 zerujemy wszystkie składniki prócz 8, uzyskując resztę z dzielenia N przez 3 zapisanego jako [1 0].
Następnie jeśli jakaś wartość jest postaci [1 0] albo [1 -1], dołączamy ją do kolejnego najmniejszego czynnika, tworząc liczbę trójcyfrową, np. [1 0]*[1 2] = [1 2 0], albo [55 0]*[1 -1] = [55 -55 0]. Dalej stosujemy konwersje, które przerobią z wolna te czynniki w dwucyfrowe, ale nie dopuścimy do powstawania jednocyfrowych. Staramy się wykorzystać tylko liczby z ciągu, by jak najwięcej czynników było jednakowych. Jeśli ciąg liczył s pozycji, fakt ten zamiast konwersji w ogólności niemal s(s-1)/2 czynników pozwala zadowolić się około 2s-1 czynnikami. W przykładzie mamy ich mniej, 20 zamiast 8*7/2, ale już pierwsze zwiększenie d na 5 usuwa cztery z nich zastępując je piętnastką zapisaną 3*5 = [3 0]. Dalej upraszczają się zarówno czynniki, jak i składniki.
Kwestia składnika bez iloczynu. Zostawiamy go tymczasowo. Ale niech no tylko pojawi się drugi, połączymy je w jedną wartość. Tak już wkrótce przy wzroście d ostatnie trzy składniki złączą się w wartość równoważną 128.
I tak im większe d, tym wielomian staje się prostszy, choć obliczenia cyfr jedności czynników mogą być rzędu pierwiastka z N. Wreszcie przekraczamy z d wartość pierwiastka sześciennego N. I dostajemy, że wielomian upraszcza się do sumy dwu liczb trójcyfrowych. Po złączeniu uzyskujemy jedną liczbę trójcyfrową, a dalej jak w opublikowanym w 2014 roku w MJM artykule... Wzrost d o 2 jest równoważny konwersji o 2.
Ostatecznie pomysł sprowadził się do przeglądu zupełnego konwersjami. Jeden z pierwszych algorytmów, jaki uzyskałem badając systemy niedziesiątkowe. Potwierdza to, że dla bardzo dużych wartości przegląd zupełny polegający na konwersjach liczby trójcyfrowej jest asymptotycznie liniowy, przepraszam, nawet pracuje liniowo.
20 października 2019
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.
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.
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.
31 sierpnia 2019
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 trzymaniu 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) .
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 trzymaniu 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) .
05 sierpnia 2019
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.
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.
07 lipca 2019
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?
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?
10 czerwca 2019
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...
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...
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.
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"
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.
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.
29 kwietnia 2019
Szczególny przypadek konwersji o większą wartość
Kiedy opisywałem faktoryzację korzystając z podstaw parzystych, wspomniałem o konwersji o większą wartość. Przykładowo przechodzenie na system o 8 więcej, o 16 więcej itp.
Kiedyś proponowałem coś takiego: mając liczbę [a, b] konwersja o 8 polega na przekształcceniu [a, b-8a], po czym naprawa powstałych cyfr za pomocą przeniesień.Wartości przechodzą na cyfrę mniej znaczącą, potem wracają na początkowe miejsce.
Okazuje się, że istnieje możliwość takiego przekształcenia, że do cyfry mniej znaczącej trafia tylko reszta. Nawet mocniej. Nie zawsze musimy mnożyć przez różnicę podstaw docelowej i początkowej.
Pokażę to na przykładzie konwersji z podstawy 20 na 28. Różnica podstaw 8. Ale największy wspólny dzielnik podstaw to 4. Możemy niejawnie 'przejść' na system 20/4 =5, przeliczyć nową wartość różnicy jak dla 8/4=2, oraz 'wrócić z powstałego' siódemkowego. Te przechodzenia zawierają przekształcenia przeciwne, czyli wzajemnie się niwelują. Pozostaje mnożenie przez 2 cyfry w dwudziestkowym, oraz reszta dla cyfry mniej znaczącej jest mnożona przez 4.
Więcej, możemy od razu oszacować wartość w nowym systemie, dobierając resztę tak, by nie mieć nadmiaru bądź niedomiaru w cyfrze.
Przykład: przeliczyć [17 14] _20 na system o podstawie 28
największy wspólny dzielnik systemów to 4, oraz 28/4=7. Jest to wielokrotność, która pozostaje przy cyfrze.
2*17/7 daje modyfikatory 4 i resztę 6, ale możemy być 'sprytniejsi' i weżmiemy 5 oraz resztę -1. Wtedy zamiast odejmować 6*4 od 14 dodamy doń 1*4.
Teraz odejmiemy znaleziony modyfikator od cyfry dziesiątek, resztę od cyfry jedności:
[17-5, 14-(-1)*4] = [12, 18] _ 28
Cyfry najmniej znaczącej nie przekształcamy. Otrzymujemy poprawną wartość cyfr w nowym systemie!
Modyfikatory odejmujemy dopiero po użyciu cyfr. Obliczenia są tak łatwe, że przy odrobinie wprawy wiemy kiedy brać nieco więcej, oraz rzadko kiedy potrzebne są dodatkowe przeniesienia między cyframi.
Przypominam, że konwersja polega na iteracyjnym dołączeniu cyfry od liczby, przekształceniu wszystkich cyfr uzyskanego podciągu.
Fragment takich obliczeń (dołączamy kolejną cyfrę 21):
z systemu 28 na system 36 (wspólny dzielnik 4), zmodyfikowana podstawa to 36/4=9
[4, 13, 11, 21] _28 podciąg cyfr podczas konwersji, ((4*36+13)*36+11)*28+21
[8, 26, 22, ] podwojone cyfry
[1*9-1, 3*9-1, 2*9+4, ] wyłuskanie modyfikatorów - wielokrotności 9 i reszt
[4-1, 13-3, 11-2, 21] uwzględnienie modyfikatorów
[4-1, 13-3+4, 11-2+4, 21-16] uwzględnienie poczwórnych reszt
[3, 14, 13, 5] _ 36 nowa wartość podciągu ((3*36+14)*36+13)*36+5
Jeśli największy wspólny dzielnik podstaw to 1, nie możemy skorzystać z tego sposobu.
Kiedyś proponowałem coś takiego: mając liczbę [a, b] konwersja o 8 polega na przekształcceniu [a, b-8a], po czym naprawa powstałych cyfr za pomocą przeniesień.Wartości przechodzą na cyfrę mniej znaczącą, potem wracają na początkowe miejsce.
Okazuje się, że istnieje możliwość takiego przekształcenia, że do cyfry mniej znaczącej trafia tylko reszta. Nawet mocniej. Nie zawsze musimy mnożyć przez różnicę podstaw docelowej i początkowej.
Pokażę to na przykładzie konwersji z podstawy 20 na 28. Różnica podstaw 8. Ale największy wspólny dzielnik podstaw to 4. Możemy niejawnie 'przejść' na system 20/4 =5, przeliczyć nową wartość różnicy jak dla 8/4=2, oraz 'wrócić z powstałego' siódemkowego. Te przechodzenia zawierają przekształcenia przeciwne, czyli wzajemnie się niwelują. Pozostaje mnożenie przez 2 cyfry w dwudziestkowym, oraz reszta dla cyfry mniej znaczącej jest mnożona przez 4.
Więcej, możemy od razu oszacować wartość w nowym systemie, dobierając resztę tak, by nie mieć nadmiaru bądź niedomiaru w cyfrze.
Przykład: przeliczyć [17 14] _20 na system o podstawie 28
największy wspólny dzielnik systemów to 4, oraz 28/4=7. Jest to wielokrotność, która pozostaje przy cyfrze.
2*17/7 daje modyfikatory 4 i resztę 6, ale możemy być 'sprytniejsi' i weżmiemy 5 oraz resztę -1. Wtedy zamiast odejmować 6*4 od 14 dodamy doń 1*4.
Teraz odejmiemy znaleziony modyfikator od cyfry dziesiątek, resztę od cyfry jedności:
[17-5, 14-(-1)*4] = [12, 18] _ 28
Cyfry najmniej znaczącej nie przekształcamy. Otrzymujemy poprawną wartość cyfr w nowym systemie!
Modyfikatory odejmujemy dopiero po użyciu cyfr. Obliczenia są tak łatwe, że przy odrobinie wprawy wiemy kiedy brać nieco więcej, oraz rzadko kiedy potrzebne są dodatkowe przeniesienia między cyframi.
Przypominam, że konwersja polega na iteracyjnym dołączeniu cyfry od liczby, przekształceniu wszystkich cyfr uzyskanego podciągu.
Fragment takich obliczeń (dołączamy kolejną cyfrę 21):
z systemu 28 na system 36 (wspólny dzielnik 4), zmodyfikowana podstawa to 36/4=9
[4, 13, 11, 21] _28 podciąg cyfr podczas konwersji, ((4*36+13)*36+11)*28+21
[8, 26, 22, ] podwojone cyfry
[1*9-1, 3*9-1, 2*9+4, ] wyłuskanie modyfikatorów - wielokrotności 9 i reszt
[4-1, 13-3, 11-2, 21] uwzględnienie modyfikatorów
[4-1, 13-3+4, 11-2+4, 21-16] uwzględnienie poczwórnych reszt
[3, 14, 13, 5] _ 36 nowa wartość podciągu ((3*36+14)*36+13)*36+5
Jeśli największy wspólny dzielnik podstaw to 1, nie możemy skorzystać z tego sposobu.
08 kwietnia 2019
Faktoryzacja liczbami parzystym, inna wersja trial division
Zastanawiałem się, czy opublikować pierwotną znalezioną wersję faktoryzacji liczbami parzystymi, kiedy naprowadziła już ona na heurystykę opisaną w poprzednim poście.Okazuje się, że ten przegląd zupełny ma nieco większą złożoność, i nie nadaje się do komputerów, tylko dla ludzi.
Ale niech tam. Przynajmniej pokażę, jak rozumowałem.
Przy faktoryzacji przebiegam jakieś 2^(lg n) reszt (trochę mniej - do pierwiastka) kwadratowego z n) dla kolejnych podstaw p. Klasycznie połowę, wystarczy brać p nieparzyste. I to jest standardowa metoda trial division, pozostaje kwestia czy stosowane jest dzielenie, czy konwersje o 2, ale to szczegół techniczny.
Przechodząc na podstawę parzystą, nie trafiam w dzielnik, ale tuż obok. Wtedy suma cyfr przystaje do zera modulo (p-1), albo naprzemienna suma (alternate sum) przystaje do zera modulo (p+1). Analogicznie jak cechy podzielności przez 9, 11 odpowiednio. Dla kolejnych wartości parzystych ta sama wartość np. 43 jest sprawdzana dwukrotnie, z obu stron 42 oraz 44. Mogę zatem zmniejszyć stałą M złożoności algorytmu trial division O(M log^2 n), biorąc co czwartą wartość i te cechy. Pokryją wartości nieparzyste oraz rozpatruję połowę M. Miłe.
Może jeszcze uda się zmniejszyć M? Przyjrzyjmy się wykładnikom przy potęgach liczby d dla kolejnych wielokrotności d w postaci kanonicznej (iloczyn kolejnych liczb pierwszych):
1 2 1 3 1 2 1 4 1 ...
Proszę porównać dla d=2 (kolejne liczby parzyste):
2 2^2 2*3 2^3 2*5 2^2*3 2*7 2^4 2*9 ...
Specyficzny ciąg. Jeśli zainicjować A=1, potem niech w A wartością maksymalną jest k, to tworzy się grzebień postaci
A (k+1) A
Ale są luki, jednak trzeba brać pod uwagę wszystkie wielokrotności 4.
Lecz możemy przeksztalcać liczbę nieco inaczej. Bardziej wielowątkowo.
Całka Riemanna pokrywa pole pod funkcją prostokątami pionowymi. Całka Lebesque'a 'prostokątami' poziomymi. W podobny sposób zmieniam kolejność obliczeń, przez co pojawią się wątki.
Pierwszy watek to podstawy będące wszystkimi nieparzystymi wielokrotnościami 4, drugi tworzą nieparzyste wielokrotności 8. Pokrywają przedział z lukami, kolejna luka zaczyna się od 2*8=16. Jest to kolejny wątek. I tak dalej.
Wątki inicjowane są kolejnymi potęgami 2: k= 4, 8, 16, 32,..., zaś w danym wątku kN liczone są postacie liczby n dla kolejnych podstaw 2pk. Postacie liczby, nie reszty z dzielenia.
Są to konwersje o podwojony najmniejszy wspólny dzielnik danego wątku.
Czyli podstawy przekształcanych systemów dla danej liczby tworzą ciągi:
4, 12, 20, 28, 36, 44, ...
8, 24, 40, ...
16, 48, ...
32, ...
...
Wygląd modyfikowanej liczby szybko się zmniejsza, obliczanie sum, naprzemiennych sum jest prosty, ale konwersje nie są już tak miłe. Pogarszają złożoność o kolejny log n.
Dla człowieka widać na pierwszy rzut oka na cyfry, czy warto liczyć sumy, dla komputera niezbyt bez dodatkowego kodu.
Ale przecież człowiek nie będzie rozkładać dużej liczby bez wsparcia komputera! Niech ten przebieg faktoryzacji pozostanie ciekawostką.
Ale niech tam. Przynajmniej pokażę, jak rozumowałem.
Przy faktoryzacji przebiegam jakieś 2^(lg n) reszt (trochę mniej - do pierwiastka) kwadratowego z n) dla kolejnych podstaw p. Klasycznie połowę, wystarczy brać p nieparzyste. I to jest standardowa metoda trial division, pozostaje kwestia czy stosowane jest dzielenie, czy konwersje o 2, ale to szczegół techniczny.
Przechodząc na podstawę parzystą, nie trafiam w dzielnik, ale tuż obok. Wtedy suma cyfr przystaje do zera modulo (p-1), albo naprzemienna suma (alternate sum) przystaje do zera modulo (p+1). Analogicznie jak cechy podzielności przez 9, 11 odpowiednio. Dla kolejnych wartości parzystych ta sama wartość np. 43 jest sprawdzana dwukrotnie, z obu stron 42 oraz 44. Mogę zatem zmniejszyć stałą M złożoności algorytmu trial division O(M log^2 n), biorąc co czwartą wartość i te cechy. Pokryją wartości nieparzyste oraz rozpatruję połowę M. Miłe.
Może jeszcze uda się zmniejszyć M? Przyjrzyjmy się wykładnikom przy potęgach liczby d dla kolejnych wielokrotności d w postaci kanonicznej (iloczyn kolejnych liczb pierwszych):
1 2 1 3 1 2 1 4 1 ...
Proszę porównać dla d=2 (kolejne liczby parzyste):
2 2^2 2*3 2^3 2*5 2^2*3 2*7 2^4 2*9 ...
Specyficzny ciąg. Jeśli zainicjować A=1, potem niech w A wartością maksymalną jest k, to tworzy się grzebień postaci
A (k+1) A
Ale są luki, jednak trzeba brać pod uwagę wszystkie wielokrotności 4.
Lecz możemy przeksztalcać liczbę nieco inaczej. Bardziej wielowątkowo.
Całka Riemanna pokrywa pole pod funkcją prostokątami pionowymi. Całka Lebesque'a 'prostokątami' poziomymi. W podobny sposób zmieniam kolejność obliczeń, przez co pojawią się wątki.
Pierwszy watek to podstawy będące wszystkimi nieparzystymi wielokrotnościami 4, drugi tworzą nieparzyste wielokrotności 8. Pokrywają przedział z lukami, kolejna luka zaczyna się od 2*8=16. Jest to kolejny wątek. I tak dalej.
Wątki inicjowane są kolejnymi potęgami 2: k= 4, 8, 16, 32,..., zaś w danym wątku kN liczone są postacie liczby n dla kolejnych podstaw 2pk. Postacie liczby, nie reszty z dzielenia.
Są to konwersje o podwojony najmniejszy wspólny dzielnik danego wątku.
Czyli podstawy przekształcanych systemów dla danej liczby tworzą ciągi:
4, 12, 20, 28, 36, 44, ...
8, 24, 40, ...
16, 48, ...
32, ...
...
Wygląd modyfikowanej liczby szybko się zmniejsza, obliczanie sum, naprzemiennych sum jest prosty, ale konwersje nie są już tak miłe. Pogarszają złożoność o kolejny log n.
Dla człowieka widać na pierwszy rzut oka na cyfry, czy warto liczyć sumy, dla komputera niezbyt bez dodatkowego kodu.
Ale przecież człowiek nie będzie rozkładać dużej liczby bez wsparcia komputera! Niech ten przebieg faktoryzacji pozostanie ciekawostką.
06 kwietnia 2019
Faktoryzacja liczbami parzystymi
Zapiszmy liczbę rozkładaną n jako
a*p+b = n
gdzie a jest bliskie b, zaś p jest parzyste. W przypadku a=b mamy rozkład:
n = a*p+a = a*(p+1)
Potraktuję to wyrażenie jako zapis w systemie o podstawie p, co pozwala używać konwersji i przeniesień. Wtedy heurystyka rozkładu sprowadza się do zastosowania następujących przekształceń:
n = a*2+b = a*2+(a+1)
gdy a jest nieparzyste, przenosimy jedynkę dodając p do b (np. (a-1)*p + (p+b)).
dalej rozważamy dwa wyrażenia:
[a',b',p'] = [a/2 , b, 2p]
oraz
[a/2, b-a, 2(p+1)]
Przenosimy wartości między pierwszą a drugą pozycją, by były jak najbliższe. Jest to związane z dzieleniem przez p+1, gdyż gdy a>b przenosimy k:
a-k = b+pk, stąd a-b=(1+p)k;
oraz przy a<b
a+k = b-pk, stąd a-b=-(1+p)k;
Jeśli różnica |a-b|<p-1, odcinamy ten ciąg przekształceń. Gdy a=b kończymy zwracając rozkład. Prodedura zawsze się zakończy, gdyż każdą liczbę n przedstawimy jako 1*(n-1)+1. Liczby pierwsze mają jedynie to przedstawienie. Nie można użyć |a-b|<p, co będzie pokazane w przykładzie dalej.
Uzyskamy w ten sposób kolejne wyrażenia, których wydaje się wykładnicza liczność. To się tylko wydaje. Na początku owszem, potem przycinianie bierze górę.
Przedstawić wszystkie możliwe przedstawienia dla rozkładu liczby 133.
p=2, a=44, b=45 (44*2+45 z dzielenia 133/3), czyli
[44, 45, 2]
kolejne trójki to:
[22, 45, 4] oraz [22, 45-44, 2(2+1)] = [22, 1, 6]
po poprzenoszeniu nadmiarów, by przybliżyć a do b mamy:
[26, 29, 4] oraz [19, 19, 6], które już wskazuje poszukiwane przedstawienie 19*(6+1). Cięcie.
Teraz z [26, 29, 4] uzyskujemy
[13, 29, 8] oraz [13, 3, 10]
Z tego drugiego przenosimy, np. do [12, 13, 10]. Kolejna iteracja da trójki [6, 13, 20] oraz [6, 1, 22]. W obu różnica |a-b| da 7, 5 odpowiednio, obie mniejsze niż p>19. Tniemy, choć z [6, 1, 22] mozemy uzyskać ostatnie przedstawienie [1, 1, 132] korzystając z konwersji na system o potrojonej podstawie.
Wracamy do [13, 29, 8], przenosimy jedynkę, tym razem zwiększając a - i tak zaraz dzielimy przez 2. Mamy [14, 21, 8].
Zauważmy, że różnica b-a=7 jest podzielna zarówno przez 7, jak i 14, i jest mniejsza niż p=8. Jest ochota na przycięcie, co zgubi kolejne przedstawienia.
Oto kolejne trójki: [7, 21, 16], oraz [7, 7, 18], z drugiej wynika kolejne przedstawienie 7*(18+1).
Pierwszą modyfikujemy do [8, 5, 16]. Co prawda teraz a>b, ale jest parzyste, zaraz się zmniejszy. Teraz podaję już tylko trójki nie spełniające warunku przycinania: [4, 5, 32], [2, 1, 66] i ostatecznie ucinane [1, 1, 132].
Znalezione trzy przedstawienia dla rozkładu 133 = 19*(6+1) = 7*(18+1) = 1*(132+1).
Teraz tylko zaimplementować...
a*p+b = n
gdzie a jest bliskie b, zaś p jest parzyste. W przypadku a=b mamy rozkład:
n = a*p+a = a*(p+1)
Potraktuję to wyrażenie jako zapis w systemie o podstawie p, co pozwala używać konwersji i przeniesień. Wtedy heurystyka rozkładu sprowadza się do zastosowania następujących przekształceń:
n = a*2+b = a*2+(a+1)
gdy a jest nieparzyste, przenosimy jedynkę dodając p do b (np. (a-1)*p + (p+b)).
dalej rozważamy dwa wyrażenia:
[a',b',p'] = [a/2 , b, 2p]
oraz
[a/2, b-a, 2(p+1)]
Przenosimy wartości między pierwszą a drugą pozycją, by były jak najbliższe. Jest to związane z dzieleniem przez p+1, gdyż gdy a>b przenosimy k:
a-k = b+pk, stąd a-b=(1+p)k;
oraz przy a<b
a+k = b-pk, stąd a-b=-(1+p)k;
Jeśli różnica |a-b|<p-1, odcinamy ten ciąg przekształceń. Gdy a=b kończymy zwracając rozkład. Prodedura zawsze się zakończy, gdyż każdą liczbę n przedstawimy jako 1*(n-1)+1. Liczby pierwsze mają jedynie to przedstawienie. Nie można użyć |a-b|<p, co będzie pokazane w przykładzie dalej.
Uzyskamy w ten sposób kolejne wyrażenia, których wydaje się wykładnicza liczność. To się tylko wydaje. Na początku owszem, potem przycinianie bierze górę.
Przedstawić wszystkie możliwe przedstawienia dla rozkładu liczby 133.
p=2, a=44, b=45 (44*2+45 z dzielenia 133/3), czyli
[44, 45, 2]
kolejne trójki to:
[22, 45, 4] oraz [22, 45-44, 2(2+1)] = [22, 1, 6]
po poprzenoszeniu nadmiarów, by przybliżyć a do b mamy:
[26, 29, 4] oraz [19, 19, 6], które już wskazuje poszukiwane przedstawienie 19*(6+1). Cięcie.
Teraz z [26, 29, 4] uzyskujemy
[13, 29, 8] oraz [13, 3, 10]
Z tego drugiego przenosimy, np. do [12, 13, 10]. Kolejna iteracja da trójki [6, 13, 20] oraz [6, 1, 22]. W obu różnica |a-b| da 7, 5 odpowiednio, obie mniejsze niż p>19. Tniemy, choć z [6, 1, 22] mozemy uzyskać ostatnie przedstawienie [1, 1, 132] korzystając z konwersji na system o potrojonej podstawie.
Wracamy do [13, 29, 8], przenosimy jedynkę, tym razem zwiększając a - i tak zaraz dzielimy przez 2. Mamy [14, 21, 8].
Zauważmy, że różnica b-a=7 jest podzielna zarówno przez 7, jak i 14, i jest mniejsza niż p=8. Jest ochota na przycięcie, co zgubi kolejne przedstawienia.
Oto kolejne trójki: [7, 21, 16], oraz [7, 7, 18], z drugiej wynika kolejne przedstawienie 7*(18+1).
Pierwszą modyfikujemy do [8, 5, 16]. Co prawda teraz a>b, ale jest parzyste, zaraz się zmniejszy. Teraz podaję już tylko trójki nie spełniające warunku przycinania: [4, 5, 32], [2, 1, 66] i ostatecznie ucinane [1, 1, 132].
Znalezione trzy przedstawienia dla rozkładu 133 = 19*(6+1) = 7*(18+1) = 1*(132+1).
Teraz tylko zaimplementować...
22 marca 2019
System bezdziesiątkowy
System bezdziesiątkowy to system, w którym nie ma dziesiątki. wszystkie liczby są cyframi. Jeden jest standardowy - cyfrę stanowi liczność kresek. pałeczek, czy jakichś innych jednostkowych elementów.
Drugie podejście to wymyślenie własnych graficznych elementów na każdą z cyfr. Jest ich nieskończenie wiele, dlatego konstrukcja ma być łatwo rozszerzalna.
Pierwsze takie podejście spróbowałem jeszcze w liceum. Uzyskałem kilkaset cyfr zbudowanych z komórek, w których pojawiały się kreski. Budowa takiej komórki jest następująca:
--------
| \ / |
| x |
|/ \ |
--------
Dwie linie pionowe, dwie poziome i dwie ukośne, łącznie 2^6 możliwości zapisu cyfry w komórce. Jeśli jesteśmy w stanie rozróżnić położenie w komórce, mamy 64 cyfr w jednej komórce. Jeśli chcemy je łatwo rozróżniać, jest ich mniej, np. mamy tylko 59+1 (pusta) rozróżnialnych, spójnych = połączonych w wierzchołkach mozliwości dla jednej komórki.
Wypełnianie krawędziami komórki jest uporządkowane następującym cyklem: najpierw krawędzie pionowe, potem pionowe, potem kombinacje dwu krawędzi zachowując porządek ich ułożenia. Po wyczerpaniu przeypadków, wstawiamy trzy takie krawędzie, wreszcie wszystkie nie ukośne (wygląda jak kwadrat). Następna cyfra to krawędź ukośna /, którą otwieramy kolejny cykl. Dokładając do niej krawędzie pionowe mamy rozróżnialne aż trzy cyfry: |/, /| oraz |/|, podobnie z krawędziami poziomymi. Teraz mamy widocznych wszystkie 16 możliwości cyklu. Wreszcie wstawiamy drugą krawędź ukośną, stosując ten sam porządek. Ostatni cykl zawiera obie krawędzie ukośne.
Teraz położenie k komórek względem siebie. Wyróżniamy jedną skrajną komórkę jako główną. Nie ma żadnych komórek dokładnie nad nią, ani po jednej jej stronie. Pozostałe komórki zaczepiamy wierzchołkiem lub krawędzią od dołu. Początkowo jest to pionowa kolumna komórek. Ostatnie są doczepione krawędzią lub wierzchołkiem do swojej poprzedniczki, ale przy większej liczności komórek doczepiamy do komórek poprzedzających. Efekt występuje już dla trzech komórek, podany nizej.
Cyfry powstają przez wypełnianie krawędziami kolejnych komórek począwszy od ostatniej. Ignorujemy te położenia, w których nie możemy na pierwszy rzut oka rozróżnić rozmieszczenia krawędzi w komórkach.
Po wstawieniu wszystkich możliwych krawędzi do każdej z komórek, ostatnie komórki zaczynają wędrówkę wokół swej poprzedniczki, łącząc się z nią krawędzią lub wierzchołkiem. Wspólna krawędź jest liczona tylko względem komórek poprzedzających.
Wyjątkowa jest sytuacja, kiedy komórka jest doczepiona do wcześniejszej niż poprzedniczka. Wtedy może przeskoczyć, doczepiając się do kolejnej komórki, bliższej swej poprzedniczki.
Jeśli kolejne przesunięcie jest zablokowane brakiem miejsca, przemieszcza się wcześniejsza komórka, zaś jej następczynie tworzą pionową kolumnę pod nią. Finalnie komórki utworzą strukturę podobną do obróconego L, gdzie w podstawie jest komórka główna, a pozostałe tworzą graficznie pionową kolumnę przesuniętą o długość krawędzi.
Przykładowo, dla trzech komórek występuje układ przypominający semafor |' skrajna komórka z dołu powinna być doczepiona do swej poprzedniczki skrajnej z góry, ale jest doczepiona do komórki głównej. Jeszcze jedno przemieszczenie przesuwa ją względem komórki głównej, zachowując połączenie wierzchołkiem, podobnie jak <. Dopiero następne przemieszczenie doczepia do komórki poprzedzającej, też wierzchołkiem. Układ komórek przypomina wtedy /\. Jesscze są trzy możliwości przeniesienia ostatniej z komórek.
W ten sposób wyczerpane zostają wszystkie wzajemne położenia komórek. Kiedy kolumna pionowa przemieści się z dołu do góry, zwiększa się o jeden krotność komórek.
Dla spójności ignorowane są przypadki, kiedy krawędzie są rozłączne lub nie uwidaczniają krotności komórek. Także przypadek, kiedy krawędzie tworzą swoje bezpośrednie przedłużenia w sąsiednich komórkach bez informacji o końcu komórki jakąś inną krawędzią.
Już dla dwu komórek liczność cyfr sięga setek, a nawet tysięcy.
Porównywanie jest proste, wystarczy zlokalizować najprostszy układ komórek zawierajacy krawędzie, i porównać liczność i porządek krawędzi. Podobnie zwiększanie i zmiejszanie cyfr o jedność.
Jednak tłumaczenie cyfr tego systemu na dziesiątkowy jest nieopłacalne - sprowadza się do przechodzenia po kolejnych cyfrach. Podobnie inne operacje arytmetyczne.
Kiedy zrezygnujemy z łączności i rozróżnialności uwidaczniając komórki, możemy łatwiej oszacowywać dziesiętną wartość. Jeśli dodatkowo będziemy podwajać wspólne krawędzie, cyfry będą wyrażane jako wielomiany potęg 64. Dla dwu komórek mamy wtedy 4*64^2 możliwe cyfry, dla 3 już 20*64^3, dla czterech aż 105*64^4.
Jako ciekawostka, symbole - oraz + są w tym systemie cyframi! Pierwszy w podejściu klasycznym to dwa, w niespójnym (kiedy widać komórki) cztery (albo pięć w zależności od wysokości położenia krawędzi, wtedy także = jest cyfrą sześć). Drugi z symboli stanowią dwie komórki po skosie złączone wierzchołkiem, o wartości przekraczającej 1745.
Drugie podejście to wymyślenie własnych graficznych elementów na każdą z cyfr. Jest ich nieskończenie wiele, dlatego konstrukcja ma być łatwo rozszerzalna.
Pierwsze takie podejście spróbowałem jeszcze w liceum. Uzyskałem kilkaset cyfr zbudowanych z komórek, w których pojawiały się kreski. Budowa takiej komórki jest następująca:
--------
| \ / |
| x |
|/ \ |
--------
Dwie linie pionowe, dwie poziome i dwie ukośne, łącznie 2^6 możliwości zapisu cyfry w komórce. Jeśli jesteśmy w stanie rozróżnić położenie w komórce, mamy 64 cyfr w jednej komórce. Jeśli chcemy je łatwo rozróżniać, jest ich mniej, np. mamy tylko 59+1 (pusta) rozróżnialnych, spójnych = połączonych w wierzchołkach mozliwości dla jednej komórki.
Wypełnianie krawędziami komórki jest uporządkowane następującym cyklem: najpierw krawędzie pionowe, potem pionowe, potem kombinacje dwu krawędzi zachowując porządek ich ułożenia. Po wyczerpaniu przeypadków, wstawiamy trzy takie krawędzie, wreszcie wszystkie nie ukośne (wygląda jak kwadrat). Następna cyfra to krawędź ukośna /, którą otwieramy kolejny cykl. Dokładając do niej krawędzie pionowe mamy rozróżnialne aż trzy cyfry: |/, /| oraz |/|, podobnie z krawędziami poziomymi. Teraz mamy widocznych wszystkie 16 możliwości cyklu. Wreszcie wstawiamy drugą krawędź ukośną, stosując ten sam porządek. Ostatni cykl zawiera obie krawędzie ukośne.
Teraz położenie k komórek względem siebie. Wyróżniamy jedną skrajną komórkę jako główną. Nie ma żadnych komórek dokładnie nad nią, ani po jednej jej stronie. Pozostałe komórki zaczepiamy wierzchołkiem lub krawędzią od dołu. Początkowo jest to pionowa kolumna komórek. Ostatnie są doczepione krawędzią lub wierzchołkiem do swojej poprzedniczki, ale przy większej liczności komórek doczepiamy do komórek poprzedzających. Efekt występuje już dla trzech komórek, podany nizej.
Cyfry powstają przez wypełnianie krawędziami kolejnych komórek począwszy od ostatniej. Ignorujemy te położenia, w których nie możemy na pierwszy rzut oka rozróżnić rozmieszczenia krawędzi w komórkach.
Po wstawieniu wszystkich możliwych krawędzi do każdej z komórek, ostatnie komórki zaczynają wędrówkę wokół swej poprzedniczki, łącząc się z nią krawędzią lub wierzchołkiem. Wspólna krawędź jest liczona tylko względem komórek poprzedzających.
Wyjątkowa jest sytuacja, kiedy komórka jest doczepiona do wcześniejszej niż poprzedniczka. Wtedy może przeskoczyć, doczepiając się do kolejnej komórki, bliższej swej poprzedniczki.
Jeśli kolejne przesunięcie jest zablokowane brakiem miejsca, przemieszcza się wcześniejsza komórka, zaś jej następczynie tworzą pionową kolumnę pod nią. Finalnie komórki utworzą strukturę podobną do obróconego L, gdzie w podstawie jest komórka główna, a pozostałe tworzą graficznie pionową kolumnę przesuniętą o długość krawędzi.
Przykładowo, dla trzech komórek występuje układ przypominający semafor |' skrajna komórka z dołu powinna być doczepiona do swej poprzedniczki skrajnej z góry, ale jest doczepiona do komórki głównej. Jeszcze jedno przemieszczenie przesuwa ją względem komórki głównej, zachowując połączenie wierzchołkiem, podobnie jak <. Dopiero następne przemieszczenie doczepia do komórki poprzedzającej, też wierzchołkiem. Układ komórek przypomina wtedy /\. Jesscze są trzy możliwości przeniesienia ostatniej z komórek.
W ten sposób wyczerpane zostają wszystkie wzajemne położenia komórek. Kiedy kolumna pionowa przemieści się z dołu do góry, zwiększa się o jeden krotność komórek.
Dla spójności ignorowane są przypadki, kiedy krawędzie są rozłączne lub nie uwidaczniają krotności komórek. Także przypadek, kiedy krawędzie tworzą swoje bezpośrednie przedłużenia w sąsiednich komórkach bez informacji o końcu komórki jakąś inną krawędzią.
Już dla dwu komórek liczność cyfr sięga setek, a nawet tysięcy.
Porównywanie jest proste, wystarczy zlokalizować najprostszy układ komórek zawierajacy krawędzie, i porównać liczność i porządek krawędzi. Podobnie zwiększanie i zmiejszanie cyfr o jedność.
Jednak tłumaczenie cyfr tego systemu na dziesiątkowy jest nieopłacalne - sprowadza się do przechodzenia po kolejnych cyfrach. Podobnie inne operacje arytmetyczne.
Kiedy zrezygnujemy z łączności i rozróżnialności uwidaczniając komórki, możemy łatwiej oszacowywać dziesiętną wartość. Jeśli dodatkowo będziemy podwajać wspólne krawędzie, cyfry będą wyrażane jako wielomiany potęg 64. Dla dwu komórek mamy wtedy 4*64^2 możliwe cyfry, dla 3 już 20*64^3, dla czterech aż 105*64^4.
Jako ciekawostka, symbole - oraz + są w tym systemie cyframi! Pierwszy w podejściu klasycznym to dwa, w niespójnym (kiedy widać komórki) cztery (albo pięć w zależności od wysokości położenia krawędzi, wtedy także = jest cyfrą sześć). Drugi z symboli stanowią dwie komórki po skosie złączone wierzchołkiem, o wartości przekraczającej 1745.
19 lutego 2019
nowe odkrycie możliwości faktoryzacji w nieoczekiwanym obszarze
Faktoryzacja liczb nieparzystych wymaga kandydatów nieparzystych. Wydaje się, że poszukiwanie dzielników dla podstaw systemów niedziesiątkowych będących liczbami parzystymi jest głupotą. A jednak!
Konwersje przy podstawach parzystych mogą aproksymować iloraz q/d gdzie q*d jest dużą liczbą na tyle skutecznie, że liczbość operacji spada do logarytmu z liczby.
Sam proces ma trzy fazy:
- oszacowanie długości dzielników
(p-x)(p+y) przechodzi w (p+x)(p+y) po konwersji, gdzie p jest potęgą 2, zaś x i y nieujemnymi odległościami dzielników od podstawy systemu
- znalezienie części całkowitej q/d, gdzie q*d = N są dzielnikami liczby rozkładanej N; płynnie przechodzi w następną fazę:
- dopasowanie reszty z dzielenia, w którym usiłuję zapisać dzielnik q>d w systemie o podstawie d. Docelowo mam uzyskać postać liczby trójcyfrowej
a b b-a _ p
lub
a b a+b _ p
Teraz wystarcza cecha podzielności i mam dzielnik np. p+1 oraz a(p+1)+b.
Działa dla dowolnego z dzielników, i zawsze znajdzie co najmniej jeden: n*1.
Ta ostatnia część jest bardzo szybka, wartości a i b mają skłonności do rozjeżdżania się, lecz potrafią się znowu zbiec. Stosuję konwersje p=p +- 2^k przy malejącym k, co aproksymuje dzielnik.
Nie wiem jeszcze dokładnie, jakie formuły zadać algorytmowi. Patrząc na oko, najpierw odległość liczby trójcyfrowej
a b c _p
c-b powinna być jak najmniejsza, a potem starać sie utrzymywać c bliskie b stosując konwersje o malejące potęgi 2. Ale nie na siłę, raczej widełkami ograniczającymi zakresy badanych wartości.W ostateczności, jest to przebieg wykładniczy względem log n, czyli liniowy.
Stosując te konwersje, znajduję dzielniki liczby 2^(101)-1, i to w około 51 krokach, jak sprawdziłem. Choć przyznaję, długość dzielników oraz niektóre bity skrajne znam z innych badanych algorytmów - służyły mi za punkt odniesienia.
Jeśli nie trafi się w odpowiedni przedział, wartości sugerowane przez heurystykę zawierają długi ciąg zer lub jedynek.
Podejście, w ktorym usiłuję uzyskać na pozycji jedności narastające potęgi 2 nie działa w ogólności. Dla ustawionych bitów dzielnika wydaje się działać, zera psują. Zatem przegląd zupełny, wykładniczy.
Istnieje jednak możliwość przycięcia tego rozrostu, co jest opisane w innym poście Faktoryzacja liczbami parzystymi z 6 kwietnia 2019 roku
Konwersje przy podstawach parzystych mogą aproksymować iloraz q/d gdzie q*d jest dużą liczbą na tyle skutecznie, że liczbość operacji spada do logarytmu z liczby.
Sam proces ma trzy fazy:
- oszacowanie długości dzielników
(p-x)(p+y) przechodzi w (p+x)(p+y) po konwersji, gdzie p jest potęgą 2, zaś x i y nieujemnymi odległościami dzielników od podstawy systemu
- znalezienie części całkowitej q/d, gdzie q*d = N są dzielnikami liczby rozkładanej N; płynnie przechodzi w następną fazę:
- dopasowanie reszty z dzielenia, w którym usiłuję zapisać dzielnik q>d w systemie o podstawie d. Docelowo mam uzyskać postać liczby trójcyfrowej
a b b-a _ p
lub
a b a+b _ p
Teraz wystarcza cecha podzielności i mam dzielnik np. p+1 oraz a(p+1)+b.
Działa dla dowolnego z dzielników, i zawsze znajdzie co najmniej jeden: n*1.
Ta ostatnia część jest bardzo szybka, wartości a i b mają skłonności do rozjeżdżania się, lecz potrafią się znowu zbiec. Stosuję konwersje p=p +- 2^k przy malejącym k, co aproksymuje dzielnik.
Nie wiem jeszcze dokładnie, jakie formuły zadać algorytmowi. Patrząc na oko, najpierw odległość liczby trójcyfrowej
a b c _p
c-b powinna być jak najmniejsza, a potem starać sie utrzymywać c bliskie b stosując konwersje o malejące potęgi 2. Ale nie na siłę, raczej widełkami ograniczającymi zakresy badanych wartości.W ostateczności, jest to przebieg wykładniczy względem log n, czyli liniowy.
Stosując te konwersje, znajduję dzielniki liczby 2^(101)-1, i to w około 51 krokach, jak sprawdziłem. Choć przyznaję, długość dzielników oraz niektóre bity skrajne znam z innych badanych algorytmów - służyły mi za punkt odniesienia.
Jeśli nie trafi się w odpowiedni przedział, wartości sugerowane przez heurystykę zawierają długi ciąg zer lub jedynek.
Podejście, w ktorym usiłuję uzyskać na pozycji jedności narastające potęgi 2 nie działa w ogólności. Dla ustawionych bitów dzielnika wydaje się działać, zera psują. Zatem przegląd zupełny, wykładniczy.
Istnieje jednak możliwość przycięcia tego rozrostu, co jest opisane w innym poście Faktoryzacja liczbami parzystymi z 6 kwietnia 2019 roku
14 stycznia 2019
Mnożenie większych liczb, alternatywne sposoby
Nie odkrywam tu nowych rzeczy, lecz podaję proste zastosowanie niektórych przekształceń stosowanych w innych przypadkach.
Równoczesne mnożenie kilku liczb.
Najlepiej, gdy mamy k czynników równej długości. Nie za dużo, ze względu na powstajace sumy, których liczność jest dana symbolem Newtona.
W ostateczności czynniki można uzupełniać zerami.
Zamieniamy iloczyny czynników na sumy iloczynów k cyfr. W pierwszym przybliżeniu są to wartości, które należy ostatecznie przenosić między pozycjami dziesiętnymi.
Jeśli mamy znaleźć wartość na pozycji i-tej, bierzemy iloczyn cyfry na pozycji i-tej dowolnego czynnika oraz cyfry jedności pozostałych. Podobnie robimy dla każdego czynnika i sumujemy. Następnie bierzemy cyfrę z pozycji (i-1) dowolnego czynnika oraz cyfrę dziesiątek dowolnego innego czynnika, Mnożymy przez siebie obie wraz z cyframi jedności pozostałych czynników. Sumujemy traktowane w ten sposób wszystkie permutacje czynników. Kontynuujemy szukanie permutacji, dopóki nie uzyskamy sum iloczynów najmniejszych możliwych czynników dla tej pozycji.
Przypomina to nieco czynności znane z Chińskiego Twierdzenia o resztach lub interpolacji wielomianami Lagrange'a. Można posłużyć się wzorem skróconego mnożenia (tu: szczególny przypadek luczb dwucyfrowych z cyfrą jedności 1):
(10a+1)(10b+1)(10c+1)(10d+1) =
10000abcd + 1000(abc+abd+acd+bcd)+100(ab+ac+ad+bc+bd+cd)+
10(a+b+c+d) + 1
Przykład: 64*27*21 = (6*2*2)*1000 + (6*2*1+6*2*7+2*2*4)*100 +(6*7*1+2*4*1+2*4*7)*10 + 4*7*1
Grupa przy 100 to suma cyfr z dwu dziesiątek, jednej jedności; przy 10 to suma iloczynów cyfr z dziesiątki i dwu jedności.
Sposób nadaje się, gdy jest kilka czynników równej długości. Później permutacje cyfr komplikują i spowalniają obliczenia.
Przerzucanie 11
Jest to metoda mnożenia egipskiego, chłopów rosyjskich zastosowana do 11 zamiast do 2.
Jeśli 11 dzieli b, to
a*b = (11a) * (11/b)
w przeciwnym przypadku wyłączamy resztę z dzielenia b przez 11.
Metoda jest posta, gdyż dzielenie liczby przez 11 sprowadza się do wypisywania cyfr uzyskanych przez różnicę cyfry z wcześniejszą.
Sposób pierwszy, wymaga poprawek: cyfry ilorazu to uzyskiwane cyfry na bieżącej pozycji:
np. 845130 / 11 =
8
4-8=-4
5-(-4)=9
1-9=-8
3-(-8)=11 = 0 ( mod 11) dodamy jedynkę na pozycji bardziej znaczącej
0-0 = 0
Na pozycjach cyfr mamy [8, -4, 9. -8, 11, 0] czyli liczbę 76830.
Sposób drugi, gdy cyfra mniej znacząca jest mniejsza od bieżącej, przenosimy jedynkę i wypisujemy cyfrę, zaś mniej znaczącą zastępujemy różnicą z otrzymaną:
845130
8>4, 7; 75130
7>5, 6; 9130
9>1, 8; 330
3=3, 3; 00
0=0, 0
Iloraz 845130 / 11 = 76830.
Mnożenie przez 11 to suma dwu kolejnych cyfr na odpowiednich pozycjach:
7683*11 = [7, 7+6, 6+8, 8+3, 3], czyli 84513.
Sposób powoli zwiększa jedną liczbę kosztem zmniejszania drugiej.
Mnożenie dopełnieniami.
Mnożąc liczby a*b, szukamy najbliższej potęgi 10 lub polowy takiej potęgi przybliżajacej b, niech to będzie b=c*10^j+d
Wtedy
a*b = ac*10^j + a*d
Kontynuujemy rekursją dla a*d.
Przypominam, że w systemie dziesiętnym mnożenie przez 5 sprowadza się do dzielenia przez 2.
a*498 = a*(500-8) = (a/2)*1000 - 2a
a*507 = a*(5*101+2) = (100a+a)*10/2 + 2a
sposób znany i stosowany, choć nie wiem, jak często implementowany. Sprowadza wszystkie występujęce iloczyny do mnozenia lub dzielenia przez 2.
Równoczesne mnożenie kilku liczb.
Najlepiej, gdy mamy k czynników równej długości. Nie za dużo, ze względu na powstajace sumy, których liczność jest dana symbolem Newtona.
W ostateczności czynniki można uzupełniać zerami.
Zamieniamy iloczyny czynników na sumy iloczynów k cyfr. W pierwszym przybliżeniu są to wartości, które należy ostatecznie przenosić między pozycjami dziesiętnymi.
Jeśli mamy znaleźć wartość na pozycji i-tej, bierzemy iloczyn cyfry na pozycji i-tej dowolnego czynnika oraz cyfry jedności pozostałych. Podobnie robimy dla każdego czynnika i sumujemy. Następnie bierzemy cyfrę z pozycji (i-1) dowolnego czynnika oraz cyfrę dziesiątek dowolnego innego czynnika, Mnożymy przez siebie obie wraz z cyframi jedności pozostałych czynników. Sumujemy traktowane w ten sposób wszystkie permutacje czynników. Kontynuujemy szukanie permutacji, dopóki nie uzyskamy sum iloczynów najmniejszych możliwych czynników dla tej pozycji.
Przypomina to nieco czynności znane z Chińskiego Twierdzenia o resztach lub interpolacji wielomianami Lagrange'a. Można posłużyć się wzorem skróconego mnożenia (tu: szczególny przypadek luczb dwucyfrowych z cyfrą jedności 1):
(10a+1)(10b+1)(10c+1)(10d+1) =
10000abcd + 1000(abc+abd+acd+bcd)+100(ab+ac+ad+bc+bd+cd)+
10(a+b+c+d) + 1
Przykład: 64*27*21 = (6*2*2)*1000 + (6*2*1+6*2*7+2*2*4)*100 +(6*7*1+2*4*1+2*4*7)*10 + 4*7*1
Grupa przy 100 to suma cyfr z dwu dziesiątek, jednej jedności; przy 10 to suma iloczynów cyfr z dziesiątki i dwu jedności.
Sposób nadaje się, gdy jest kilka czynników równej długości. Później permutacje cyfr komplikują i spowalniają obliczenia.
Przerzucanie 11
Jest to metoda mnożenia egipskiego, chłopów rosyjskich zastosowana do 11 zamiast do 2.
Jeśli 11 dzieli b, to
a*b = (11a) * (11/b)
w przeciwnym przypadku wyłączamy resztę z dzielenia b przez 11.
Metoda jest posta, gdyż dzielenie liczby przez 11 sprowadza się do wypisywania cyfr uzyskanych przez różnicę cyfry z wcześniejszą.
Sposób pierwszy, wymaga poprawek: cyfry ilorazu to uzyskiwane cyfry na bieżącej pozycji:
np. 845130 / 11 =
8
4-8=-4
5-(-4)=9
1-9=-8
3-(-8)=11 = 0 ( mod 11) dodamy jedynkę na pozycji bardziej znaczącej
0-0 = 0
Na pozycjach cyfr mamy [8, -4, 9. -8, 11, 0] czyli liczbę 76830.
Sposób drugi, gdy cyfra mniej znacząca jest mniejsza od bieżącej, przenosimy jedynkę i wypisujemy cyfrę, zaś mniej znaczącą zastępujemy różnicą z otrzymaną:
845130
8>4, 7; 75130
7>5, 6; 9130
9>1, 8; 330
3=3, 3; 00
0=0, 0
Iloraz 845130 / 11 = 76830.
Mnożenie przez 11 to suma dwu kolejnych cyfr na odpowiednich pozycjach:
7683*11 = [7, 7+6, 6+8, 8+3, 3], czyli 84513.
Sposób powoli zwiększa jedną liczbę kosztem zmniejszania drugiej.
Mnożenie dopełnieniami.
Mnożąc liczby a*b, szukamy najbliższej potęgi 10 lub polowy takiej potęgi przybliżajacej b, niech to będzie b=c*10^j+d
Wtedy
a*b = ac*10^j + a*d
Kontynuujemy rekursją dla a*d.
Przypominam, że w systemie dziesiętnym mnożenie przez 5 sprowadza się do dzielenia przez 2.
a*498 = a*(500-8) = (a/2)*1000 - 2a
a*507 = a*(5*101+2) = (100a+a)*10/2 + 2a
sposób znany i stosowany, choć nie wiem, jak często implementowany. Sprowadza wszystkie występujęce iloczyny do mnozenia lub dzielenia przez 2.
Subskrybuj:
Posty (Atom)