I have an access application that has a front-end component which the users use to find the factorials/exponents/products of numbers with large amounts of digits.
I came up with a better algorithm (which turned out to be a known way) for computing factorials than the recursive: factorial
= n * factorial(n-1)
It works like this: find the prime factorization of n! (speedily by noticing that p_i factors into n!, Sum [k=1, infinity] integer((n / (p_i ^ k))) times) (the floor function here is zero once p_i^k > n)
Then compute the n! product by multiplying the powers of all the primes, utilizing the optimization:
a^b = (a*(a^(b-1)) if b is odd), ((a^(b/2))^2 if b is even)
This is fine and dandy and WAY faster than straight recursion. But here's my issue:
I know that memoization isn't nearly as useful for this algorithm as it is for recursion, but obviously it could still have its benefits. What I'm wondering is, what's a good way of measuring the difference in runtime cost between evaluating a factorial this way, and simply recursively computing it based on the highest memoized value that is less than the value being factorialized.
Example 1:
no memoized values in table yet. n = 300. Obviously we then want to compute it with the algorithm above.
Example 2:
300! memoized in table. n = 301. Obviously it's cheaper to compute 301 * memoized value than to compute 301! using the algorithm above.
Example 3:
300! and 301! memoized in table. n = 350. is it faster to compute 350 * 349 * 348 * 347 * ... * 302 * memoized value OR compute 350! straight from the algorithm above
I'm guessing a way to do it is something along the lines of O(n^2) on number of digits of multiplicands between the memoized value and the operand in question when doing it recursively VS. something along the lines of an estimation of the number of prime factors of n!
But really I don't know anything about analyzing the runtime costs of competing algorithms. (other than benchmarks which aren't rigorous enough for my needs)
I came up with a better algorithm (which turned out to be a known way) for computing factorials than the recursive: factorial
= n * factorial(n-1)It works like this: find the prime factorization of n! (speedily by noticing that p_i factors into n!, Sum [k=1, infinity] integer((n / (p_i ^ k))) times) (the floor function here is zero once p_i^k > n)
Then compute the n! product by multiplying the powers of all the primes, utilizing the optimization:
a^b = (a*(a^(b-1)) if b is odd), ((a^(b/2))^2 if b is even)
This is fine and dandy and WAY faster than straight recursion. But here's my issue:
I know that memoization isn't nearly as useful for this algorithm as it is for recursion, but obviously it could still have its benefits. What I'm wondering is, what's a good way of measuring the difference in runtime cost between evaluating a factorial this way, and simply recursively computing it based on the highest memoized value that is less than the value being factorialized.
Example 1:
no memoized values in table yet. n = 300. Obviously we then want to compute it with the algorithm above.
Example 2:
300! memoized in table. n = 301. Obviously it's cheaper to compute 301 * memoized value than to compute 301! using the algorithm above.
Example 3:
300! and 301! memoized in table. n = 350. is it faster to compute 350 * 349 * 348 * 347 * ... * 302 * memoized value OR compute 350! straight from the algorithm above
I'm guessing a way to do it is something along the lines of O(n^2) on number of digits of multiplicands between the memoized value and the operand in question when doing it recursively VS. something along the lines of an estimation of the number of prime factors of n!
But really I don't know anything about analyzing the runtime costs of competing algorithms. (other than benchmarks which aren't rigorous enough for my needs)
Last edited:
