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.
Brak komentarzy:
Prześlij komentarz