Kiedy opisywałem faktoryzację korzystając z podstaw parzystych, wspomniałem o konwersji o większą wartość. Przykładowo przechodzenie na system o 8 więcej, o 16 więcej itp.
Kiedyś proponowałem coś takiego: mając liczbę [a, b] konwersja o 8 polega na przekształcceniu [a, b-8a], po czym naprawa powstałych cyfr za pomocą przeniesień.Wartości przechodzą na cyfrę mniej znaczącą, potem wracają na początkowe miejsce.
Okazuje się, że istnieje możliwość takiego przekształcenia, że do cyfry mniej znaczącej trafia tylko reszta. Nawet mocniej. Nie zawsze musimy mnożyć przez różnicę podstaw docelowej i początkowej.
Pokażę to na przykładzie konwersji z podstawy 20 na 28. Różnica podstaw 8. Ale największy wspólny dzielnik podstaw to 4. Możemy niejawnie 'przejść' na system 20/4 =5, przeliczyć nową wartość różnicy jak dla 8/4=2, oraz 'wrócić z powstałego' siódemkowego. Te przechodzenia zawierają przekształcenia przeciwne, czyli wzajemnie się niwelują. Pozostaje mnożenie przez 2 cyfry w dwudziestkowym, oraz reszta dla cyfry mniej znaczącej jest mnożona przez 4.
Więcej, możemy od razu oszacować wartość w nowym systemie, dobierając resztę tak, by nie mieć nadmiaru bądź niedomiaru w cyfrze.
Przykład: przeliczyć [17 14] _20 na system o podstawie 28
największy wspólny dzielnik systemów to 4, oraz 28/4=7. Jest to wielokrotność, która pozostaje przy cyfrze.
2*17/7 daje modyfikatory 4 i resztę 6, ale możemy być 'sprytniejsi' i weżmiemy 5 oraz resztę -1. Wtedy zamiast odejmować 6*4 od 14 dodamy doń 1*4.
Teraz odejmiemy znaleziony modyfikator od cyfry dziesiątek, resztę od cyfry jedności:
[17-5, 14-(-1)*4] = [12, 18] _ 28
Cyfry najmniej znaczącej nie przekształcamy. Otrzymujemy poprawną wartość cyfr w nowym systemie!
Modyfikatory odejmujemy dopiero po użyciu cyfr. Obliczenia są tak łatwe, że przy odrobinie wprawy wiemy kiedy brać nieco więcej, oraz rzadko kiedy potrzebne są dodatkowe przeniesienia między cyframi.
Przypominam, że konwersja polega na iteracyjnym dołączeniu cyfry od liczby, przekształceniu wszystkich cyfr uzyskanego podciągu.
Fragment takich obliczeń (dołączamy kolejną cyfrę 21):
z systemu 28 na system 36 (wspólny dzielnik 4), zmodyfikowana podstawa to 36/4=9
[4, 13, 11, 21] _28 podciąg cyfr podczas konwersji, ((4*36+13)*36+11)*28+21
[8, 26, 22, ] podwojone cyfry
[1*9-1, 3*9-1, 2*9+4, ] wyłuskanie modyfikatorów - wielokrotności 9 i reszt
[4-1, 13-3, 11-2, 21] uwzględnienie modyfikatorów
[4-1, 13-3+4, 11-2+4, 21-16] uwzględnienie poczwórnych reszt
[3, 14, 13, 5] _ 36 nowa wartość podciągu ((3*36+14)*36+13)*36+5
Jeśli największy wspólny dzielnik podstaw to 1, nie możemy skorzystać z tego sposobu.
Brak komentarzy:
Prześlij komentarz