Witam, otrzymałem takie oto zadanie:
Podaj, w jaki sposób zostanie obliczona wartość potęgi \(\displaystyle{ x^{n}}\) za pomocą możliwie najmniejszej liczby mnożeń dla wykładnika, który jest dany jako liczba w systemie trójkowym: \(\displaystyle{ n = (1212)_{3}}\). Zapisz ciąg kolejno wykonywanych mnożeń w tym przypadku. Ile ich jest?
Znam algorytm na potęgowanie, który działa dla wykładnika zapisanego w systemie binarnym, szukałem jakiejś analogii, którą można by się posłużyć dla systemu trójkowego, jednak na razie nie znalazłem nic takiego.
[Algorytmy] Potęgowanie, wykładnik w systemie trójkowym
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: [Algorytmy] Potęgowanie, wykładnik w systemie trójkowym
Ponieważ ilość mnożeń nie zależy od systemu liczbowego w jakim jest podany wykładnik to przejdź na system decymalny lub binarny i wskaż liczbę mnożeń.
W dziesiętnym \(\displaystyle{ x^{50}}\) wymaga siedmiu mnożeń:
\(\displaystyle{ x \cdot x=x^2\\
x^2 \cdot x^2=x^4\\
x^4 \cdot x^4=x^8\\
x^8 \cdot x^8=x^{16}\\
x^{16} \cdot x^{16}=x^{32}\\
x^{32} \cdot x^{16}=x^{48}\\
x^{48} \cdot x^{2}=x^{50}}\)
W binarnym \(\displaystyle{ 1212_3=50_{10}=110010_2}\) ilość mnożeń ustal wg swojego algorytmu.
W dziesiętnym \(\displaystyle{ x^{50}}\) wymaga siedmiu mnożeń:
\(\displaystyle{ x \cdot x=x^2\\
x^2 \cdot x^2=x^4\\
x^4 \cdot x^4=x^8\\
x^8 \cdot x^8=x^{16}\\
x^{16} \cdot x^{16}=x^{32}\\
x^{32} \cdot x^{16}=x^{48}\\
x^{48} \cdot x^{2}=x^{50}}\)
W binarnym \(\displaystyle{ 1212_3=50_{10}=110010_2}\) ilość mnożeń ustal wg swojego algorytmu.