[squeakdev] 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 20190424, at 1:29 PM, Nicolas Cellier <
>> nicolas.cellier.aka.nice at gmail.com> wrote:
>> >
>> > Hi Tim,
>> > I've posted some enhancements with a 3way ToomCook multiplication
>> algorithm
>> > (it is a generalization of karatsuba, but we divide in n parts instead
>> of 2, here 3 parts for Toom3)
>>
>> 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
BarettNewtonRaphson which is the most efficient known algorithm
See for example
http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec5FastDivisionHasselstrom2003.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/squeakdev/attachments/20190426/5f35d345/attachment.html>
More information about the Squeakdev
mailing list
