Quote:
|
Originally Posted by Klipt
public int factorial(int n)
{
if (n == 1)
return 1;
else
return (factorial(n - 1) * n)%10;
} Which as a side effect may may your code slower since % is supposed to take quite a few cycles. Then try calculate 10 000! (factorial), 100 000!, 1000 000!... until it takes a noticeable time. |
Rough calculations leave this to be about 100 clock cycles / iterations. or about 10000 iterations required for one ms on a 1GHz cpu. (these numbers might be a bit off and i'll spare the disassembly unless someone asks)
Quote:
|
EDIT: of course, since the last digit of n! is 0 for any n >= 5 ... I wonder if multiplication by 0 is any faster? In which case, maybe calculate the last digit of the nth Fibonacci number instead (but don't do it recursively!)
|
It looks like a mulitplication will take no less than 13* clock cycles on this arcitecture. (vs an average of 20 for our estimate) the idiv required for the '%' (43 clock cycles) will help de-weight that effect.
-MBirchmeier
*
http://home.comcast.net/~fbui/intel/i.html#imul