Anonymous user
Addition-chain exponentiation: Difference between revisions
Racket version
m (omissions and categories) |
(Racket version) |
||
Line 468:
0.00000 0.00000 0.00000 0.00000 1.00000 0.00000
</pre>
=={{header|Racket}}==
This produces simple addition chains only.
<lang racket>
#lang racket
(define (chain n)
; computes a simple addition chain for n
(cond [(= n 1) '()]
[(even? n) (define n/2 (/ n 2))
(cons (list n n/2 n/2) (chain n/2))]
[(odd? n) (define n-1 (- n 1))
(cons (list n n-1 1) (chain (- n 1)))]))
(define mult
(let ([n 0])
(λ xs
(cond [(equal? xs (list 'count)) n]
[(equal? xs (list 'reset)) (set! n 0)]
[else (set! n (+ n 1))
(apply * xs)]))))
(define (expt/chain x n chain)
; computes x^n using the addition chain
(define ht (make-hash))
(hash-set! ht 1 x)
(define (expt1 n)
(or (hash-ref ht n #f)
(let ()
(define x^n
(match (assoc n chain)
[(list _ s t) (mult (expt1 s) (expt1 t))]))
(hash-set! ht n x^n)
x^n)))
(expt1 n))
(define (test x n)
(displayln (~a "Chain for " n "\n" (chain n)))
(mult 'reset)
(displayln (~a x " ^ " n " = " (expt/chain x n (chain n))))
(displayln (~a "Multiplications: " (mult 'count)))
(newline))
(test 1.00002206445416 31415)
(test 1.00002550055251 27182)
</lang>
Output:
<lang racket>
Chain for 31415
((31415 31414 1) (31414 15707 15707) (15707 15706 1) (15706 7853 7853) (7853 7852 1) (7852 3926 3926) (3926 1963 1963) (1963 1962 1) (1962 981 981) (981 980 1) (980 490 490) (490 245 245) (245 244 1) (244 122 122) (122 61 61) (61 60 1) (60 30 30) (30 15 15) (15 14 1) (14 7 7) (7 6 1) (6 3 3) (3 2 1) (2 1 1))
1.00002206445416 ^ 31415 = 1.9999999998913485
Multiplications: 24
Chain for 27182
((27182 13591 13591) (13591 13590 1) (13590 6795 6795) (6795 6794 1) (6794 3397 3397) (3397 3396 1) (3396 1698 1698) (1698 849 849) (849 848 1) (848 424 424) (424 212 212) (212 106 106) (106 53 53) (53 52 1) (52 26 26) (26 13 13) (13 12 1) (12 6 6) (6 3 3) (3 2 1) (2 1 1))
1.00002550055251 ^ 27182 = 1.9999999999774538
Multiplications: 21
</lang>
=={{header|Tcl}}==
| |||