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.
23 listopada 2019
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.
Subskrybuj:
Posty (Atom)