in reply to Re^6: Factorial algorithm execution time
in thread Factorial algorithm execution time

There is a measurable, if minor improvement. Which is about what your algorithm offers over mine.

The reason that it is so small is that the connection between size and improvement is not that strong. You only save when you manage to reduce how many "digits" are involved, and at least with Perl 5.6's implementation of Math::BigInt, digits are of size 1e5. Making sure that only a few multiplications have huge numbers is most of what you can save. Multiplying big numbers is a bottleneck. You cannot avoid the bottleneck much more. Next you should speed it up.

If you want to try a pure Perl solution, I suggest implementing Karatsuba multiplication. It isn't nearly as fast as Fourier transforms, but it is easier to understand and implement.

  • Comment on Re: Re^6: Factorial algorithm execution time