05 stycznia 2021

Możliwość dalszej modyfikacji znajdowania największego wspólnego dzielnika

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: