Opisałem pod koniec kwietnia konwersję dla większych przyrostów liczb w poście 'szczegolny przypadek konwersji'
Postanowiłem zastosować ten sposób do bardzo starej definicji, z którą zaczynałem zabawę z systemami niedziesiętkowymi.
Mianowicie p^n = \sum _{i=0} ^{n} \binom (n, i) (p-1)^i = ((p-1)+1)^n
Rozpisanie ze wzoru skróconego mnożenia jest automatyczną konwersją z systemu o podstawie p na system o podstawie p-1, ogólniej:
p^n = ((p-r)+r)^n
Związane są z tym potęgi przyrostu r oraz wzory na kombinacje. Kiedyś uważałem, że te duże wartości pojawiajace się we wzorze sprawią, że obliczanie będzie nieefektywne. I tak jest, dopóki znaleziona konwersja nie uwidoczniła mi, że te, skąd inąd potencjalnie ogromne wartości mogą się wzajemnie skracać. Wystarczy więcej przekształcać niż obliczać.
Każda cyfra przy konwersji wpływa na wszystkie cyfry mniej znaczące. Inaczej, każda cyfra zależy od pewnego wyrażenia od wszystkich cyfr bardziej znaczących.
Przekształcenie dla przyrostu r okazało się następujące dla cyfry i-tej:
a_i += 1/(p+r) (sum _{j>i} (-r)^{j-i} \binom (j, i) a_{j-1} )
dla cyfry na danej pozycji, reszta z dzielenia przechodzi bez żadnych modyfikacji do cyfry mniej znaczącej. Cyfra najmniej znacząca nie bierze udziału w przekształceniach, jest tylko modyfikowana resztą z pozycji dziesiątek.
W ten sposób bozbyliśmy się rekursji przy konwersji, pozostają dwa przebiegi. Główny liczony wielowątkowo oraz drobna korekta związana z naprawą cyfr.
Przykład: Mamy liczbę w 548321 w systemie dziewiątkowym. Należy podać tę liczbę w dziesiątkowym.
Nie będę pisał symboli Newtona \binom (n, i) = n! / (i! * (n-i)! ), od razu skrócone iloczyny - wartości trójkąta Pascala widać przy współczynnikach po przekątnych;
5 + (- 5*5)/10 = 5-2 = 3 reszta -5
4 + (-4* 4 + 5* 2*5)/10 = 4+3 = 7 reszta 4
8 + (-8* 3 + 4* 2*3 - 5* 2*5)/10 = 8-5 = 3 reszta 0
3 + (-3* 2 + 8* 3 - 4* 4 + 5* 5)/10 = 3+2 = 5 reszta 7
2 + (-2 +3 -8 +4 -5)/10 = 2+0 = 2 reszta -8 albo lepiej 1 reszta 2
1
Drugi przebieg, korygujemy resztami uzyskując wynik:
3 (-5+7) (3+4) (0+5) (7+1) (2+1) = 327583
Jest to prawidłowa wartość tej liczby w systemie dziesiętnym.
Brak komentarzy:
Prześlij komentarz