Ostatnie kilka miesięcy poświęciłem na sposoby usuwania nieoznaczoności przy znajdywaniu dzielników. Zmiany systemów pozwalają znajdować dokładnie cyfry, o ile uda nam się w jakiś sposób znaleźć krotność cyfr dzielników. W przeciwnym razie pojawia się nieoznaczoność. Sprawdzanie zapisów liczb w różnych systemach do pewnego miejsca działa dobrze, ale nie wiadomo, jak długo.
Zwłaszcza występujące przeniesienia wartości między kolejnymi cyframi bardzo przeszkadzają.
Wróciłem do trial division, tym razem jednak zdecydowałem, że reszta z dzielenia przez p będzie przy cyfrze najbardziej znaczącej. Budowa reszty w systemie binarnym jest następująca:
r = a*2^m
gdzie m+1 jest krotnością cyfr kandydata na dzielnik b, czyli
N = r + b*p, log_2 b = m+1
Używam dzielenia wstecz, rzadko działającego, w którym iloraz znajdujemy od cyfr najmniej znaczących.
Przekształcenie badane przechodzi między dzielnikami nieparzystymi p i q za pomocą przeniesień. Dodatkowo, znaleziony sposób jest liniowy, w którym występują dodawania, odejmowania i czasem mnożenie przez 2 lub 3. Zatem przekształcenie jest liniowe. Co więcej, w odróżnieniu od opublikowanego już algorytmu zmiany podstaw, przekształcenie pozostaje liniowe dla q-p<p.
Czynnością generującą najwięcej pomyłek obliczeniowych dla człowieka jest dbanie o poprawność przeniesień. Reszta to proste działania.
Przykład N = 8934053, reszta z dzielenia przez 59 jest (hexadecymalnie)
N = 38*2^16 + 59*0x1AA9F
Znalezione przekształcenie modyfikuje 0x1AA9F próbując pobrać przy ustawionym bicie i*59 wartość 61, a następnie zależnie od parzystości wyniku albo zeruje, albo ustawia bit i w ilorazie N / 61. Możemy to traktować jako liczbę binarną, stosując dodatkową zmienną interpretującą ustawione bity jako 59, które parzyste przenoszą wcześniej połowę wartości, zaś nieparzyste wykorzystując pożyczki odejmują 61 od wartości też przenosząc wcześniej połowę parzystej różnicy. Reszta nie może być traktowana jako iloczyn 59*i, ale dla przebiegu to i tak ma niewielkie znaczenie. Uzyskujemy nową resztę 69*2^16, zaś postać liczby ulega zmianie do
69*2^16 + 61*0x11A89
Powstała postać binarna jest najlepiej dopasowana do nowej wartości, co dzieje się automatycznie.
Jak to przebiega szczegółowo. Końcówka
1 1 1 1 oznacza 59 59 59 59.
Chcemy zabrać 61 od ostatniego 59, ale nie można. Zatem pożyczamy 1 1 = 0 3 uzyskując postać
1 1 0 3 czyli 59 59 0 183
Od 183 odejmujemy 61 i dzielimy przez 2 uzyskując 58. Wartość parzysta zeruje bit w tablicy ? ? 0 1. Przenosząc na kolejną wcześniejszą pozycję mamy
58/2+1*59 = 88.
Kolejna pozycja to 88/2+59 = 103, nieparzysta, stąd dla tabeli przy 61 mamy ostatnie bity 1 0 0 1.
Jeśli na danej pozycji wartość nieparzysta jest mniejsza niż q, pożyczamy.
Końcówka, na pozycji 2^16 mamy 59+38, z przeniesień dodajemy 33 uzyskując 61+69. Wartość 61 to bit w tablicy ewentualnego dzielnika, zaś 69 reszta.
Z dzielnikiem mamy do czynienia, gdy reszta jest równa 0.
Jeśli poprawnie uda się pobierać pożyczki z binarnych cyfr wcześniejszych, możemy zapamiętując tylko wielokrotność a, tablicę (liczba binarna) ewentualnego ilorazu i dzielnej p, przekształcając je liniowo.
Wtedy algorytm faktoryzacji szacuję na O() = n log n.
Brak komentarzy:
Prześlij komentarz