[Algorytmy] Potęgowanie, wykładnik w systemie trójkowym

[DuDiiC]

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.

[kerajs]

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.