W ostatnim poście pokazałem, jak można stosować cechę podzielności, ale nie wskazałem szybkiego sposobu przechodzenia z systemu na system. Za to użyłem takiego przy konwertowaniu z systemu dziesiątkowego na ósemkowy.
Zatem dodatek: szybki sposób konwersji systemów pozycyjnych.
Zanim go jednak przedstawię, oto różnica między liczbą a cyfrą.
CYFRA danego systemu liczbowego to liczba mieszcząca się między 0 włącznie oraz podstawą systemu liczbowego p, czyli w przedziale [0, p). Stanowi zarazem podstawowy składnik konstrukcji liczb. Dla małych podstaw cyfry mają własne symbole graficzne.
LICZBA [w systemie pozycyjnym] to [uporządkowany] ciąg cyfr a_n .. a_1 a_0.
W algorytmie poniższym cyfry są traktowane jako liczby, oraz w czasie początkowych przekształceń ignorujemy nałożone nań ograniczenia na wielkość.
Mając liczbę a_n...a_0 w systemie p, chcemy ją zapisać w systemie o podstawie p+r (p+r>1), stosujemy oparty na schemacie Hornera zapisu liczb
(...(a_n*p+a_{n-1})...)*p+a_0
następujący algorytm:
inicjacja: sprawdzamy przyrost r, załóżmy ze jest r>0 Bierzemy a_n, pozostałe cyfry czekają w kolejce [a_{n-1} , ... , a_0]
1) pobieramy cyfrę a_j z kolejki;
2) każdą cyfrę a_i (zaczynając od i=j, zwiększając do i=n ) modyfikujemy do liczby a_i := a_i - r*a_{i+1}, kiedy nie ma wartości i+1, traktujemy ją jako 0;
3) powstałe liczby sprowadzamy do cyfr dodając t razy (p+r) - pożyczamy od cyfr bardziej znaczących, aby liczba stojąca na miejscu cyfry była w odpowiednim przedziale;
4) poprzedzającą cyfrę a_{i+1} zmniejszamy o znalezione w 3) t;
powtarzamy 3) 4) tak długo, aż liczba będzie się składała tylko z prawidłowych w danym systemie cyfr;
5) kiedy kolejka cyfr jest pusta, uzyskujemy postać liczby w systemie (p+r), w przeciwnym przypadku wracamy do 1)
Na zakończenie modyfikujemy aktualną krotność cyfr, gdyż wartość ta może się zmienić.
Kiedy r jest dodatnie, w 2) dodajemy zamiast odejmować, zaś liczbę sprowadzamy do cyfry przez przekazywanie nadmiarów (p+r) cyfrom bardziej znaczącym.
Sposób nie jest tak szybki jak konwersje między systemami o podstawach będących potęgami jednej liczby a, w których liczbę zapisujemy przy podstawie a, a następnie cyfra powstaje z paczki odpowiedniej długości, np. konwersja z systemu o podstawie 27 na system o podstawie 9 przez system o podstawie 3:
22 2 4_{27} = 211 002 011_3 = 2 11 00 20 11_3 = 24064_9,
ale i tak znacznie szybszy niż stosowanie definicji systemów.
Przykład: przekonwertujemy szesnastkowe 0xBACA na system dziesiętny.
cyfry początkowe: [ 0xB=11, 0xA=10, 0xC=12, 0xA=10]
Początek to lista 11, mamy przyrost 10-16=-6, czyli do poszczególnych cyfr będziemy dodawać iloczyny 6
zaczynamy pierwszą iterację:
11 10+6*11
11 76
na pozycji jedności mamy liczbę! 76, którą należy zmniejszyć, aby na powrót stała się cyfrą systemu, tym razem dziesiątkowego
(11+t) (76-t*10) t=7
18 6
teraz cyfra dziesiątek jest za duża. Przenosimy nadmiar tworząc następną cyfrę, cyfrę setek.
1 8 6
Dla sprawdzenia, 11*16+10 = 186 = 1*10^2 + 8*10 + 6,
Kolejna iteracja, dołączamy cyfrę 0xC=12
1 8 6 12
1[+0] 8+6*1 6+6*8 12+6*6
1 14 54 48
przenosimy nadmiary (od razu wynik) (11*16+10)*16+12 = 2988
2 9 8 8
Ostatnia cyfra, czyli ostatnia iteracja
2 9 8 8 10
2[+0] 9+6*2 8+6*9 8+6*8 10+6*8
2 21 62 56 58
Przenosimy nadmiary
4 7 8 1 8
Zatem szesnastkowe 0xBACA to dziesiętne 47818.
W drugą stronę podobnie, lecz mamy 5 iteracji, przyrost 6. Pierwsza jest postaci
4[-0] 7-6*4
4 -17
naprawa polega na dodawaniu docelowej podstawy 16, czyli
4-2 -17+2*16
2 15
Kolejna iteracja
2 15 8
2 15-6*2 8-6*15
2 3 -82
1 13 14
Kolejna iteracja
1 13 14 1
1 13-6*1 14-6*13 1-6*14
1 7 -64 -83
1 2 10 13
Ostatnia iteracja
1 2 10 13 8
1 2-6*1 10-6*2 13-6*10 8-6*13
1 -4 -2 -47 -70
0 11 10 12 10
Ostatecznie przekształcamy te szesnastkowe cyfry na liczbę 0xBACA.
algorytmy, pomysły na rozkład liczb i arytmetykę, także systemów niedziesiątkowych; elementy programowania pod DOSem
28 stycznia 2012
23 stycznia 2012
Podzielnosc w systemach niedziesiatkowych
Ułamki egipskie oraz algorytm faktoryzacji zwrócily moja uwagę na systemy niedziesiątkowe. Na razie system binarny oraz systemy o podstawie będące potęgą 2.
Występują bardzo proste cechy podzielności dla liczb będących postaci 2^n +- 1.
Dzieląc liczbę w systemie o podstawie 2^n na paczki binarne długości n-1 znaków, liczba jest podzielna przez 2^n-1 gdy suma wartości poszczególnych paczek binarnych też jest podzielna. (por. cecha podzielności przez 9).
Dla liczb postaci 2^n+1 reszta jest równa reszcie sumy naprzemiennej tych paczek (por. cecha podzielności przez 11.
Do odpowiednich liczb należą 3, 5, 7, 9, 15, 17, 31, 33 i wiele innych.
Wystarczy przekształcić liczbę do postaci np. oktagonalnej by już mieć postać równoważną binarnej i zastosować cechę.
Przykład: sprawdzimy resztę z dzielenia 3523432 przez 17 równe 10001 binarnie.
Przekształcamy 3523432 do systemu ósemkowego, dodając do każdej cyfry z wyjątkiem pierwszej przed '|' podwojoną wcześniejszą i 'naprawiając cyfry' przez przenoszenie nadmiarów 8:
3 5 | 2 3 4 3 2
4 3 2 | 3 4 3 2
5 4 0 3 | 4 3 2
6 7 0 3 4 | 3 2
1 0 4 6 4 2 3 | 2
1 2 6 0 1 2 7 2 |
1 5 3 4 1 5 5 0
Zatem w ósemkowym liczba wyglada 15341550 = binarnie 001 101 011 100 001 101 101 000 = 0011 0101 1100 0011 011 01000 = heksadecymalnie 3 5 12 3 6 8.
Według cechy podzielności, naprzemienna suma -3+5-12+3-6+8 = -5 = 12 (17) ma taką samą resztę. Istotne są tu znaki, ale rzeczywiście, wartość ta w dziesiatkowym przedstawi się jako 207260*17+12.
Algorytm dotyczący sposobu przechodzenia między systemami jest opublikowany w następnym poście.
Występują bardzo proste cechy podzielności dla liczb będących postaci 2^n +- 1.
Dzieląc liczbę w systemie o podstawie 2^n na paczki binarne długości n-1 znaków, liczba jest podzielna przez 2^n-1 gdy suma wartości poszczególnych paczek binarnych też jest podzielna. (por. cecha podzielności przez 9).
Dla liczb postaci 2^n+1 reszta jest równa reszcie sumy naprzemiennej tych paczek (por. cecha podzielności przez 11.
Do odpowiednich liczb należą 3, 5, 7, 9, 15, 17, 31, 33 i wiele innych.
Wystarczy przekształcić liczbę do postaci np. oktagonalnej by już mieć postać równoważną binarnej i zastosować cechę.
Przykład: sprawdzimy resztę z dzielenia 3523432 przez 17 równe 10001 binarnie.
Przekształcamy 3523432 do systemu ósemkowego, dodając do każdej cyfry z wyjątkiem pierwszej przed '|' podwojoną wcześniejszą i 'naprawiając cyfry' przez przenoszenie nadmiarów 8:
3 5 | 2 3 4 3 2
4 3 2 | 3 4 3 2
5 4 0 3 | 4 3 2
6 7 0 3 4 | 3 2
1 0 4 6 4 2 3 | 2
1 2 6 0 1 2 7 2 |
1 5 3 4 1 5 5 0
Zatem w ósemkowym liczba wyglada 15341550 = binarnie 001 101 011 100 001 101 101 000 = 0011 0101 1100 0011 011 01000 = heksadecymalnie 3 5 12 3 6 8.
Według cechy podzielności, naprzemienna suma -3+5-12+3-6+8 = -5 = 12 (17) ma taką samą resztę. Istotne są tu znaki, ale rzeczywiście, wartość ta w dziesiatkowym przedstawi się jako 207260*17+12.
Algorytm dotyczący sposobu przechodzenia między systemami jest opublikowany w następnym poście.
Subskrybuj:
Posty (Atom)