algorithm - 求幂 - 基于三的位置系统

Question

我有一个十进制的自然数 x 和一个三进制的自然数 n。如何使用最小乘法次数计算 x^n 的值？

我知道二进制系统的算法，我一直在寻找类比，但没有找到。

Answer 1

也许你需要这样的东西:

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)  

工作的德尔福代码

 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;

日志:

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