Knuth's power tree: Difference between revisions

{{trans|Python}}

 

V lvl = [[1]]

 

show_pow_i(2, x)

show_pow_i(3, 191)

 

{{out}}

=={{header|Ada}}==

In this program the power tree is in a generic package which is instantiated for each base value.

with Ada.Numerics.Big_Numbers.Big_Integers;

with Ada.Text_IO; use Ada.Text_IO;

Part_2;

Part_3;

{{out}}

<pre>

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

=={{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)

[0..17]|>List.iter(fun n->printfn "2**%d=%A\n" n (xp 2 n))

printfn "3**191=%A" (xp 3 191)

{out}

<pre>

 

===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)

let xpf=kTf 11

printfn "1.1**81=%f" (xpf 1.1 81)

{{out}}

<pre>

=={{header|Go}}==

{{trans|Kotlin}}

 

import (

showPow(1.1, 81, false)

showPow(3, 191, true)

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

private static Map<Integer, Integer> p = new HashMap<>()

private static List<List<Integer>> lvl = new ArrayList<>()

showPos 3.0, 191, true

}

{{out}}

<pre>0: []

{{works with|GHC|8.8.1}}

{{libheader|containers|0.6.2.1}}

 

module Rosetta.PowerTree

let b' = b * m Map.! (l - k)

m' = Map.insert l b' m

{{out}}

{{libheader|numbers|3000.2.0.2}}

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|Java}}==

{{trans|Kotlin}}

import java.util.ArrayList;

import java.util.HashMap;

showPow(3.0, 191, true);

}

{{out}}

<pre>0: []

 

(*) Use gojq for infinite-precision integer arithmetic.

def kpath($n):

if $n == 0 then .path=[]

(range(0;18) as $n | showPow(2; $n)),

showPow(1.1; 81),

{{out}}

Using gojq, the output is the same as for [[#Wren|Wren]].

 

'''Module''':

 

const p = Dict(1 => 0)

end

 

 

'''Main''':

 

for n in 0:17

for (x, n) in ((big(3), 191), (1.1, 81))

println("$x ^ $n:\n - path: ", join(path(n), ", "), "\n - result: ", pow(x, n))

 

{{out}}

=={{header|Kotlin}}==

{{trans|Python}}

 

import java.math.BigDecimal

showPow(1.1, 81, false)

showPow(3.0, 191)

 

{{out}}

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

NextStep[pows_List] := Module[{maxlen, sel, new, vals, knows},

maxlen = Max[Length /@ pows[[All, "Path"]]];

steps = NestWhile[NextStep, pows, Not[MemberQ[#[[All, "P"]], 81]] &];

SelectFirst[steps, #["P"] == 81 &]["Path"];

{{out}}

<pre>[Graphics object showing the tree]

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

 

tree.showPow(1.1, 81)

echo ""

 

{{out}}

 

=={{header|Perl}}==

my %p = (1 => 0);

 

use bigint (try => 'GMP');

show_pow(3, 191);

{{out}}

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

{{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>

<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">

 

=={{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: ()

(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.

 

sub power-path ($n ) {

say 'Path for 81: ', power-path 81;

say '1.1 ** 81 = ', power 1.1, 81;

{{out}}

<pre>

 

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

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

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

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{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">

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

 

for (n in 0..17) showPow.call(2, n)

showPow.call(1.1, 81)

 

{{out}}

=={{header|zkl}}==

{{trans|Python}}

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

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

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">