Little programming challenge: Factorials

[pcollins]

(define (factorial n)
 (iter 1 1 n))

(define (iter p c c_m)
 (if (> c c_m)
     p
     (iter (* p c)
    (+ 1 c)
    c_m)))

 

Time is O(n), space is O(1)

[Aeternus]

(define (factorial n)
 (iter 1 1 n))

(define (iter p c c_m)
 (if (> c c_m)
     p
     (iter (* p c)
    (+ 1 c)
    c_m)))

 

Time is O(n), space is O(1)

 

The problem you have here is that either you have a finite limit on the n that can be calculated, or if you don't, space isn't O(1) since precision number systems will invariably use more space for large numbers which will mean the space required will increase as n increases (as the result will be a much much larger number which will need more space to store precisely).

 

The same issue occurs with the time complexity, O(n) only holds when you have finite integer types which have constant time operations. When you begin to deal with large values of n and need some form of precision number system, you encounter the problem that larger numbers are harder to calculate with meaning the operations on such numbers aren't O(1) which means the factorial calculation is no longer O(n).

 

Lisp is great though

[shadowacct]

A nice library can be found here: GMP: http://www.gmplib.org

 

Something like 10000! can be done in a fraction of a second on an ordinary PC. I use this library a lot for all kinds of number theory computations. Also things like Miller-Rabin tests for probabilistic primality tests and many other things can be performed with an amazing speed. This library really is the #1 in multiple precision arithmetic. If you want floating point, then use MPFR, which builds on top of GMP. Links can be found on the webpage.