Exponentiation - positional system based on three

I have a natural number x in the decimal system and natural number n in a ternary numeral system. How to calculate the value of x^n using the minimum number of multiplications?

I know the algorithm for a binary system and I was looking for an analogy, but I did not find it.

1 Answer
1

Perhaps you need something like this:

function expbycubing(x, n):

//treat n = 0..2 cases here

switch n % 3:
0: return expbycubing(x * x * x, n shrt 1)
///// note shift in ternary system (tri)201 => (tri)020
1: return x * expbycubing(x * x * x, n shrt 1)
2: return x * x * expbycubing(x * x * x, n shrt 1)


Working Delphi code

function expbycubing(x, n: Integer): int64;
begin
Memo1.Lines.Add(Format('x: %d n: %d', [x, n]));
if n = 0 then Exit(1);
if n = 1 then Exit(x);
if n = 2 then Exit(x * x);
case n mod 3 of
0: Result := expbycubing(x * x * x, n div 3);
1: Result := x * expbycubing(x * x * x, n div 3);
2: Result := x * x * expbycubing(x * x * x, n div 3);
end;
end;

var
i: Integer;
begin
for i := 12 to 12 do
Memo1.Lines.Add(Format('%d: %d', [i, expbycubing(2, i)]));
end;


log:

x: 2 n: 12
x: 8 n: 4
x: 512 n: 1
12: 4096


Is the correct answer? Maybe I don't understand, but for example x = 2, n = tri(110) I have: x -> x^3 -> x^9 * x = x^10-> x^30 * x = x^31, but I should have x^12. Could you explain, please?
– M. Dudek
Jun 29 at 11:13

You unwinded recursion wrongly. When function returns from return x * expbycubing(x * x * x, n shrt 1), x still has old value, so chain is x -> x^3 -> x^9 => here x^9 * x^3 => x^12. I added execution log. The deepest level result 512 is multiplied by upper level x=8 to produce 4096
– MBo
Jun 29 at 12:31

return x * expbycubing(x * x * x, n shrt 1)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.