nexpt

Conformance: SketchyLISP Core

Purpose: Raise a natural number to a power. Return x raised to the power of y. Both x and y must be natural numbers.

Arguments:
X - number (base)
Y - number (exponent)

Model:

(define (nexpt x y)
  (cond ((zero? y) 1)
    (else (n* x (nexpt x (n- y 1))))))

Implementation:

(define (nexpt x y)
  (letrec
    ((square
       (lambda (x)
         (n* x x)))
     (_nexpt
       (lambda (y)
         (cond ((zero? y) 1)
           ((even? y)
             (square (nexpt x (nquotient y 2))))
           (else (n* x (square (nexpt x (nquotient y 2)))))))))
    (_nexpt (natural y))))

Example:

(nexpt 3 3) 
=> 27

See also:
digits, expt, gcd.