## [squeak-dev] Faster fibonacci

Eliot Miranda eliot.miranda at gmail.com
Tue Jan 28 03:56:26 UTC 2020

Hi Phil,

On Mon, Jan 27, 2020 at 6:07 PM Phil B <pbpublist at gmail.com> wrote:

> That article was an interesting read.  One thing I've always been curious
> about: what applications are people using the arbitrary precision stuff in
> Squeak for?  (I generally make an effort to avoid straying into large
> integers due to the performance implications, but the things I'm working on
> don't require the precision they offer.)
>

One thing I used it for was in implementing 64-bit Spur VM above the 32-bit
Spur implementation.

>
> On Mon, Jan 27, 2020 at 8:28 PM David T. Lewis <lewis at mail.msen.com>
> wrote:
>
>> On Sun, Jan 26, 2020 at 01:59:21PM -0800, tim Rowledge wrote:
>> > Remember the fun with we had calculating 4784969 fibonacci? There's an
>> > interesting article in the Comm.ACM this month about the maybe-final
>> > improvement in huge number multiplication;
>> >
>> https://cacm.acm.org/magazines/2020/1/241707-multiplication-hits-the-speed-limit/fulltext
>> >
>> > tim
>> > --
>> > tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
>> > Strange OpCodes: RIW: Re-Invent Wheel
>> >
>>
>> Very interesting stuff. Probably not ready for a practical implementation
>> in Squeak though. The performance benefits come into play only for very
>> large numbers. The ACM article says:
>>
>>   The n(logn) bound means Harvey and van der Hoeven's algorithm is faster
>>   than Schönhage and Strassen's algorithm, or Fürer's algorithm,
>>   or any other known multiplication algorithm, provided n is sufficiently
>>   large. For now, "sufficiently large" means almost unfathomably large:
>>   Harvey and van der Hoeven's algorithm doesn't even kick in until the
>>   number of bits in the two numbers being multiplied is greater than 2
>>   raised to the 172912 power. (By comparison, the number of particles in
>>   the observable Universe is commonly put at about 2270.)
>>
>> Checking the size of that boundary in Squeak:
>>
>>   (2 raisedTo: 172912) digitLength. ==> 21615
>>   (2 raisedTo: 172912) asFloat. ==> Infinity
>>
>> I don't know nothin' about nothin' but even I know that 'Infinity' is
>> a very big number ;-)
>>
>> But maybe that is missing the point. After all, we actually do a
>> very good job of implementing large integer arithmetic in Squeak.
>> Well OK, it is not exactly "we", Nicolas is the one who did most
>> of it.
>>
>> Indeed, Squeak has no problem at all dealing with a rediculous
>> expression such as this:
>>
>>   (((2 raisedTo: 172912)
>>     cubed cubed cubed + 13 / (2 raisedTo: 172912)
>>     * Float pi asScaledDecimal) asInteger) cubed cubed digitLength.
>>
>>      " ==> 5057678 "
>>
>> That's an integer with about 5 MB of internal representation. So maybe
>> there is one more LargePositiveInteger>>digitMulXXXX method waiting
>> to be created?
>>
>> Dave
>>
>>
>>
>

--
_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20200127/d6385fdd/attachment.html>