[squeak-dev] Faster fibonacci

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Fri Apr 26 16:10:27 UTC 2019

Le ven. 26 avr. 2019 à 13:55, Fabio Niephaus <lists at fniephaus.com> a écrit :

> On Fri, Apr 26, 2019 at 4:02 AM tim Rowledge <tim at rowledge.org> wrote:
>> > On 2019-04-24, at 1:29 PM, Nicolas Cellier <
>> nicolas.cellier.aka.nice at gmail.com> wrote:
>> >
>> > Hi Tim,
>> > I've posted some enhancements with a  3-way Toom-Cook multiplication
>> algorithm
>> > (it is a generalization of karatsuba, but we divide in n parts instead
>> of 2, here 3 parts for Toom-3)
>> Wow. That's nearly twice as fast for the  fib(4784969) - 8.4 sec.
>> Amazing. So about 10x over the original.
>> Now *printing* the number is rather slower and if you have any magic code
>> to improve that it would be interesting.
>> I would *strongly* support putting the algorithm improvements into trunk.
>> Very little code for colossal speedup and a really interesting exemplar of
>> advanced algorithms.
> +1
changes are in inbox now
they should have associated tests

For the printing, cost is dominated by division.
division cost is dominated by multiplication.
We could opt for a divide and conquer algorithm too, or mixed
Barett-Newton-Raphson which is the most efficient known algorithm
See for example

Another interesting POV is that most of these divide and conquer lead to
easy parallelisation...
If we could spawn image clones above a certain level, and communicate the
results via sockets.
The printing though would require to share the target String memory, or we
could end in a O(n*log(n)) reconstruction cost to gather the pieces.

>> tim
>> --
>> tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
>> Strange OpCodes: ESBD: Erase System and Burn Documentation
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20190426/5f35d345/attachment.html>

More information about the Squeak-dev mailing list