Le ven. 26 avr. 2019 à 18:10, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> a écrit :

>
>
> 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
>
>
Just ask, it's in the inbox now :)

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/20190427/5f8bccb8/attachment.html>