Mając faktoryzować liczbę postaci
n = (a*p+b)*p+c,
zastanawiałem się, czy można tak przekształcić tę liczbę, aby szybciej znaleźć jej ewentualne dzielniki. Bez użycia brute force dla poszczególnych liczb pierwszych lub liczb nieparzystych (jak nie znam wszystkich liczb pierwszych).
Pierwsze podejrzenie padło na postać:
n = e*p + (d*p+f)^2 = d*p^2 + (e+2*d*f)*p + f^2
Wzór sugeruje, że jeśli cyfra najmniej znacząca jest kwadratem, to wyłaczając odpowiedni kwadrat z n znajdę mniejszą wartość związaną z dzielnikiem. Pozostaje iloczyn 'e*p', który jednak podczas konwersji na odpowiednią podstawę modyfikuje wyraz wolny.
Kolejne pytanie, czy mogę tak przekształcać liczbę, aby mieć kontrolę nad zmianami wyrazu wolnego?
Wtedy odpowiedni ciąg konwersji zacznie przybliżać wyraz wolny do zera, dla którego istnieje dzielnik.
Podczas faktoryzacji przez zmianę systemów szybko uzyskuję liczby trzycyfrowe, zatem co robią konwersje z wyrazem wolnym liczb trzycyfrowych?
Okazało się, że przy konwersji z systemu o podstawie p na system o podstawie p+k na współczynniki liczb trzycyfrowych znalazłem wzory iteracyjne.
Załóżmy, że zwiększamy podstawę (k dodatnie):
Współczynnik a jest stały.
Współczynnik b zmienia się liniowo od a albo k: b = b-2*a*k.
Współczynnik c zmienia się kwadratowo od k: c = a*k^2 - b*k + c.
Po wstawieniu nowych wartości
[a,b,c] = [a, b-2ak, akk-bk+c]
uzyskiwałem liczby, które nie były 'cyframi' przedziału [0,p), ale nie zawsze były miejsze, czasem także większe od p. Po 'naprawie' cyfr uzyskiwałem prawidłowe postaci cyfr w kolejnych systemach.
Ale dobrze widać było tylko sąsiednie podstawy. Kiedy zwiększałem k, nawet tylko do 2, przy większych a bardzo często naprawa modyfikowała b, co powodowało szybko narastający błąd szacowań. Zachowania się wyrazu wolnego nie byłem w stanie przewidzieć.
Zatem ten sposób nie jest najlepszy. Może służyć jako zastąpienie wersji rekursywnej programu wersją iteracyjną (k=2), gdyż wtedy następuje do dwu pożyczek/przeniesień. Z kolei nie wiemy bez sprawdzenia, które z nich będzie.
Brak komentarzy:
Prześlij komentarz