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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Sven Van Caekenberghe-2
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





Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

SergeStinckwich
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 <[hidden email]> 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-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
>
>
>
>
>



--
Serge Stinckwich
UCBN & UMI UMMISCO 209 (IRD/UPMC)
Every DSL ends up being Smalltalk
http://www.doesnotunderstand.org/

Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

Thierry Goubier
In reply to this post by Sven Van Caekenberghe-2
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 <[hidden email]>:
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






Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

Sven Van Caekenberghe-2
In reply to this post by SergeStinckwich

> On 24 May 2016, at 10:21, Serge Stinckwich <[hidden email]> 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 <[hidden email]> 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-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
>>
>>
>>
>>
>>
>
>
>
> --
> Serge Stinckwich
> UCBN & UMI UMMISCO 209 (IRD/UPMC)
> Every DSL ends up being Smalltalk
> http://www.doesnotunderstand.org/
>


Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

Sven Van Caekenberghe-2
In reply to this post by Thierry Goubier

> On 24 May 2016, at 10:55, Thierry Goubier <[hidden email]> 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 <[hidden email]>:
> 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
>
>
>
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

Thierry Goubier


2016-05-24 11:03 GMT+02:00 Sven Van Caekenberghe <[hidden email]>:

> On 24 May 2016, at 10:55, Thierry Goubier <[hidden email]> 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 <[hidden email]>:
> 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
>
>
>
>
>
>



Reply | Threaded
Open this post in threaded view
|

Re: [Article] Speeding up factorial computation by changing the order of multiplications

Henrik Sperre Johansen
In reply to this post by Sven Van Caekenberghe-2
For the specially interested, there's also this fun thread from some years ago:

Cheers,
Henry

On 24 May 2016, at 9:57 , Sven Van Caekenberghe <[hidden email]> 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-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







signature.asc (859 bytes) Download Attachment