Tuesday, April 10, 2007

Scheme and Factorials

I am currently working of Scheme. I decided to try out few programs on factorial and factorial like products.

If you have a mathematical definition, you can easily write its Scheme equivalent procedure (I cannot prove this statement).

--------------------------------------

(define (factorial n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (* (factorial (- n 1)) n))
)
)

---------------------------------------

Multifactorial

(define (multifactorial n k)
(cond ((and (<= 0 n) (< k =" 2)"> n 0)) n)
((= n 0) 1)
(else (* (multiplelevelfactorial (- n 1) m) (multiplelevelfactorial n (- m 1))))
)
)

To test:
Superfactorial (k = 2) of 4 is 288
Superduperfactorial (k = 3) of 4 is 6912

---------------------------------------

(define (power a b)
(cond ((= b 1) a)
(else (* a (power a (- b 1))))
)
)

(define (hyperfactorial n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (* (power n n) (hyperfactorial (- n 1))))
)
)

To test:
Hyperfactorial of 4 is 27648

---------------------------------------

All above procedures are recursive.

Linear iteration for calculating factorial would result into faster results.

(define (factorial n)
(fact-iter 1 1 n)
)

(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product) (+ counter 1) max-count)
)
)

If n is very large number and you can use Stirling's approximation to get much faster results.