Szuka się dzielników liczby w różny sposób. Ale w żadnym miejscu nie spotkałem zwykłego odwrócenia mnożenia. Domyślam się, co jest tego powodem - przeniesienia. Kiedy próbowałem znaleźć funkcję odwrotną do mnozenia od cyfr najmniej znaczących, przeniesienia wyzwalały nieoznaczoność, dzięki czemu znajdowałem zaledwie cyfrę najmniej znaczącą (też nie w każdym przypadku).
Jest jeszcze jeden problem - znajomość długości dzielników, czyli liczność ich bitów. To skomplikowało jeden z algorytmów, w których dopasowywałem liczbę do wzorca bitowego.
Niech zatem a i b będą stosunkowo małymi liczbami binarnymi, oraz dla pewnego wykładnika potegi k mamy
a*b*2^k <= N < a*(b+1)*2^k .
Dalej będę dopasowywał liczbę binarną N do wzorca binarnego W o wartości N, ale subtelniej.Wzorzec przypomina liczbę, lecz na pozycji cyfr mogą stać dowolne liczby nieujemne, ograniczone z góry krotnością bitów przypuszczalnych dzielników. Tzn. jeśli dzielnik ma 7 cyfr, w tym 3 ustawione bity, na żaden pozycji wzorca wartość nie przekroczy 3. Dla liczby 7-bitowej z siedmioma ustawionymi bitami na żadnej pozycji wzorca nie pojawi się wartość większa niż 7.
Na wzorzec najlepiej spojrzeć jak na iloczyn pisemny dwu liczb binarnych, w których nie dokonaliśmy przeniesień, czyli np. 11b * 111b = [1 2 2 1] (po trzech przeniesieniach 10101b).
Pierwsze spostrzeżenie, długość a można przenosić do długości b, o ile a kończy się zerami, tzn. ab = 1100*101 = 11*10100.
A najlepiej niech a i b zaczynają się i kończą ustawionymi bitami, a potrzebną długość pobieramy z k. Dlatego pozwalam by liczba 'binarna' a kończyła się dwójką, np. 12b = 1*2+2=4.
Spstrzeżenie drugie, gdy liczba po lekkiej modyfikacji a_{m+1) = 2a_m będzie mniejsza niż liczba o cyfrach najbardziej znaczących 10..020..011... (krotność zer jest równa), dzielniki na pewno zaczynają się od 10..0... z daną krotnością. W tym przypadku suma długości a*b i potęgi k jest długością liczby N. W innym przypadku suma długości a*b i k jest o 1 mniejsza.
Spostrzeżenie trzecie, jeśli wciskamy liczbę N we wzorzec W dla znalezionych wartości a*b*2^k, możliwe maksymalne przeniesienie cyfr bardziej znaczących N jest pojedynczym bitem na pozycji k+1. Zmniejszając tę wartość znika jedno z przeniesień.
I wydaje mi się, że te spostrzeżenia wystarczą do wyznaczenia dzielników.
Przyjmujemy a=11 lub a=12, dopasowujemy b tak, by schemat dla a*b*2^k był tylko odrobinę większy niż N. Długość b ma być nie mniejsza niż długość a. Dopasowujemy najbardziej znaczące cyfry binarne N do wzorca. Często uzyskamy za dużo, co oznacza, że wzięta została za duża wartość a, należy ją zmniejszyć. Niech jednak a nie kończy się zerem, lecz wartością 1, 2.
Powinniśmy sprawdzić, czy przypadkiem nie trafiliśmy już na dzielnik.
Jeśli już przekształcimy co się da, zwiększamy a=2a+1 i znów dopasowujemy b oraz N do wzorca dla a*b.
Ciąg (a) w kolejnych iteracjach powinien rozbieżnie dążyć do dzielnika. Tyle teoria wg jednego przykładu. A jak praktyka w ogólności?
Brak komentarzy:
Prześlij komentarz