Knuth's power tree: Difference between revisions

 

 

 

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

 

 

 

 

 

::* &nbsp; <big>2ⁿ</big> &nbsp; &nbsp; where &nbsp; n &nbsp; ranges from &nbsp; 0 ──► 17 &nbsp; (inclusive) <br>

 

 

 

 

 

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

<pre>

</pre>

Where, for the power &nbsp; <big>43</big>, &nbsp; following the tree "downwards" from &nbsp; <big>1</big>:

 

<br>

 

 

 

 

 

=={{header|EchoLisp}}==

===Power tree===

We build the tree using '''tree.lib''', adding leaves until the target n is found.

(lib 'tree)

 

(add-level T init-chain: (make-vector 0) target nums)

))

{{out}}

<pre>

</pre>

===Exponentiation===

;; j such as chain[i] = chain[i-1] + chain[j]

(define (adder chain i)

(vector-set! pow i ( * [pow [1- i]] [pow (adder chain i)])))

[pow (1- lg)])

{{out}}

<pre>

(power-exp 3 #( 1 2 3 5 7 14 19 38 57 95 190 191) )

→ 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347

</pre>

 

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=: ]

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

 

(x:1.1) usepath 81

2253240236044012487937308538033349567966729852481170503814810577345406584190098644811r1000000000000000000000000000000000000000000000000000000000000000000000000000000000

 

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.

Thus, for example:

 

 

=={{header|Perl}}==

my %p = (1 => 0);

 

use bigint (try => 'GMP');

show_pow(3, 191);

{{out}}

<pre style="height:32ex;overflow:scroll">

191: (1 2 4 8 16 32 64 128 160 176 184 188 190 191)

3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347

</pre>

 

=={{header|Python}}==

 

# remember the tree generation state and expand on demand

for x in range(18): show_pow(2, x)

show_pow(3, 191)

{{out}}

<pre>

=={{header|Racket}}==

{{trans|Python}}

 

(define pow-path-cache (make-hash '((0 . (0)) (1 . (0 1)))))

(show-pow 2 x))

(show-pow 3 191)

{{out}}

<pre>0: ()

81: (1 2 3 5 10 20 40 41 81)

1.1^81 = 2253.2402360440283</pre>

 

=={{header|REXX}}==

 

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.*/

/*────── X LP HP X LP HP X LP ◄── X, low power, high power ··· repeat*/

do until XP=''

 

/* [↑] W≡length for an aligned display*/

 

 

end /*k*/

call show /*display the expression and its value.*/

end /*e*/

end /*until XP ···*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

powerTree: arg y 1 oy; $= /*Z is the result; $ is the power tree.*/

if y=0 | y=1 then return y /*handle special cases for zero & unity*/

/* [↓] add blank "flag" thingy──►list.*/

end /*while*/

 

end

end /*while s¬==0*/

end /*while n¬==0*/

end /*while @.y==0*/

return space($) /*del extra blanks*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

show: if e<0 then z=format(1/z, , 40)/1; _=right(e, w) /*use reciprocal? */

<pre>

power tree for -4 is: 1 2 4 ═══ 2^-4 is: 0.0625

=={{header|Sidef}}==

{{trans|zkl}}

var p = Hash(1 => 0)

 

for x in ^18 { show_pow(2, x) }

show_pow(1.1, 81)

{{out}}

<pre style="height:32ex;overflow:scroll">

191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191]

3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347

</pre>

 

=={{header|zkl}}==

{{trans|Python}}

fcn path(n,p=Dictionary(1,0),lvl=List(List(1))){

if(n==0) return(T);

 

fcn tree_pow(x,n,path){

foreach i in (path){ r[i]=r[i-p]*r[p]; p=i; }

r[n]

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

{{out}}

<pre style="height:32ex;overflow:scroll">