Kod w poprzednim poście można przedłużyć, i teraz zaprezentuję to przedłużenie. To też jest algorytm faktoryzacji, tutaj "odwracający" kierunek sprawdzeń w tym sensie, że współczynnik a maleje od pierwiastka kwadratowego z liczby rozkładanej n do 1.
Kod ma 'tylko' pierwiastek kwadratowy z n iteracji. Jednak w testach okazał się wolny. Zaprezentuję go z funkcją użytą w poprzednim kodzie, conversion1(n,p), która wyraża liczbę w postaci c*p*p+a*p+b = n dla c=0. Chociaż dla tych wartości lepiej użyć modyfikacji pobranych z rozwinięcia (a-1)*(b+1) = a*b+b-a-1. Dzielenie będzie zastąpione dodawaniem i odejmowaniem.
Jeszcze jedna uwaga, użyta funkcja floorSqrt(n) zwraca całkowito-liczbowy pierwiastek kwadratowy oraz jego różnicę od wartości, tzn. jeśli f,g = floorSqrt(n), to n = f*f+g, 0 <= g < 2*f+1.
Numery linii oznaczają wcięcia, jak przy bardziej dopracowanych, publikowanych przeze mnie kodach w Pythonie 2.
0def factor4(n):
1 a,b = floorSqrt(n)
1 if 0==b and n==a*a: return [a,a]
1 p = a
1 k=1
1 while 1<a:
2 if b<a:
# if 1==p%2: #dzielnik bywa pomijany np. 55
# p+=2
# k=2
# else:
3 p+=1
3 k=1
3 c,a,b = conversion1(n,p)
2 else:
3 k = b/a
3 if 0==b%a:
4 p += k
4 q = n/p
4 print "dzielnik p",p, q
4 return [p,q]
3 p = p+k+1
3 c,a,b = conversion1(n,p)
2 print "[",a,",",b,"]_",p," ",k
1 return [n]
Zakomentowana instrukcja if miała zmiejszyć krotność iteracji dla wartości nieco większych niż sqrt n, by sprawdzać tylko nieparzyste, ale okazało się, że niektóre iloczyny nie są wtedy rozkładane. Taką liczbą jest 55 = 5*11.
Kod ma kolejną wadę opóźniajacą faktoryzację: zwraca wartość będącą pierwszą [n], lub dwie [p,q], ale nie wiadomo, czy p oraz q są pierwsze czy złożone. Zatem funkcja wywołująca factor4(n) musi ją wywołać ponownie dla tych wartości. Przy programowaniu współbieżnym wyniki można odkładać do tablic, i rzut wskaźnikiem (czytaj: rzut okiem) na długości tych tablic wskazuje, czy dzielniki są znalezione, jakie są, ale to nie będzie pełny rozkład.
Tak też można...
Brak komentarzy:
Prześlij komentarz