## Ancient Algorithms

### December 23, 2014

(define (product left right) (let loop ((left left) (right right) (prod 0)) (if (zero? left) prod (loop (quotient left 2) (* right 2) (if (odd? left) (+ prod right) prod)))))

(define (hero n) (cond ((< n 1) (/ (hero (* n 4)) 2)) ((<= 4 n) (* (hero (/ n 4)) 2)) (else (let* ((x (/ (+ n 1.0) 2)) (x (/ (+ x (/ n x)) 2)) (x (/ (+ x (/ n x)) 2)) (x (/ (+ x (/ n x)) 2)) (x (/ (+ x (/ n x)) 2)) (x (/ (+ x (/ n x)) 2))) x))))

(define (triple m n) (values (- (* m m) (* n n)) (* 2 m n) (+ (* m m) (* n n))))

(define (ancient m n) (cond ((< m n) (ancient m (- n m))) ((< n m) (ancient (- m n) n)) (else m)))

(define (modern m n) (if (zero? n) m (modern n (modulo m n))))

(define (pi n) (let ((outer (* 3 (sqrt 3)))) (let loop ((n n) (outer outer) (inner (/ outer 2))) (if (= n 1) (values inner outer) (let ((outer (/ 2 (+ (/ outer) (/ inner))))) (loop (- n 1) outer (sqrt (* outer inner))))))))

(define (primes n) (let ((sieve (make-vector (+ n 1) #t))) (do ((p 2 (+ p 1))) ((< n p) (newline)) (when (vector-ref sieve p) (display p) (display " ") (do ((i (* p p) (+ i p))) ((< n i)) (vector-set! sieve i #f))))))

You can run the program at http://programmingpraxis.codepad.org/uMpTzHIU.

The output of this program is:

Just noticed that gcdA and gcdM are mistakenly calling the system gcd function. They should be:

Just so everybody’s clear, 2^2 – 1^2 = 3

[…] Ancient Algorithms […]

[…] One writer saw Johnny Ball’s video about Russian Multiplication on Numberphile and suggested it would make a good exercise. Indeed it would; in fact, we have already done it twice ([1] [2]). […]