Miotam się ostatnio między programowaniem w stylu gier paragrafowych, a kontynuacją wymyślania sposobów rozkładu.
Można jeszcze bardziej zmodyfikować sposób obliczania wspólnego dzielnika. Wiem już, że mogę dzielić argumenty przez małe liczby, które są podzielne przez dokładnie jeden z argumentów, oraz zatrzymać algorytm, kiedy osiągnie odpowiednio małą wartość przy narastajacej wiedzy o braku dzielników w tym zakresie.
Można to robić mniej zachłannie, co o dziwo jest w stanie zwiększyć szybkość zmniejszania się argumentów.
Jeśli oba argumenty są nieparzyste, i wiem, że wspólnym dzielnikiem nie jest wielokrostość 2 lub 5, mnożę jeden z argumentów przez małą stałą, by uzyskać taką samą cyfrę najmniej znaczącą. Następnie odejmuję. Uzyskana różnica jest podzielna przez 10, dzielę przezeń, potem jeszcze przez ewentualne dwójki. W ten sposób w jednej iteracji mogę zmniejszyć wartość o rząd wielkości.
Zobaczmy na przykładzie liczb Fibonacciego, które tworzą najdłuższy ciąg zbieżny do wspólnego dzielnika:
nwd(377, 233)
Ponieważ 3*9 = 27 mają tę samą cyfrę najmniej znaczącą, liczę nwd( 377, 9*233) = nwd( 377, 2097), Odejmuję je 2097-377 i dzielę przez 10 i jeszcze kilka 2. Uzyskuję:
nwd( 233, 43 )
Postępując jak wcześniej (tym razem cyfra 3 taka sama, bez mnożenia), dostaję
233-43 = 19*10
czyli nwd(233, 43) = nwd( 43, 19).
Można kontynuować, uzyskując w kolejnym kroku nwd (3*43, 19), lecz rozsądek podaje, by wrócić do standardu i uzyskać parę nwd(19, 5). Kolejna operacja (ze zmianą znaku) zwraca nwd (19,4*5) = nwd (19,20) = 1.
Łącznie 4 iteracje, a standardowym odejmowaniem algorytmu Euklidesa byłoby 13.
Stosuję to do sprawdzania kolejnego algorytmu rozkładu przeglądem zupełnym z sita, w którym potrzebowałem znać tablicę liczb pierwszych nie większych niż co najwyżej pierwiastek czwartego stopnia z liczby rozkładanej. Chyba nie potrzebuję znać tej tablicy kosztem dodatkowej struktury.
Brak komentarzy:
Prześlij komentarz