Ostatni algorytm, którego nie podałem w postaci informatycznej przeszukuje 'stożek' wartości mniejszych niż liczba faktoryzowana n, którego podstawą jest 2^i, oraz 2^(2i)<n<2^(2i+1).
Zastanawiało mnie, czy muszę przeszukiwać cały ten 'stożek'. Może istnieje 'ścieżka', która doprowadzi bezpośrednio do dzielnika.
Niech n = a*b+c, gdzie a<b jest potęgą 2, oraz c<a.
Stosowana konwersja podwaja a oraz odpowiednio zmniejsza b. Wartość c zachowuje się jak chce, nie przekraczając a. Dla wartości skrajnych tworzy ciąg niemalejący.
Do dalszej iteracji wybierałem ten z przedziałów [a, a+1], [a+1, a+2] w którym spełniony był warunek b1 < 2^k < b2, k<i.
W ten sposób dochodziłem do tego, że b po którejś iteracji stawało się potęgą 2.
Często znajdowałem pierwiastek, ale tylko wtedy, gdy był on bliski potęgi 2. Kiedy był dalej, należało przeliczyć reszty w krotności podwojonej ostatniej znalezionej reszty. Była to często wartość bliska podstawy 'stożka'.
W szczególności dla liczb pierwszych należało sprawdzać wszystkie wartości 'stożka'. Podobny obraz dawała także liczba złożona, w której dzielniki były najdalej 'odsunięte' od potęg 2.
Zatem ten sposób nie pozwala przyspieszać, należy przerachować wszystkie wartości parzyste 'grzebienia' nie większe niż 2^(i+1).
Dlatego 'grzebienia', gdyż sprawdzam wszystkie liczby postaci 2^k*d przedziału [2^i, 2^(i+1)), gdzie -1<k<i oraz d jest liczbą nieparzystą. Liczb takich jest tyle ile wynosi k+1, oraz 'tną' one pionowo 'stożek' na warstwy.
Zresztą, kto popatrzy na liczność przypadków przykładu poprzedniego posta, będzie wiedział, skąd nazwa 'grzebień'.
Brak komentarzy:
Prześlij komentarz