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