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

On Fri, Apr 26, 2019 at 4:02 AM tim Rowledge <tim@rowledge.org> wrote:

> On 2019-04-24, at 1:29 PM, Nicolas Cellier <nicolas.cellier.aka.nice@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@rowledge.org; http://www.rowledge.org/tim
Strange OpCodes: ESBD: Erase System and Burn Documentation