Knuth's power tree: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
Line 1:
{{task|Knuth's power tree}}
(Knuth's power tree is used for computing <big><big>x<sup>n</sup></big></big> efficiently
Line 11:
Then, using those integers, calculate and show the exact
::* <big>2<sup>n</sup></big> where n ranges from 0 ──► 17 (inclusive) <br>
Line 20:
A ''zero'' power is often handled separately as a special case.
Optionally, support negative
Line 82:
{{trans|Python}}
<
V lvl = [[1]]
Line 116:
show_pow_i(2, x)
show_pow_i(3, 191)
show_pow_f(1.1, 81)</
{{out}}
Line 179:
81: [1, 2, 3, 5, 10, 20, 40, 41, 81]
1.1^81 = 2253.240236
</pre>
=={{header|Ada}}==
In this program the power tree is in a generic package which is instantiated for each base value.
<syntaxhighlight lang="ada">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;</syntaxhighlight>
{{out}}
<pre>
=== Part 1 ===
2 ** 0 = 1
2 ** 1 = 2
2 ** 2 = 4
2 ** 3 = 8
2 ** 4 = 16
2 ** 5 = 32
2 ** 6 = 64
2 ** 7 = 128
2 ** 8 = 256
2 ** 9 = 512
2 ** 10 = 1024
2 ** 11 = 2048
2 ** 12 = 4096
2 ** 13 = 8192
2 ** 14 = 16384
2 ** 15 = 32768
2 ** 16 = 65536
2 ** 17 = 131072
2 ** 18 = 262144
2 ** 19 = 524288
2 ** 20 = 1048576
2 ** 21 = 2097152
2 ** 22 = 4194304
2 ** 23 = 8388608
2 ** 24 = 16777216
2 ** 25 = 33554432
=== Part 2 ===
3 ** 190 = 4498196224760364601242719132174628305800834098010033971355568455673974002968757862019419449
3 ** 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
3 ** 192 = 40483766022843281411184472189571654752207506882090305742200116101065766026718820758174775041
=== Part 3 ===
1.1 ** 81 = 2253.240236
1.1 ** 82 = 2478.564260
1.1 ** 83 = 2726.420686
1.1 ** 84 = 2999.062754
</pre>
Line 184 ⟶ 342:
===Power tree===
We build the tree using '''tree.lib''', adding leaves until the target n is found.
<
(lib 'tree)
Line 225 ⟶ 383:
(add-level T init-chain: (make-vector 0) target nums)
))
</syntaxhighlight>
{{out}}
<pre>
Line 265 ⟶ 423:
</pre>
===Exponentiation===
<
;; j such as chain[i] = chain[i-1] + chain[j]
(define (adder chain i)
Line 277 ⟶ 435:
(vector-set! pow i ( * [pow [1- i]] [pow (adder chain i)])))
[pow (1- lg)])
</syntaxhighlight>
{{out}}
<pre>
Line 294 ⟶ 452:
=={{header|F_Sharp|F#}}==
===Integer Exponentiation===
<
// Integer exponentiation using Knuth power tree. Nigel Galloway: October 29th., 2020
let kT α=let n=Array.zeroCreate<int*int list>((pown 2 (α+1))+1)
Line 310 ⟶ 468:
[0..17]|>List.iter(fun n->printfn "2**%d=%A\n" n (xp 2 n))
printfn "3**191=%A" (xp 3 191)
</syntaxhighlight>
{out}
<pre>
Line 336 ⟶ 494:
===Float Exponentiation===
<
// Float exponentiation using Knuth power tree. Nigel Galloway: October 29th., 2020
let kTf α=let n=Array.zeroCreate<int*int list>((pown 2 (α+1))+1)
Line 352 ⟶ 510:
let xpf=kTf 11
printfn "1.1**81=%f" (xpf 1.1 81)
</syntaxhighlight>
{{out}}
<pre>
Line 359 ⟶ 517:
=={{header|Go}}==
{{trans|Kotlin}}
<
import (
Line 426 ⟶ 584:
showPow(1.1, 81, false)
showPow(3, 191, true)
}</
{{out}}
Line 493 ⟶ 651:
=={{header|Groovy}}==
{{trans|Java}}
<
private static Map<Integer, Integer> p = new HashMap<>()
private static List<List<Integer>> lvl = new ArrayList<>()
Line 554 ⟶ 712:
showPos 3.0, 191, true
}
}</
{{out}}
<pre>0: []
Line 619 ⟶ 777:
{{works with|GHC|8.8.1}}
{{libheader|containers|0.6.2.1}}
<
module Rosetta.PowerTree
Line 676 ⟶ 834:
let b' = b * m Map.! (l - k)
m' = Map.insert l b' m
in go b' l m' ls</
{{out}}
{{libheader|numbers|3000.2.0.2}}
Line 711 ⟶ 869:
We can represent the tree as a list of indices. Each entry in the list gives the value of <code>n</code> for the index <code>a+n</code>. (We can find <code>a</code> using subtraction.)
<
L=: P=: %(1+y){._ 1
findpath=: ]
Line 738 ⟶ 896:
end.
{:exp
)</
Task examples:
<
0 1 1 2 2 3 3 5 4 6 5 10 6 10 7 10 8 16 9 14 10 14 11 13 12 15 13 18 14 28 15 28 16 17 17 21 18 36 19 26 20 40 21 40 22 30 23 42 24 48 25 48 26 52 27 44 28 38 29 31 30 56 31 42 32 64 33 66 34 46 35 57 36 37 37 50 38 76 39 76 40 41 41 43 42 80 43 84 44 47 45 70 46 62 47 57 48 49 49 51 50 100 51 100 52 70 53 104 54 104 55 108 56 112 57 112 58 61 59 112 60 120 61 120 62 75 63 126 64 65 65 129 66 67 67 90 68 136 69 138 70 140 71 140 72 144 73 144 74 132 75 138 76 144 77 79 78 152 79 152 80 160 81 160 82 85 83 162 84 168 85 114 86 168 87 105 88 118 89 176 90 176 91 122 92 184 93 176 94 126 95 190
Line 844 ⟶ 1,002:
(x:1.1) usepath 81
2253240236044012487937308538033349567966729852481170503814810577345406584190098644811r1000000000000000000000000000000000000000000000000000000000000000000000000000000000
</syntaxhighlight>
Note that an 'r' in a number indicates a rational number with the numerator to the left of the r and the denominator to the right of the r. We could instead use decimal notation by indicating how many characters of result we want to see, as well as how many characters to the right of the decimal point we want to see.
Line 850 ⟶ 1,008:
Thus, for example:
<
2253.24023604401248793730853803334956796672985248117050381481057734540658419009864481100</
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.ArrayList;
import java.util.HashMap;
Line 921 ⟶ 1,079:
showPow(3.0, 191, true);
}
}</
{{out}}
<pre>0: []
Line 991 ⟶ 1,149:
(*) Use gojq for infinite-precision integer arithmetic.
<
def kpath($n):
if $n == 0 then .path=[]
Line 1,031 ⟶ 1,189:
(range(0;18) as $n | showPow(2; $n)),
showPow(1.1; 81),
showPow(3; 191)</
{{out}}
Using gojq, the output is the same as for [[#Wren|Wren]].
Line 1,039 ⟶ 1,197:
'''Module''':
<
const p = Dict(1 => 0)
Line 1,070 ⟶ 1,228:
end
end # module KnuthPowerTree</
'''Main''':
<
for n in 0:17
Line 1,081 ⟶ 1,239:
for (x, n) in ((big(3), 191), (1.1, 81))
println("$x ^ $n:\n - path: ", join(path(n), ", "), "\n - result: ", pow(x, n))
end</
{{out}}
Line 1,147 ⟶ 1,305:
=={{header|Kotlin}}==
{{trans|Python}}
<
import java.math.BigDecimal
Line 1,190 ⟶ 1,348:
showPow(1.1, 81, false)
showPow(3.0, 191)
}</
{{out}}
Line 1,256 ⟶ 1,414:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
NextStep[pows_List] := Module[{maxlen, sel, new, vals, knows},
maxlen = Max[Length /@ pows[[All, "Path"]]];
Line 1,307 ⟶ 1,465:
steps = NestWhile[NextStep, pows, Not[MemberQ[#[[All, "P"]], 81]] &];
SelectFirst[steps, #["P"] == 81 &]["Path"];
TreePow[%, 1.1]</
{{out}}
<pre>[Graphics object showing the tree]
Line 1,344 ⟶ 1,502:
This is a translation of the Kotlin/Python program. The algorithm is the same but there are some changes: replacement of global variables by a tree object, use of longer names, replacement of the "lvl" list of lists by a simple list, use of generics to handle the case of big integers...
<
import bignum
Line 1,407 ⟶ 1,565:
tree.showPow(1.1, 81)
echo ""
tree.showPow(newInt(3), 191)</
{{out}}
Line 1,454 ⟶ 1,612:
=={{header|Perl}}==
<
my %p = (1 => 0);
Line 1,497 ⟶ 1,655:
use bigint (try => 'GMP');
show_pow(3, 191);
}</
{{out}}
<pre style="height:32ex;overflow:scroll">
Line 1,545 ⟶ 1,703:
{{trans|Go}}
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}})</span>
Line 1,607 ⟶ 1,765:
<span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.1"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">81</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">191</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre style="font-size: 12px">
Line 1,633 ⟶ 1,791:
=={{header|Python}}==
<
# remember the tree generation state and expand on demand
Line 1,660 ⟶ 1,818:
for x in range(18): show_pow(2, x)
show_pow(3, 191)
show_pow(1.1, 81)</
{{out}}
<pre>
Line 1,686 ⟶ 1,844:
=={{header|Racket}}==
{{trans|Python}}
<
(define pow-path-cache (make-hash '((0 . (0)) (1 . (0 1)))))
Line 1,725 ⟶ 1,883:
(show-pow 2 x))
(show-pow 3 191)
(show-pow 1.1 81)</
{{out}}
<pre>0: ()
Line 1,771 ⟶ 1,929:
(formerly Perl 6)
Paths are random. It is possible replace <code>.pick(*)</code> with <code>.reverse</code> if you want paths as in Perl, or remove it for Python paths.
<syntaxhighlight lang="raku"
sub power-path ($n ) {
Line 1,810 ⟶ 1,968:
say 'Path for 81: ', power-path 81;
say '1.1 ** 81 = ', power 1.1, 81;
</syntaxhighlight>
{{out}}
<pre>
Line 1,825 ⟶ 1,983:
Also, negative powers are supported.
<
numeric digits 1000 /*be able to handle some large numbers.*/
parse arg XP /*get sets: X, low power, high power.*/
Line 1,884 ⟶ 2,042:
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: if e<0 then z=format(1/z, , 40)/1; _=right(e, w) /*use reciprocal? */
say left('power tree for ' _ " is: " $,60) '═══' x"^"_ ' is: ' z; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,915 ⟶ 2,073:
=={{header|Sidef}}==
{{trans|zkl}}
<
var p = Hash(1 => 0)
Line 1,952 ⟶ 2,110:
for x in ^18 { show_pow(2, x) }
show_pow(1.1, 81)
show_pow(3, 191)</
{{out}}
<pre style="height:32ex;overflow:scroll">
Line 2,001 ⟶ 2,159:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var p = { 1: 0 }
Line 2,045 ⟶ 2,203:
for (n in 0..17) showPow.call(2, n)
showPow.call(1.1, 81)
showPow.call(3, 191)</
{{out}}
Line 2,109 ⟶ 2,267:
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
</pre>
=={{header|zkl}}==
{{trans|Python}}
<
fcn path(n,p=Dictionary(1,0),lvl=List(List(1))){
if(n==0) return(T);
Line 2,137 ⟶ 2,294:
fmt:="%d: %s\n" + T("%g^%d = %f", "%d^%d = %d")[x==Int(x)] + "\n";
println(fmt.fmt(n,p:=path(n),x,n,tree_pow(x,n,p)))
}</
<
show_pow(1.1,81);
var [const] BN=Import("zklBigNum"); // GNU GMP big ints
show_pow(BN(3),191);</
{{out}}
<pre style="height:32ex;overflow:scroll">
| |||