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

Thierry Goubier thierry.goubier at gmail.com
Tue May 24 07:45:04 EDT 2016


2016-05-24 11:03 GMT+02:00 Sven Van Caekenberghe <sven at stfx.eu>:

>
> > 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 ?
>

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 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
> >
> >
> >
> >
> >
> >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-users_lists.pharo.org/attachments/20160524/a05e9791/attachment.html>


More information about the Pharo-users mailing list