Knuth's power tree: Difference between revisions

=={{header|Nim}}==

{{trans|Kotlin}}

{{libheader|bignum}}

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

<lang Nim>import tables

import bignum

type

Id = Natural # Node identifier (= exponent value).

Tree = object

parents: Table[Id, Id] # Mapping node id -> parent node id.

lastLevel: seq[Id] # List of node ids in current last level.

func initTree(): Tree =

## Return an initialized tree.

const Root = Id(1)

Tree(parents: {Root: Id(0)}.toTable, lastLevel: @[Root])

func path(tree: var Tree; id: Id): seq[Id] =

## Return the path to node with given id.

if id == 0: return

while id notin tree.parents:

# Node "id" not yet present in the tree: build a new level.

var newLevel: seq[Id]

for x in tree.lastLevel:

for y in tree.path(x):

let newId = x + y

if newId in tree.parents: break # Node already created.

# Create a new node.

tree.parents[newId] = x

newLevel.add newId

tree.lastLevel = move(newLevel)

# Node path is the concatenation of parent node path and node id.

result = tree.path(tree.parents[id]) & id

func treePow[T: SomeNumber | Int](tree: var Tree; x: T; n: Natural): T =

## Compute x^n using the power tree.

let one = when T is Int: newInt(1) else: T(1)

var results = {0: one, 1: x}.toTable # Intermediate and last results.

var k = 0

for i in tree.path(n):

results[i] = results[i - k] * results[k]

k = i

return results[n]

proc showPow[T: SomeNumber | Int](tree: var Tree; x: T; n: Natural) =

echo n, " → ", ($tree.path(n))[1..^1]

let result = tree.treePow(x, n)

echo x, "^", n, " = ", result

when isMainModule:

var tree = initTree()

for n in 0..17: tree.showPow(2, n)

echo ""

tree.showPow(1.1, 81)

echo ""

tree.showPow(newInt(3), 191)</lang>

{{out}}

<pre>0 → []

2^0 = 1

1 → [1]

2^1 = 2

2 → [1, 2]

2^2 = 4

3 → [1, 2, 3]

2^3 = 8

4 → [1, 2, 4]

2^4 = 16

5 → [1, 2, 4, 5]

2^5 = 32

6 → [1, 2, 4, 6]

2^6 = 64

7 → [1, 2, 4, 6, 7]

2^7 = 128

8 → [1, 2, 4, 8]

2^8 = 256

9 → [1, 2, 4, 8, 9]

2^9 = 512

10 → [1, 2, 4, 8, 10]

2^10 = 1024

11 → [1, 2, 4, 8, 10, 11]

2^11 = 2048

12 → [1, 2, 4, 8, 12]

2^12 = 4096

13 → [1, 2, 4, 8, 12, 13]

2^13 = 8192

14 → [1, 2, 4, 8, 12, 14]

2^14 = 16384

15 → [1, 2, 4, 8, 12, 14, 15]

2^15 = 32768

16 → [1, 2, 4, 8, 16]

2^16 = 65536

17 → [1, 2, 4, 8, 16, 17]

2^17 = 131072

81 → [1, 2, 4, 8, 16, 32, 64, 80, 81]

1.1^81 = 2253.240236044025

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

3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347</pre>