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
http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec5-Fast-Division-Hasselstrom2003.pdf

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>