Mam już napisany program do faktoryzacji z rodziny rozwiązań odwracających działania. Nie wydaje się mi się bardzo szybki, ale to dlatego, że każę mu wypisywać w każdej iteracji drzewo możliwości, aby móc obserwować jego działanie. To wypisywane jest właśnie bardzo wolne.
Algorytm do działania potrzebuje listy początkowych liczb pierwszych primes = [3,5,7,...] oraz iloczynów początkowych liczb pierwszych product = [6,30,210,...] = [2*3, 2*3*5, 2*3*5*7, ...]. Liczba pierwsza 2 nie jest uzwględniona w tablicy primes, ale w product już tak.
Tablice te w razie potrzeby trzeba rozszerzać, choć dla testowanych przypadków kilkunastucyfrowych wystarczy naledwie kilka liczb pierwszych oraz ich iloczynów. Rozszrzerzanie tych tablic w razie potrzeby o kolejną liczbę pierwszą, jej iloczyn z pozostałymi, stanowi część funkcji.
Zasada iteracji jest następująca: na drzewie mam już odłożone iloczyny a*b mające tę samą resztę co product[i-1]. Rozszerzenie do iloczynu product[i] o liczbę pierwszą p ma tworzy specyficzną budowę:
a = a+k*product[i-1], k=0..p-1
b = b+j*product[i-1], j=0..p-1
Jest ich p^2. Spośród nich wybieram te a*b, które mają tę samą resztę co liczba rozkładana n modulo product[i], oraz nie mogą być zbyt duże. Te odkładam do drzewa (a,b,i), chyba, że iloczyn pokrywa sie z n, wtedy następuje koniec funkcji, zwrócenie wyniku n = a*b. W drzewie trzymam dodatkowo indeks i, będący zarazem poziomem drzewa
Inicjacja, gdy n modulo 6 jest 1, odkładam dwie pary (1,1, indeks 1), (5,5, 1), gdy n modulo 6 jest 5 odkładam (1,5, 1).
Dla liczb kilkunastocyfrowych poziom drzewa nie przekracza 10, a kiedy pisałem ten post, zanim zapisałem pierwsze dwa akapity, już uzyskałem rozkład:
9198491200007 = 197 * 109 * 428374759
poziom drzewa czyli długość tablic pomocniczych nie przekraczał 8.
Podstawowa trudność spowalaniająca przy odkładaniu a*b była tą, że obliczenia były wykonywane także dla równoważnej pary b*a. Niepotrzebnie. Po wyłapaniu tych przypadków program zyskał zauważalnie na szybkości. Oraz osobno sprawdzam podzielność przez 2, 3.
Program lepiej działa dla większych wartości. Liczby gładkie mają zbyt dużo równoważnych iloczynów, co powoduje mocny rozrost drzewa. Z kolei liczby pierwsze i półpierwsze są rozpoznawane znacznie szybciej.
Nie wiem dlaczego, ale intuicja podpowiada mi, że dopasowywanie par (a,b,) warto zacząć od większych wartości, i zmniejszać w kierunku wartosci z poprzedniej iteracji.
Brak komentarzy:
Prześlij komentarz