On Sun, 28 Apr 2019 at 3:35 pm, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> wrote:

>
>
> Le sam. 27 avr. 2019 à 22:49, Nicolas Cellier <
> nicolas.cellier.aka.nice at gmail.com> a écrit :
>
>>
>>
>> Le sam. 27 avr. 2019 à 20:26, tim Rowledge <tim at rowledge.org> a écrit :
>>
>>>
>>>
>>> > On 2019-04-27, at 1:43 AM, Nicolas Cellier <
>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>> >
>>> >
>>> >
>>> >
>>> > Just ask, it's in the inbox now :)
>>>
>>> Good grief. That's some interesting code.
>>>
>>> BUT - it isn't in the inbox so far as I can see; the newest Kernel mcz
>>> is http://source.squeak.org/inbox/Kernel-nice.1216.mcz ... oh, wait, I
>>> see you've put an even newer version in trunk. Phew, I thought you might
>>> have been suffering from uploading problems like my NuScratch stuff.
>>>
>>> I merged (because I had my fastfib method already) your Kernel-nice.1220
>>> and tried out [4784969 fastDoublingFib asString ] timeToRun . It crashed
>>> because of no Interval>>digitShiftSum: method, which needs to go into
>>> Collections I guess.
>>>
>>> Oups! It's in Collection, I forgot to commit it!
>>
>> Previously
>>> [4784969 fastDoublingFib asString ] timeToRun -> 136833mS (on my Pi3+)
>>> Now
>>> [4784969 fastDoublingFib asString ] timeToRun  -> 21060mS
>>> Call 6.5X faster.
>>>
>>> Assuming we are all confident about the correctness I'd urge making that
>>> the default multiply for large ints. Unless somebody is going to improve
>>> the plugin to assist in making this even faster?
>>>
>>> tim
>>>
>>
>> The problem is that fastMultiply: just put overhead for every moderately
>> LargeIntegers, which is the most common case, so I hesitate to do it the
>> default.
>>
>> Implementing divide and conquer in the primitives is also not a pleasant
>> path: divide and conquer often trade speed for space, so it means that we
>> must massively allocate new objects in primitives which is a difficult
>> task. Or resuse some preallocated memory, which gives a horrible taste to
>> these beautiful and simple algorithms. Also it hides those algorithms from
>> our view, make debugging not a pleasure, and make improvment a less
>> enjoyable hobby.
>>
>> What we could do instead, is to make some primitive fail when digitLength
>> is above a certain threshold.
>> That threshold would be a parameter controlled from the image, and a
>> default value of 0 at VM startup could mean no primitive failure making the
>> VM friendly to those image not Karatsuba aware...
>>
>>
> Hmm, after thoughts and experiments, I retract what I said.
> The overhead cost in Squeak is very marginal at least in 64bits VM, so we
> can make #fastMultiply: the default.
> Last time I tried was in VW, where the arrangement of primitives is a bit
> different.
>

Java's BigInteger applies different multiplication algorithms depending on
the values to multiply:
https://github.com/openjdk/jdk/blob/4ebb1e2702e7d22f86eacef3b4a5204df70416ab/src/java.base/share/classes/java/math/BigInteger.java#L1578

Maybe we could do something similar?

Fabio


> Seuls les imbéciles ne changent pas d'avis ;)
>
> --
>>> tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
>>> Useful random insult:- Talks to plants on their own level.
>>>
>>>
>>>
>>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20190428/176f7725/attachment.html>