[Article] Speeding up factorial computation by changing the order of multiplications
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-cha... Enjoy, Sven -- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
Very nice article Sven ! Can you contribute your code to the PolyMath project under the MIT Licence (and maybe some tests) ? Thank you. On Tue, May 24, 2016 at 8:57 AM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
-- Serge Stinckwich UCBN & UMI UMMISCO 209 (IRD/UPMC) Every DSL ends up being Smalltalk http://www.doesnotunderstand.org/
On 24 May 2016, at 10:21, Serge Stinckwich <serge.stinckwich@gmail.com> wrote:
Very nice article Sven !
Thanks, but it is just intro level (which is important too, of course).
Can you contribute your code to the PolyMath project under the MIT Licence (and maybe some tests) ?
It is only one method. You can copy it over if you want. I am not 100% happy with the selector name #productTo: either. And there should probably be some error checking in a facade method before going into the loop, like self assert: upper isInteger. self assert: (self between: 1 and: upper). Have you seen the Fast Factorial Functions website mentioned at the end ? http://www.luschny.de/math/factorial/FastFactorialFunctions.htm If I see that, I can only be very humble about the implementation in the article (which was based on some very old Lisp code that I had lying around - I did not come up with this myself). Sven
Thank you.
On Tue, May 24, 2016 at 8:57 AM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
-- Serge Stinckwich UCBN & UMI UMMISCO 209 (IRD/UPMC) Every DSL ends up being Smalltalk http://www.doesnotunderstand.org/
Hi Sven. Using '((self + upper) / 2 ) truncated' seems to be a little bit faster than 'self + upper bitshift: -1'. Thierry 2016-05-24 9:57 GMT+02:00 Sven Van Caekenberghe <sven@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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
On 24 May 2016, at 10:55, Thierry Goubier <thierry.goubier@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@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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
2016-05-24 11:03 GMT+02:00 Sven Van Caekenberghe <sven@stfx.eu>:
On 24 May 2016, at 10:55, Thierry Goubier <thierry.goubier@gmail.com> wrote:
Hi Sven.
Using '((self + upper) / 2 ) truncated' seems to be a little bit faster than 'self + upper bitshift: -1'.
Is it ?
Yes, just not by much and it avoids explaining that we use bitshift: there because n << 1 is usually much faster in C with a lousy compiler on a micro-controller.
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 ?
Then there is no reason to use a cryptic optimisation that doesn't optimise anything, 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)
No. High performance versions of numerical/signal/image/video processing codes are so complex usually for performance reasons that such a list is not surprising. The cleverness of some of the solutions are humbling, yes. To be able to make such a difference as you did with a few lines, however, is significant. Because it makes it easily integrated. Thierry
Thierry
2016-05-24 9:57 GMT+02:00 Sven Van Caekenberghe <sven@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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
For the specially interested, there's also this fun thread from some years ago: http://forum.world.st/Challenge-Tuning-the-large-factorial-td3588660.html <http://forum.world.st/Challenge-Tuning-the-large-factorial-td3588660.html> Cheers, Henry
On 24 May 2016, at 9:57 , Sven Van Caekenberghe <sven@stfx.eu> wrote:
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-cha...
Enjoy,
Sven
-- Sven Van Caekenberghe Proudly supporting Pharo http://pharo.org http://association.pharo.org http://consortium.pharo.org
participants (4)
-
Henrik Johansen -
Serge Stinckwich -
Sven Van Caekenberghe -
Thierry Goubier