Mamy dwa sposoby podejścia do konwersji, rekursywny, który najczęściej stosuję, oraz iteratywny, korzystający pośrednio z wzorów skróconego mnożenia typu (a+kb)^i.
Szukanie rozkładu to dla mnie jest już szukanie systemu, w którym cyfra najmniej znacząca, cyfra jedności jest zerem, albo suma cyfr jest wielokrotnością podstawy systemu. W obu przypadkach zmienia się krotność cyfr zapisu dzielników liczby.
Zapis może zmienić sposób patrzenia, oraz ujawnić nowe możliwości. I tak się stało niedawno.
Skoro liczbę złożoną można przedstawić jako [a, a]_p, to będę odejmował stałą wartość takiej postaci od liczby. Po drobnych kłopotach z zapisem, okazało się, że jest to przekształcenie iteracyjne konwersji.
Najpierw sposób. Mam liczbę w postaci ciągu cyfr w systemie pozycyjnym o podstawie p. Chcę zabrać równowartość cyfry najbardziej znaczącej.
Tworzę wielomian współczynników Newtona mnożonych przez kolejne potęgi dwójki, np.
[1, 12=2*6, 60=4*15, 160=8*20, 240=16*15, 192=32*6, 64]
oraz w liczbie n za pomocą przeniesień nadaję poszczególnym cyfrom wartości większe niż w wielomianie, np. z liczby n = [5, 0, 5, 2, 3, 1, 7] _p=11 tworzę:
[1, 36, 71, 163, 246, 192, 66]_11
Po odjęciu wielomianu po pozycjach mam wartość o mniejszej krotnosci cyfr (początkowe zero do zignorowania):
[0, 24, 11, 3, 6, 0, 2]
z którą postępujemy analogicznie. Kończymy gdy uzyskamy jedną cyfrę.
Odjęcie wartości wielomianu jest odjęciem wielokrotności potęgi 13. Początkowe cyfry (odejmowane) tworzą zapis cyfr systemu trynastkowego właśnie dzięki wielomianowi (11+2)^6 .
I tak powstał nowy zapis sposóbu konwersji, mający więcej obliczeń niż wersja rekursywna.
Jako wniosek, zauważam, że skoro suma cyfr ma być wielokrotnością podstawy, to dla liczby zapisanej w postaci potęg dwójki w miejscu cyfr poza cyfrą jedności, np. [8, 4, 2, 7]_ 31 nia ma szans na dzielniki bliskie 31, 62, 124 itd. przy podwajaniu podstawy. Bo przy konwersji p*2 suma cyfr maleje. Zaś dla dzielnika ma sięgać podstawy. Suma cyfr może wzrosnąć tylko podczas przeniesienia jedynki do cyfry mniej znaczącej, tu o połowę podstawy. Stąd dwa przeniesienia, i suma cyfr wzrasta powyżej podstawy systemu (podwojonemu).
Możemy nawet wzmocnić ograniczenie, by było tylko jedno przeniesienie i suma odpowiednio mała, by zigrorować szukanie dzielników w okolicy.
Uwaga - przeniesienia mogą się propagować, jak przy [7, 4, 4, 1]_p = [3, n+p/2, 2, 1]_2p.
Brak komentarzy:
Prześlij komentarz