27 czerwca 2013

Ostatni algorytm faktoryzacji, jeszcze raz z przykładem i złożonością

-->
Opiszę jeszcze raz dokładnie ostatni algorytm faktoryzacji, z próbą policzenia złożoności. 
-->
Nieparzystą liczbę rozkładaną n spełniającą warunek 22i < n <22i+1 dla pewnego i zapisujemy jako iloczyn dwu wartości n = a*b+c, gdzie a2=(2i)2 < n, c<a.
Szukamy z założenia dzielników nieparzystych wykorzystując konwersję do podstawy parzystej o 2 większą, eliminując dzielnik 2 na początku algorytmu. Liczby złożone n mające dzielniki z przedziału (2i, 2i+1) mają następującą postać:
a*b+a = a*(b+1)
dla podstaw p=b+1 parzystych. Mamy 2i-1 przypadków złożoności konwersji zmiany systemu o 2.
Przygotowanie do faktoryzacji to przekształcenie liczby n w trójkę [a,b,c], w której a=2i jest największe możliwe, b jest częścią całkowitą n/a oraz c jest resztą z dzielenia n/a.
Jeden z procesorów konwertuje liczbę n na systemy o coraz większych podstawach, oraz przesyła postać [a, b, c] drugiemu procesorowi. Drugi dokonuje konwersji na systemy o coraz mniejszych podstawach.

Konwersja liczby n = [a,b,c], gdzie n = a*b+c na system o 2 większy. Praktycznie cyfra setek oraz cyfra dziesiątek są złączone w jedną liczbę dla zastosowania tożsamości
[a, b, c] = [a+2, b-e, c-2b+e(a+2)]
oraz a:=a+2; b:=b+e; c:=c-2b+e(a+2). Wartość e jest dobierana empirycznie w taki sposób, by c-2b+e(a+2) miała wartość dodatnią nie większą niż a+2. Złożoność konwersji zwiększania systemu o 2.
a = a+2, złożoność bitowa i = O(log n), gdyż a ma długość i oraz i=log n;
c = c+[(a+2)]*-b-b, dwa odejmowania oraz do 6 dodawań, złożoność nie przekracza 6*log n, zwiększanie e jest w czasie stałym bitowo; dochodzą porównania możliwości odjęcia przy zachowaniu znaku, wykonywane w czasie liniowym bitowo, razem O(log n);
b = b-e, jedno odejmowanie małej liczby zawierającej co najwyżej 3 bity, prawie stałe;
a==c, porównania wykonywane w czasie liniowym O(log n).
Podsumowując, konwersja wykonywana jest O( log n * 2-1+log n) = O(n log n) bitowo.

Konwersja liczby n = [a, b, c] gdzie n = a*b+c na system dwukrotnie mniejszy. Postać liczby a = 2kd, gdzie 2 i d są względnie pierwsze.
[2*a, b, c] = [a, 2*b + f, c-f*a] .
Współczynnik sterujący f przyjmuje wartość 1, kiedy c>a, w przeciwnym przypadku 0. Procedurę kontynuujemy, dopóki a będzie parzyste. Krotność pętli jest równa k < i = log n.
Wyliczona wartość c jest porównywana z zerem, gdyż wtedy a oraz b są dzielnikami. Mamy do czynienia z dużą licznością przypadków, ale istnieje ograniczenie, gdyż szereg 1 + ½ + ¼ + ... +2-i jest zbieżny do 2. Współczynniki szeregu wskazują liczność przypadków z k=1, k=2, ..., k=i odpowiednio dla wszystkich pobranych argumentów przedziału [2i, 2i+1).
Złożoność konwersji podwajania podstawy.
a = a/2, przesunięcie bitowe liczby mniejszej niż pierwiastek z n, O(log n)
b = 2b + f, przesuniecie bitowe liczby zwiększanej do n, z ewentualnym dodaniem 1, O(n)
c = c-f*a, przy ustawionej fladze odejmowanie O(log n), w przeciwnym razie O(1).
Podsumowując, konwersja ta wykonywana jest k razy dla danych wejściowych, liczność z wykorzystaniem pierwszej z konwersji sumuje się do O( n 2i-1 ) * O( 2*2i-1*n ) = O( n2 log n * 2i-1*2*2i-1 ) = O( n2 log n 22i-1 ) = O(n2 (log n)3 ) = O( 22log n (log n)3 ) .


Przykład n = 8934053, rozkład całkowity
Początek każdej linii: wyrażenie powstałe z konwersji z systemu o 2 większej, po ‘=’ konwersje z połowioną podstawą.
Inicjacja (znajdowanie najmniejszej potęgi 2i większej niż pierwiastek):
1*8934053+0 = 2*4467026+1 = 4*2233513+1 = 8*1116756+5 = 16*558378+5 = 32*279189+5 = 64*139594+37 = 128*69797+37 = 256*34898+165 = 512*17449+165 = 1024*8724+677 = 2048*4362+677
2048*4362+677 Start algorytmu
2050*4358+153 = 1025*8716+153
2052*4353+1697 = 1026*8707+671 = 513*17415+158
2054*4349+1207 = 1027*8699+180
2056*4345+733 = 1028*8690+733 = 514*17381+219 = 257*34762+219
2058*4341+275 = 1029*8682+275
2060*4336+1893 = 1030*8673+863 = 515*17347+348
2062*4332+1469 = 1031*8665+438
2064*4328+1061 = 1032*8657+29 = 516*17314+29 = 258*34628+29 = 129*69256+29
2066*4324+669 = 1033*8648+669
2068*4320+293 = 1034*8640+293 = 517*17280+293
2070*4315+2003 = 1035*8631+968
2072*4311+1661 = 1036*8623+625 = 518*17247+107 = 259*34494+107
2074*4307+1335 = 1037*8615+298
2076*4303+1025 = 1038*8606+1025 = 519*17213+506
2078*4299+731 = 1039*8598+731
2080*4295+453 = 1040*8590+453 = 520*17180+453 = 260*34361+193 = 130*68723+63 = 65*137446+63
2082*4291+191 = 1041*8582+191
2084*4286+2029 = 1042*8573+987 = 521*17157+466
2086*4282+1801 = 1043*8565+758
2088*4278+1589 = 1044*8557+545 = 522*17115+23 = 261*34230+23
2090*4274+1393 = 1045*8549+348
2092*4270+1213 = 1046*8541+167 = 523*17082+167
2094*4266+1049 = 1047*8533+2
2096*4262+901 = 1048*8524+901 = 524*17049+377 = 262*34099+115 = 131*68198+115
2098*4258+769 = 1049*8516+769
2100*4254+653 = 1050*8508+653 = 525*17017+128
2102*4250+553 = 1051*8500+553
2104*4246+469 = 1052*8492+469 = 526*16984+469 = 263*33969+206
2106*4242+401 = 1053*8484+401
2108*4238+349 = 1054*8476+349 = 527*16952+349
2110*4234+313 = 1055*8468+313
2112*4230+293 = 1056*8460+293 = 528*16920+293 = 264*33841+29 = 132*67682+29 = 66*135364+29 = 33*270728+29
2114*4226+289 = 1057*8452+289
2116*4222+301 = 1058*8444+301 = 529*16888+301
2118*4218+329 = 1059*8436+329
2120*4214+373 = 1060*8428+373 = 530*16856+373 = 265*33713+108
2122*4210+433 = 1061*8420+433
2124*4206+509 = 1062*8412+509 = 531*16824+509
2126*4202+601 = 1063*8404+601
2128*4198+709 = 1064*8396+709 = 532*16793+177 = 266*33586+177 = 133*67173+44
2130*4194+833 = 1065*8388+833
2132*4190+973 = 1066*8380+973 = 533*16761+440
2134*4186+1129 = 1067*8373+62
2136*4182+1301 = 1068*8365+233 = 534*16730+233 = 267*33460+233
2138*4178+1489 = 1069*8357+420
2140*4174+1693 = 1070*8349+623 = 535*16699+88
2142*4170+1913 = 1071*8341+842
2144*4167+5 = 1072*8334+5 = 536*16668+5
2146*4163+255 = 1073*8326+255
2148*4159+521 = 1074*8318+521 = 537*16636+521
2150*4155+803 = 1075*8310+803
2152*4151+1101 = 1076*8303+25 = 538*16606+25 = 269*33212+25
2154*4147+1415 = 1077*8294+338
2156*4143+1745 = 1078*8287+667 = 539*16575+128
2158*4139+2091 = 1079*8279+1012
2160*4136+293 = 1080*8272+293 = 540*16544+293 = 270*33089+23 = 135*66178+23
2162*4132+669 = 1081*8264+669
2164*4128+1061 = 1082*8256+1061 = 541*16513+520
2166*4124+1469 = 1083*8249+386
2168*4120+1893 = 1084*8241+809 = 542*16483+267 = 271*32966+267
2170*4117+163 = 1085*8234+163
2172*4113+617 = 1086*8226+617 = 543*16452+617
2174*4109+1087 = 1087*8219+0 
Dzielniki 8934053 = 1087*8219


Modyfikacje:
Najgorsze dla złożoności jest sprawdzanie przypadków dzielników mniejszych niż 2i. Dużo można zdziałać modyfikując ten fragment. Można to zrobić przez eliminację złożoności, kosztem utraty znajomości drugiego z dzielników, lub zmniejszając krotność przypadków do sprawdzenia.
1) mniejsza złożoność.
Nie musimy znać kolejnego dzielnika, gdyż znajdziemy go później dzieląc n przez znaleziony. Dlatego dla drugiego procesora nie przysyłamy trójki [a, b, c], ale parę [a, c]. Wewnątrz znika nam warunek mnożenia 2 przez b złożoności bitowej O(n) zastąpiony operacjami złożoności bitowej O( log n). Łącznie uzyskujemy złożoność bitową
O( n log n * (log n)3 ) = O( n (log n)4 ).
2) wielokrotność reszty daleko od dzielnika.
Aby uzyskać przypadek, że dla danego a uzyskamy c-a=0, wartości c zbyt małe lub zbyt duże będą skutkowały niepotrzebnym sprawdzaniem. Aby go chociaż częściowo eliminować, do procesora drugiego dołączamy informację o k, czyli czwórkę [a, b, c, k],
Kiedy mamy połowić podstawę systemu a=2kd przy odpowiednio małej wartości c, sprawdzamy, czy a > 2kc. Jeśli tak, pętlę można opuścić, c nie będzie na tyle duże, aby wskazać dzielnik.
Podobna sytuacja jest dla c=a-1. Tu w każdej iteracji c będzie malało, lecz za mało, by wskazać dzielnik.
3) szybkie wskazanie małych dzielników.
Podejście 2) potrafi zmniejszyć liczność rozpatrywanych przypadków. Lecz małe dzielniki można wykryć jeszcze szybciej, obliczając nwd(a,c) spośród wartości [a, b, c] przesyłanych do procesora drugiego. Algorytm ten mocno pogarsza złożoność, i działa dobrze zwłaszcza przy istnieniu małych dzielników. Czasem policzenie nwd(b,c) wskaże dzielnik jeszcze szybciej, lecz z uwagi na duże wartości nie jest zalecany.
4) wiele procesorów
Dotychczas rozważane było użycie dwu procesorów. Nic nie stoi na przeszkodzie, by przedział [2i, 2i+1) podzielić na kilka przedziałów oraz rachować w każdym z nich niezależnie. Wystarczy odpowiednio wcześnie podczas przygotowania wyznaczyć podstawy dla granic przedziałów.

Brak komentarzy: