(Knuth's power tree is used for computing   xn   efficiently.)




Task

Compute and show the list of Knuth's power tree integers necessary for the computation of:

   xn   for any real   x   and any non-negative integer   n.


Then, using those integers, calculate and show the exact values of (at least) the integer powers below:

   2n     where   n   ranges from   0 ──► 17   (inclusive) 

   3191
   1.181


A  zero  power is often handled separately as a special case.

Optionally, support negative integer powers.



Example

An example of a small power tree for some low integers:

                                                                    1
                                                                     \
                                                                      2
                          ___________________________________________/ \
                         /                                              \
                        3                                                4
                       / \____________________________________            \
                      /                                       \            \
                     5                                         6            8
                    / \____________                           / \            \
                   /               \                         /   \            \
                  7                 10                      9     12           16
                 /                 //\\                     │      │           /\
                /            _____//  \\________            │      │          /  \
              14            /     /    \        \           │      │         /    \
             /│ \         11    13      15       20        18     24        17    32
            / │  \         │    /\      /\        │        /\      │        /\     │
           /  │   \        │   /  \    /  \       │       /  \     │       /  \    │
         19  21    28     22 23   26  25   30    40     27   36    48     33 34   64
         │   /\    /│\     │  │   /\   │   /\    /│\     │   /\    /│\     │  │   /\
         │  /  \  / │ \    │  │  /  \  │  /  \  / │ \    │  /  \  / │ \    │  │  /  \
        38 35 42 29 31 56 44 46 39 52 50 45 60 41 43 80 54 37 72 49 51 96 66 68 65 128

Where, for the power   43,   following the tree "downwards" from   1:

   (for   2)   compute square of   X,   store X2
   (for   3)   compute   X * X2,   store X3
   (for   5)   compute   X3 * X2,   store X5
   (for 10)   compute square of   X5,   store X10
   (for 20)   compute square of   X10,   store X20
   (for 40)   compute square of   X20,   store X40
   (for 43)   compute   X40 * X3   (result).
Note that for every even integer (in the power tree),   one just squares the previous value.

For an odd integer, multiply the previous value with an appropriate odd power of   X   (which was previously calculated).
  For the last multiplication in the above example, it would be   (43-40),   or   3. 


According to Dr. Knuth (see below),   computer tests have shown that this power tree gives optimum results for all of the   n
  listed above in the graph.

For   n   ≤ 100,000,   the power tree method:

   bests the factor method   88,803   times,
   ties   11,191   times,
   loses   6   times.


References

   Donald E. Knuth's book:   The Art of Computer Programming, Vol. 2, Second Edition, Seminumerical Algorithms, section 4.6.3: Evaluation of Powers.
   link   codegolf.stackexchange.com/questions/3177/knuths-power-tree     It shows a   Haskell,   Python,   and a   Ruby   computer program example   (but they are mostly   code golf).
   link   comeoncodeon.wordpress.com/tag/knuth/     (See the section on Knuth's Power Tree.)     It shows a   C++   computer program example.
   link to Rosetta Code   addition-chain exponentiation.


with Ada.Containers.Ordered_Maps;
with Ada.Numerics.Big_Numbers.Big_Integers;
with Ada.Text_IO;   use Ada.Text_IO;
 
procedure Power_Tree is
 
   Debug_On : constant Boolean := False;
 
   generic
      type Result_Type is private;
      Base     : Result_Type;
      Identity : Result_Type;
      with function "*" (Left, Right : Result_Type) return Result_Type is <>;
   package Knuth_Power_Tree is
      subtype Exponent is Natural;
 
      function Power (Exp : Exponent) return Result_Type;
   end Knuth_Power_Tree;
 
   package body Knuth_Power_Tree is
 
      package Power_Trees is
        new Ada.Containers.Ordered_Maps (Key_Type     => Exponent,
                                         Element_Type => Result_Type);
      Tree : Power_Trees.Map;
 
      procedure Debug (Item : String) is
      begin
         if Debug_On then
            Put_Line (Standard_Error, Item);
         end if;
      end Debug;
 
      function Power (Exp : Exponent) return Result_Type is
         Pow : Result_Type;
      begin
         if Tree.Contains (Exp) then
            return Tree.Element (Exp);
         else
            Debug ("lookup failed of " & Exp'Image);
         end if;
 
         if Exp mod 2 = 0 then
            Debug ("lookup half " & Exponent'(Exp / 2)'Image);
            Pow := Power (Exp / 2);
            Pow := Pow * Pow;
         else
            Debug ("lookup one less " & Exponent'(Exp - 1)'Image);
            Pow := Power (Exp - 1);
            Pow := Result_Type (Base) * Pow;
         end if;
         Debug ("insert " & Exp'Image);
         Tree.Insert (Key => Exp, New_Item => Pow);
         return Pow;
      end Power;
 
   begin
      Tree.Insert (Key => 0, New_Item => Identity);
   end Knuth_Power_Tree;
 
 
   procedure Part_1
   is
      package Power_2 is new Knuth_Power_Tree (Result_Type => Long_Integer,
                                               Base        => 2,
                                               Identity    => 1);
      R : Long_Integer;
   begin
      Put_Line ("=== Part 1 ===");
      for N in 0 .. 25 loop
         R := Power_2.Power (N);
         Put ("2 **");  Put (N'Image);
         Put (" =");    Put (R'Image);
         New_Line;
      end loop;
   end Part_1;
 
   procedure Part_2
   is
      use Ada.Numerics.Big_Numbers.Big_Integers;
 
      package Power_3 is new Knuth_Power_Tree (Result_Type => Big_Integer,
                                               Base        => 3,
                                               Identity    => 1);
      R : Big_Integer;
   begin
      Put_Line ("=== Part 2 ===");
      for E in 190 .. 192 loop
         R := Power_3.Power (E);
         Put ("3 **" & E'Image & " =");  Put (R'Image);  New_Line;
      end loop;
   end Part_2;
 
   procedure Part_3
   is
      subtype Real is Long_Long_Float;
      package Real_IO is new Ada.Text_IO.Float_IO (Real);
      package Power_1_1 is new Knuth_Power_Tree (Result_Type => Real,
                                                 Base        => 1.1,
                                                 Identity    => 1.0);
      R : Real;
   begin
      Put_Line ("=== Part 3 ===");
      for E in 81 .. 84 loop
         R := Power_1_1.Power (E);
         Put ("1.1 **" & E'Image & " = ");
         Real_IO.Put (R, Exp => 0, Aft => 6);
         New_Line;
      end loop;
   end Part_3;
 
begin
   Part_1;
   Part_2;
   Part_3;
end Power_Tree;