How to resolve the algorithm Knuth's power tree step by step in the F# programming language

Published on 12 May 2024 09:40 PM
#F_Sharp

How to resolve the algorithm Knuth's power tree step by step in the F# programming language

Table of Contents

Problem Statement

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

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

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

A  zero  power is often handled separately as a special case. Optionally, support negative integer powers.

An example of a small power tree for some low integers: Where, for the power   43,   following the tree "downwards" from   1: 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:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knuth's power tree step by step in the F# programming language

Source code in the fsharp programming language

// Integer exponentiation using Knuth power tree. Nigel Galloway: October 29th., 2020
let kT α=let n=Array.zeroCreate<int*int list>((pown 2 (α+1))+1)
         let fN g=let rec fN p=[yield g+p; if p>0 then let g,_=n.[p] in yield! fN g] in (g+g)::(fN (fst n.[g]))|>List.rev
         let fG g=[for α,β in g do for g in β do let p,_=n.[g] in n.[g]<-(p,fN g|>List.filter(fun β->if box n.[β]=null then n.[β]<-(g,[]); true else false)); yield n.[g]]
         let rec kT n g=match g with 0->() |_->let n=fG n in kT n (g-1)
         let fE X g=let α=let rec fE g=[|yield g; if g>1 then yield! fE (fst n.[g])|] in fE g
                    let β=Array.zeroCreate<bigint>α.Length
                    let l=β.Length-1
                    β.[l]<-bigint (X+0)
                    for e in l-1.. -1..0 do β.[e]<-match α.[e]%2 with 0->β.[e+1]*β.[e+1] |_->let l=α.[e+1] in β.[e+1]*β.[α|>Array.findIndex(fun n->l+n=α.[e])]
                    β.[0]
         n.[1]<-(0,[2]); n.[2]<-(1,[]); kT [n.[1]] α; (fun n g->if g=0 then 1I else fE n g) 
let xp=kT 11         
[0..17]|>List.iter(fun n->printfn "2**%d=%A\n" n (xp 2 n))
printfn "3**191=%A" (xp 3 191)


// 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 fN g=let rec fN p=[yield g+p; if p>0 then let g,_=n.[p] in yield! fN g] in (g+g)::(fN (fst n.[g]))|>List.rev
          let fG g=[for α,β in g do for g in β do let p,_=n.[g] in n.[g]<-(p,fN g|>List.filter(fun β->if box n.[β]=null then n.[β]<-(g,[]); true else false)); yield n.[g]]
          let rec kT n g=match g with 0->() |_->let n=fG n in kT n (g-1)
          let fE X g=let α=let rec fE g=[|yield g; if g>1 then yield! fE (fst n.[g])|] in fE g
                     let β=Array.zeroCreate<float>α.Length
                     let l=β.Length-1
                     β.[l]<-X
                     for e in l-1.. -1..0 do β.[e]<-match α.[e]%2 with 0->β.[e+1]*β.[e+1] |_->let l=α.[e+1] in β.[e+1]*β.[α|>Array.findIndex(fun n->l+n=α.[e])]
                     β.[0]
          n.[1]<-(0,[2]); n.[2]<-(1,[]); kT [n.[1]] α; (fun n g->if g=0 then 1.0 else fE n g) 

let xpf=kTf 11
printfn "1.1**81=%f" (xpf 1.1 81)

You may also check:How to resolve the algorithm Weird numbers step by step in the Wren programming language
You may also check:How to resolve the algorithm Attractive numbers step by step in the Arturo programming language
You may also check:How to resolve the algorithm Determine if a string has all the same characters step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Strip comments from a string step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Check output device is a terminal step by step in the Wren programming language