Rekurencyjne potęgowanie przez mnożenie

Witam, w pewnym zadaniu mam podany taki algorytm i mam wydedukować co on robi (załącznik: algorytm). Mam też podaną odpowiedź (załącznik: odpowiedź), i co do niej właśnie mam pytania.

Dlaczego przyjmujemy, że n to akurat 3*a+b? I dlaczego rozważamy to oddzielnie dla n < 3 i n > 2?
Czy można jakoś prościej zgadnąć, co ten algorytm robi?

Byłbym bardzo wdzięczny za pomoc

Pozdrawiam

To jest lekka modyfikacja algortmu square then multiply, gdzie zamiast square / podnoszenia do 2 potęgi masz podniesienie do potęgi 3, ale idea jest taka sama.

1. Dziwne pytanie. Każdą liczbe można zapisać w postaci 3*a + b gdzie a,b są całkowite i b<3, a tutaj jest to wygodne bo masz w algrytmie dwie ścieżki -> dla liczby podzielnej przez 3 (czyli b=0) oraz dla niepodzielnej (czyli 0<b<3). W rzeczywistości rozważasz dwie ścieżki w zależności od wartości n mod 3. Więc masz opcje n mod 3 == 0 lub n mod 3 != 0. Kongruencja n mod 3 == X znaczy tyle samo co istnieje pewna liczba całkowita k taka że 3*k + X = n.
2. Rozważasz to oddzielnie bo to jest corner case -> dla n < 3 zmienna a=0 i b=n

Czy można jakoś prościej zgadnąć, co ten algorytm robi?

Możesz rozpisać sobie wyniki dla kilku kolejnych wyrazów i próbować zgadnąć regułę ;]

Ten pseudokod (Python) działa (zwraca x do potęgi n):

def pow(x, n):
	if n == 1:
		return x
	else:
		if n % 3 == 0:
			k = pow(x, n // 3)
			return k * k * k
		else:
			return x * pow(x, n - 1)

Teraz, Zobacz tutaj (exponentiation by squaring): https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method
Też potęguje, i Porównaj do Twojego algorytmu:
jeśli x mod 3 == 0 zwróć; F(x, n div 3) * F(x, n div 3) * F(x, n div 3)
jeśli nie, to zwróć: x * x ^(n - 1) = x^n.
Czyli, jak trafi na liczbę podzielną przez 3 to zwróci iloczyn trzech wywołań, a jak nie to będzie pomniejszać n(aż będzie podzielne przez 3) i tak dalej; w każdym razie będzie to potęgowanie. Złożoność na pewno jest większa niż O(logn).
EDIT: Takich algorytków Możesz tworzyć więcej, weźmy 5:

def pow(x, n):
	if n == 1:
		return x
	else:
		if n % 5 == 0:
			k = pow(x, n // 5)
			return k * k * k * k * k
		else:
			return x * pow(x, n - 1)

print(pow(2, 3)) # -> 8...