[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>
More information about the Squeak-dev
mailing list
|