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

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Knuth's power tree step by step in the Racket 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 Racket programming language

Source code in the racket programming language

#lang racket

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

(define pow-path-level '(1))  

(define (pow-path-extend!)
  (define next-level
    (for*/fold ([next-level '()])
               ([x (in-list pow-path-level)]
                [y (in-list (pow-path x))]
                [s (in-value (+ x y))]
                #:when (not (hash-has-key? pow-path-cache s)))
      (hash-set! pow-path-cache s (append (hash-ref pow-path-cache x) (list s)))
      (cons s next-level)))
  (set! pow-path-level (reverse next-level)))

(define (pow-path n)
  (let loop ()
    (unless (hash-has-key? pow-path-cache n)
      (pow-path-extend!)
      (loop)))
 (hash-ref pow-path-cache n))
 
(define (pow-tree x n)
  (define pows (make-hash `((0 . 1) (1 . ,x))))
  (for/fold ([prev 0])
            ([i (in-list (pow-path n))])
    (hash-set! pows i (* (hash-ref pows (- i prev)) (hash-ref pows prev)))
    i)
  (hash-ref pows n))
 
(define (show-pow x n)
  (printf "~a: ~a\n" n (cdr (pow-path n)))
  (printf "~a^~a = ~a\n" x n (pow-tree x n)))
 
(for ([x (in-range 18)])
  (show-pow 2 x))
(show-pow 3 191)
(show-pow 1.1 81)

You may also check:How to resolve the algorithm Detect division by zero step by step in the Prolog programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the Objective-C programming language
You may also check:How to resolve the algorithm Cholesky decomposition step by step in the Fortran programming language
You may also check:How to resolve the algorithm Babbage problem step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm 4-rings or 4-squares puzzle step by step in the Python programming language