The problem is to find the nth power of x^n of a number x, where n i s a positive integer. What is the difference between the two pieces of code below. They both produce the same result.
This is the code for the first one:
(define (power x n)
(define (square n) (* n n))
(cond ((= n 1) x)
((even? n)
(square (power x (/ n 2))))
(else
(* (power x (- n 1)) x))))
This is the second one:
(define (power x n)
(if (= n 1)
x
(* x (power (- n 1) x))))
The difference is in the time it takes for the two algorithms to run.
The second one is the simpler, but also less efficient: it requires O(n) multiplications to calculate x^n.
The first one is called the square-and-multiply algorithm. Essentially, it uses the binary representation of the exponent, and uses the identities
x^(ab) = ((x^a)^b)
x^(a+b) = (x^a)(x^b)
to calculate the result. It needs only O(log n) multiplications to calculate the result.
Wikipedia has some detailed analysis of this.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments