(define (f x) (if (< x 1) 1 (* (+ x 1) (f (- x 1))) ) )
(define (f x y z) (cond ((= x 1) (* y z)) ((= (% x 2) 0) (f (/ x 2) (* y 2) z)) (else (f (- x 1) y (+ z x))) ) )
(define (f x y z) (cond ((= x 0) (* y z)) ((< x 5) (f y z (+ x 7)) ((< x 10) (+ y (* 2 z) (f (- x 1) y z))) (else x) ) )
(define (f n a b) (cond ((= b (+ a 1)) 'ok) ((= b (+ a 2)) (swap n a (+ a 1))) (else (f n a (integer (* (+ a b) 0.666))) (f n (integer (* (+ a b) 0.333) b)) (f n a (integer (* (+ a b) 0.666))) ) ) )
(define (f n z) (cond ((= n 0) z) ((< n 3) (* z (f (- n 1) (+ z 1)))) (else (f (- n 1) (* n z))) ) )
(define (f n z) (cond ((= n 0) z) ((< n 3) (f (- n 1) (* z n))) (else (* z (f (- n 1) (+ z 1)))) ) )
(define (f z) (if (< z 2) z (+ (f (- z 2)) (- z 1)) ) )
(define (f z) (define (iter a b count) (if (= count 0) b (iter (f (- count 1)) (f (- count 2)) (- count 1)) ) ) (iter 0 0 z) )
(define (f z) (define (iter a b count) (if (= count 0) a (iter b (+ a b) (- count 1)) ) ) (iter 0 1 z) )
(define (f z) (cond ((< z 2) 1) (else (* z (f (- z 1))) (f 1)) ) )
(define (f x) (if (< x 2) x (+ (f (- x 1)) (f (- x 2))) ) )
(define (f x) (if (< x 2) x (+ (f (- x 1)) (f (- x 2))) ) )
e(b,n) = b * e(b,n-1) if n > 0 e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = b * e(b,n-1) if n > 0 e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b*b,n/2) if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b*b,n/2) if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b*b,n/2) if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b,n/2)^2 if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b,n/2)^2 if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b,n/2) * e(b,n/2) if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = e(b,n/2) * e(b,n/2) if n is positive,even e(b,n) = b * e(b,n-1) if n is positive,odd e(b,n) = 1 otherwiseif implemented directly, takes:
e(b,n) = f(b,n,1) f(b,n,t) = f(b*b,n/2,t) if n is positive,even f(b,n,t) = f(b,n-1,t*b) if n is positive,odd f(b,n,t) = t otherwiseif implemented directly, takes:
e(b,n) = f(b,n,1) f(b,n,t) = f(b*b,n/2,t) if n is positive,even f(b,n,t) = f(b,n-1,t*b) if n is positive,odd f(b,n,t) = t otherwiseif implemented directly, takes:
gcd(a,b) = a if b is zero gcd(a,b) = gcd(b,a%b) otherwisewas first attributed to:
gcd(m,n)
?
Assume m is larger than n and that
gcd(m,n)
takes k steps.
gcd(a,b) = a if b is zero gcd(a,b) = gcd(b,a%b) otherwiseif implemented directly, takes:
gcd(a,b) = a if b is zero gcd(a,b) = gcd(b,a%b) otherwiseThe number of remainder operations performed by
gcd(412,60)
using applicative order evaluation is:
gcd(a,b) = a if b is zero gcd(a,b) = gcd(b,a%b) otherwiseAssuming a knowledge of when to stop, what is the number of remainder operations performed by
gcd(412,60)
using normal order evaluation?
There are four recursive calls which involve
remainder operations.
gcd(a,b)
is
gcd(b,a%b)
is the first of these.
(define (expmod base exp m) (% (fast-expt base exp) m))
(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (% (square (expmod base (/ exp 2) m)) m)) (else (% (* base (expmod base (- exp 1) m)) m))))What is the recurrence that describes the even case?
(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (% (square (expmod base (/ exp 2) m)) m)) (else (% (* base (expmod base (- exp 1) m)) m))))What is the recurrence that describes the default case?
(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (% (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) m)) (else (% (* base (expmod base (- exp 1) m)) m))))What is the recurrence that describes the even case?