Przegląd zupełny do wartości pierwiastka sześciennego z rozkładanej liczby odbywa się po wszystkich nieparzystych wartościach. Nawet dalej, ale niekoniecznie do pierwiastka kwadratowego.
Można przyspieszyć przegląd przy małych a, gdyż
niech n = (a*p+b)*p+c.
dla ustalonego a wartość b tworzy funkcję monotoniczną od zmian podstawy p.
Jeśli dla podstawy parzystej mamy sumę a+b bliską p przy ustalonym a (a tak jest blisko dzielnika), zmienia się głównie b, c jest szumem. Zatem wystarczy tylko sprawdzać wartości z różnym a. Tych zaś jest też nie więcej niż pierwiastek sześcienny. Dodatkowo dla postaw bliskich pierwiastkowi sześciennemu a zmienia się o 2, nie o 1. Oszacowanie jest zawyżone.
Zatem stałą złożoności przeglądu zupełnego można związać nie tyle z pierwiastkiem kwadratowym, co sześciennym rozkładanej liczby.
Szczegóły tej ostatniej fazy z małymi a nie są jednak jednoznacznie wyznaczone. Warunek a+b=p nie wskazuje dokłądnie dzielnika, lecz wartość przybliżoną. Należy zastosować drugie kryterium, które działa dla przesuniętej wartości p o 2: naprzemienna suma jest równa zero, ale nie mamy jednak tutaj zbieżności, lecz skok. Zbieżność możemy uzyskać, gdy zapiszemy b oraz c w bardzo specyficznej postaci, zmieniając p z odpowiedniej strony:
a*p^2 + (a+b)*p + (b-c) = n
c dąży do b, a jest ustalone.
Jeszcze jeden przebieg konwersji dla gigantycznych a, małych p.
Można spakować wszystkie cyfry większe niż cyfra setek do cyfry setek bez utraty danych. Konwersję o r=2 jest wtedy wygodnie przedstawić:
ap^2 + bp + c,
gdzie a jest gigantyczne, pozostałe zwykłe cyfry systemu o podstawie p. Przekształcenie rekursywne, najpierw tylko dla a:
a'= a-floor( 2a/(p+2) ), b'=b-remainder(2a/(p+2))
i naprawa, potem powtórzyć jeszcze raz dla wszystkich cyfr.
Wartość z pozycji setek jest szybko tłumiona przy wzroście p.
Brak komentarzy:
Prześlij komentarz