Faktoryzacja liczb sprawdzająca
prawie równocześnie największe i najmniejsze dzielniki jest
możliwa do przedstawienia, chociaż algorytm jest bardziej
skomplikowany. Przedstawię szkic za pomocą pseudokodu.
Ponieważ jednak podejście jest
niestandardowe, najpierw funkcje biorące udział w algorytmach.
Liczba jest listą swoich cyfr, zaś
cyfra to liczba z przedziału [0,p), gdzie p jest podstawą systemu
liczbowego.
Last lista
zwraca ostatni element listy, w
przypadku listy będącej liczbą, jej najmniej znaczącą cyfrę.
First lista
podobnie jak last, lecz zwraca pierwszy
element listy, w przypadku liczb cyfrę najbardziej znaczącą.
Succ element
zwraca element poprzedzający dany
iterator na liście, w braku takiego zwraca 0.
Move element lista
przenosi wskazany Element dołączając
go do innej listy na koniec.
Rep [warunek] instrukcja
oznacza prostą pętlę powtarzającą
się tak długo, dopóki warunek jest prawdziwy.
Fi instrukcje warunek
oznacza funkcję, która najpierw liczy
instrukcje, a potem w zależności od warunku albo przywraca stare
wartości, albo zostawia nowe, jest bardzo podobna do funkcji If,
która robi to samo, ale w innej kolejności.
Konwersja [parametr]
tu oznacza konwersję zmniejszającą
podstawę systemu o 2, chyba, że podany jest parametr. Wtedy
zwiększa podstawę o ten parametr.
Corr [podstawa]
jest funkcją działającą na liczbach
(listach) sprawdzającą, czy liczba jest poprawnie przedstawiona, w
szczególności testuje warunki na cyfry, czy są liczbami
całkowitymi w odpowiednim przedziale. Jeśli nie, nadmiary przenosi
do cyfr bardziej znaczących, części ułamkowe jako liczby
całkowite do cyfr mniej znaczących. Działa rekursywnie kończąc
działanie, kiedy liczba jest we właściwej postaci.
Foreach lista : instrukcja
dla każdego elementu listy wykonuje
podaną instrukcję.
Algorytm konwersji Konwersja [r=2]
Wejście: Liczba n pusta, Liczba m przy
podstawie p+r, podstawa p
Rep [ m niepuste ] {
Move m.First n
Foreach n : element += r * Succ element
n.Corr [ p ]
}
Wyjście: Liczba n przy podstawie p,
jako skutek uboczny może zmieniać p o r.
Algorytm faktoryzacji korzystający
tylko z tej konwersji ma wadę: po znalezieniu dzielników nie wiemy,
czy są one pierwsze czy złożone. Należy uruchomić algorytm
ponownie dla każdego z dzielników, lub zapamiętać sprawdzonych
kandydatów na dzielniki.
Jeśli dzielnik x dzieli podstawę
systemu, aby dzielić liczbę, potrzebuje być także dzielnikiem
wyrazu wolnego. W sprawdzaniu małych dzielników ograniczymy się
tylko do iteracji, kiedy x jest dzielnikiem podstawy systemu.
Potrzebujemy trzech dodatkowych
wartości: dzielnika minimalnego xmin, maksymalnego xmax oraz
aktualnego x, inicjowanych x = xmin = 2, xmax=3.
Zaś dla większych liczb, często
łatwiej i szybciej jest testować nieco większe wartości niż
najbliższego kandydata na dzielnik. Mogą się one układać w
pewien wzorek, w którym zaczynamy sprawdzać od większego
kandydata, po czym w regularny sposób zmniejszamy do aktualnej
najmniejszej podejrzanej wartości.
Przystąpmy do samego algorytmu
faktoryzacji:
1. przygotowanie postaci liczby
najmniejszej z trzycyfrowych n = [a, b, c], znalezienie podstawy p
2. Konwersja do najbliższej podstawy p
nieparzystej i sprawdzenie dzielników xmin, x, xmax
3. dopasowanie licznika iteracji d
4. Rep [ istnieją kandydaci na
dzielniki ] {
5. if 0= (d--) sprawdzenie i ponowne
przeliczenie x, xmin, xmax, d
5a przy znalezionym dzielniku jego
wyłączenie i restart algorytmu
6. Konwersja, modyfikacja podstawy p
-=2
7. Corr [p]
8. if 0=n.Last czyli wyraz wolny równy 0, znaleziony dzielnik p; iteracyjny restart dla
liczby z usuniętym Last, oraz z tą samą wartością xmin dla
podstawy p
}
Ad 1. Chodzi o doprowadzenie do postaci
b*p+c, w której b,c<p oraz p, b są największe z możliwych. W
tym celu można przyjąć p jako sufit z pierwiastka kwadratowego
liczby. Mając już tę postać stosujemy Konwercja [1], dzięki
czemu uzyskujemy najmniejszą z możliwych liczbę trzycyfrową z a
równym 1, b równym 0 albo 1 przy danej podstawie p;
Ad 2. W tym kroku sprawdzamy warunek
p<xmin. Gdy 2=xmin, sprawdzamy podzielność przez 2 oraz
stosujemy Konwersja [1], aby nie szukać niepotrzebnie dzielników po
wartościach parzystych. Znalezione dzielniki usuwamy, i powtarzamy
algorytm ze zmodyfikowaną liczbą. Gdy xmin jest większe, dobieramy
x, xmax oraz d jak w 8;
Ad 3. Mała liczba naturalna d
wskazująca, ile iteracji pętli będziemy czekać, aż x będzie
dzielnikiem podstawy p. Jeśli nie jest wyznaczona w kroku 2,
przyjmuje wartość 1 dla liczb postaci 3k+2, 2 dla liczb postaci
3k+4, wartość d=0 wykrywa podzielność przez 3;
Ad 4. Pętla 4-8, z której istnieją
wyjścia na dwa sposoby, dla liczb pierwszych xmin>p, dla
złożonych następuje ponowne wywołanie algorytmu dla
poszczególnych dzielników z tymi samymi ustawieniami xmin;
Ad 5. W tym kroku d jako 0 wskazuje, że
x dzieli p. Sprawdzamy, czy x dzieli też n.Last, czyli cyfrę
najmniej znaczącą. Jeśli tak, mamy dzielnik x, zaś cała liczba
ulega zniekształceniu, tak że należy zrestartować algorytm. Nie można
podzielić podstawy oraz wyrazu wolnego przez x, gdyż wtedy mogą
'uciec' inne dzielniki. Jeżeli x>xmin, zmniejszamy x-=2 oraz
liczymy d z pomocą y:
y = p modulo x; d = ( y%2 ? (y+x)/2 :
y/2 )
Gdy x=xmin wstawiamy xmin = xmax oraz
sprawdzamy wartości d liczone ww wzorem dla kolejnych elementów
ciągu (p modulo (x+2*k) ). Interesuje nas podciąg malejący z
wyjątkiem ostatniego elementu, który jest większy niż
przedostatni. Taki podciąg cechuje się budową zbliżoną do (24,
22, 15, 8, 1, 17).
Przyjmujemy za xmax = (x+2*k)
ostatniego elementu, oraz x = xmax-2.
Ad 8. Liczba jest iloczynem k*p, lecz
nie wiemy, czy dzielniki są pierwsze czy złożone. Uruchamiamy
algorytm dla tych wartości z aktualnym ustawieniem xmin;
Przykład liczbowy 169 747 007 = 19 *
1087 * 8219, szkic
Liczb niepodzielna przez 2. Do
algorytmu wchodzi postać
[a, b, c] = [1, 1, 5195] przy podstawie
p=13028.
Następuje konwersja, by podstawa p
była nieparzysta p=13027 = 3k+1, liczba [1, 3, 5197] , dwie iteracje
doprowadzą do wartości p podzielnej przez 3. Obliczamy d dla p
modulo 5 uzyskując 1, dla 7 jest większe. Mamy zatem d=1, xmin = 3,
x = 5, xmax=7.
W pierwszej iteracji liczba przyjmuje
postać
[1, 7, 5207] przy p=13025.
Podstawa p jest podzielna przez 5,
lecz najmniej znacząca cyfra 5207 = 5*1041+2. Niezerowa reszta
wskazuje, że 5 nie jest dzielnikiem. Zmniejszamy x do 3, d=1.
W drugiej iteracji liczba
[1, 11, 5225]
przy p=13023,
p jest podzielne przez 3, sprawdzamy podzielność
przez 3 cyfry najmniej znaczącej 5225 = 3*1741+2.
Teraz xmin=7, dane p jest podzielne
przez 9, lecz x=9 nie jest dzielnikiem, jest 5 iteracji d=5 do
sprawdzenia 7, reszta z dzielenia przez 11 jest większa, zatem xmax=11, x=7.
Po kolejnych kilku iteracjach okazuje
się, że liczba postaci
[1, 103, 7843] przy p=12977
ma podstawę
oraz najmniej znaczącą cyfrę podzielną przez x = xmin = 19.
Następuje restart algorytmu z xmin=19.
Teraz należy powtórzyć krok 1. uzyskując postać liczby 169 747
007 : 19 = 8 934 053 jako
[1, 3, 2923] przy p=2987.
Teraz należy na
nowo wyliczyć d=2, zaś do następnego dzielnika 21 jest 13
iteracji.
Kolejną postacią liczby jest [1, 7,
2933] przy p=2985.
I tak sprawdzamy kolejne duże
dzielniki mniejsze od 2985, zarazem większe od 19.
Kiedy p opadnie do 1215, wiemy już z
xmin=135, że dzielniki są w przedziale [xmax=157, 1215) lub sprawdzane właśnie 135, do
sprawdzenia 173 dzielą nas dwie iteracje, zaś kolejne kandydatki:
171, 169, 167 i dalej dzieli taka sama krotność iteracji.
Osiągamy wreszcie postać [7, 580,
986] przy p=1089, dla której znowu następuje oczekiwanie na
sprawdzenie dzielnika 217 (xmin=175) przy p=1085, lecz kolejna
iteracja przekształca liczbę do postaci
[7, 610, 0] przy p=1087.
Mamy kolejne dzielniki: 1087 oraz 7*1087+610.
Obliczając jednak postać trzycyfrową
tych wartości okazuje się, że są one mniejsze niż xmin=175,
dzielniki są zatem liczbami pierwszymi.
Rozkład dokonany.
W algorytmie tym rachujemy na coraz mniejszych wartościach, występujące dzielenie jest przez stosunkowo bardzo małe liczby.
Brak komentarzy:
Prześlij komentarz