[Pharo-users] [Article] Speeding up factorial computation by changing the order of multiplications

Sven Van Caekenberghe sven at stfx.eu
Tue May 24 05:03:57 EDT 2016


> On 24 May 2016, at 10:55, Thierry Goubier <thierry.goubier at gmail.com> wrote:
> 
> Hi Sven.
> 
> Using  '((self + upper) / 2 ) truncated' seems to be a little bit faster than 'self + upper bitshift: -1'.

Is it ?

Even so, you probably agree that that calculation involving the bounds that are not large integers is totally irrelevant in the light of the heavy multiplications of large integers with thousands of digits, no ?

That is why I also said that the recursion cost is (probably) acceptable.

Anyway, if you want to freak out, go read the Fast Factorial Functions website mentioned at the end

 http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

It is totally humbling (for me anyway)

> Thierry
> 
> 
> 
> 2016-05-24 9:57 GMT+02:00 Sven Van Caekenberghe <sven at stfx.eu>:
> I just published a short, introduction level article,
> 
> Speeding up factorial computation by changing the order of multiplications.
> 
> This is a story about a small, seemingly innocent code change that speeds up a very simple computation. It is pretty magical and serves as an example of how things are not always what they seem.
> 
> https://medium.com/concerning-pharo/speeding-up-factorial-computation-by-changing-the-order-of-multiplications-f4da3a5576da#.l3nrk9oax
> 
> Enjoy,
> 
> Sven
> 
> --
> Sven Van Caekenberghe
> Proudly supporting Pharo
> http://pharo.org
> http://association.pharo.org
> http://consortium.pharo.org
> 
> 
> 
> 
> 
> 





More information about the Pharo-users mailing list