Faster fibonacci

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
36 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

fniephaus


On Sun, 28 Apr 2019 at 3:35 pm, Nicolas Cellier <[hidden email]> wrote:


Le sam. 27 avr. 2019 à 22:49, Nicolas Cellier <[hidden email]> a écrit :


Le sam. 27 avr. 2019 à 20:26, tim Rowledge <[hidden email]> a écrit :


> On 2019-04-27, at 1:43 AM, Nicolas Cellier <[hidden email]> 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:
Maybe we could do something similar?

Fabio


Seuls les imbéciles ne changent pas d'avis ;)

--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- Talks to plants on their own level.






Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

marcel.taeumel
In reply to this post by timrowledge
Hi Tim,

command-line scripts are executed *after* all other start-up calls were made using a deferred UI message. There is no need to fiddle around with the order in the start-up list. See:

SmalltalkImage >> #processStartUpList:
AutoStart class >> #startUp: (last line)
ProjectLauncher >> #startUp
ProjectLauncher >> #startUpAfterLogin

Best,
Marcel

Am 26.04.2019 22:03:54 schrieb tim Rowledge <[hidden email]>:



> On 2019-04-25, at 7:40 PM, tim Rowledge wrote:
>
>
> Looking at FileStream class initialise I see
> Smalltalk
> addToStartUpList: self after: SecurityManager; "the intent being before: AutoStart"
> and yet inspecting the startuplist shows that FileStream comes well *after* AutoStart (which in a somewhat convoluted way actually makes ProjectLauncher actually do the startup document reading) and so we got things messed up sometime.

It seems all we need is to run
FileStream initialise
to fix this, at least in a current image.

I'd guess that making sure the order of things in the startup list is correct is something the ReleaseManager ought to be able to do. I would have guessed that it might use SmalltalkImage class>>#initializeStartUpList but can't see a connection in the code right now.

Mind you, that method has a fairly big bug in that it ignores the ordering desires of all the classes involved, which may explain the original problem. We can't simplistically run through the list of classes currently in the startup list and send #initialize to them since any number of them might do much more stuff in those methods, including stuff that could be destructive. We would need to separate out the startup list related code and only run that.

So conceptually,
a) in all senders of #addToStartUpList* and related methods, split out the startup list part to an agreed method such as #addToStartUpSequence that handles the ordering requirements, if any. A default nul version inObject would be nice.
b) to rebuild the startup list, take copy of the current list and send each item #addToStartUpSequence
c) some classes may need to be checked out for where they need to be in the ordering - I see thsat ProcessorScheduler is mentioned particularly in SmalltalkImage class>>#initializeStartUpList and yet its #initialize makes no reference to #addToStartUpList*
d) use the rebuilt method from ReleaseBuilder

Ideas?

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- Lights are on but nobody's home.





Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

timrowledge
Hi marcel -

> On 2019-04-28, at 11:40 PM, Marcel Taeumel <[hidden email]> wrote:
> command-line scripts are executed *after* all other start-up calls were made using a deferred UI message. There is no need to fiddle around with the order in the start-up list. See:
>
> SmalltalkImage >> #processStartUpList:
> AutoStart class >> #startUp: (last line)
> ProjectLauncher >> #startUp
> ProjectLauncher >> #startUpAfterLogin

I see that; but then we have to work out why the stdin/out/err filehandles need (re)initialising.  FileStream class>>startUp: (true) is supposed to do it as part of the normal startup sequence but I had to add it at the beginning of my doit-file. Not to mention why does it seem to not work at all on Windows? And also, there is still the point that things are not in the requested/required order in the StartUp list.

As an extra excitement, how shall we allow for having startup files that want to avoid the UI starting up - say to support the idea of using Squeak for quick jobs as part of scripting? I'm not at all sure what a good answer would be here, it seems at first thought that we'd need either have two ways to specify the files in the commandline (say, -earlyfilein & -uifilein, which are both horrible and should not be used!) or to have some tags in the files to say where sections get evaluated - perhaps [preUI] & [postUI].


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- Fell out of the family tree.



Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

keithy
In reply to this post by timrowledge

Years ago I was trying to rationalise all the various functionality of Smalltalk/SmalltalkImage across
forks. I also wanted to support a scheme that would handle being bootstrapped from sources.

i.e. the startup process may load in or unload a number of classes from sources at an early stage, and when the time came to think about #startUp they may not have been #initialised, (the #startUp might be their initialisation).

So I vaguely recollect that when I had a go at re-doing the startuplist I removed this responsibility to a class of its own, called StartupManager, and removed the class var that holds the list in favour of a voting system.

I found some code hiding away (somewhat obfuscated)

https://bazaar.launchpad.net/~keithy/cuis/System-Support_StartupManager/revision/1#StartupManager-into-Cuis2/1-System-Support-StartupManager.install/0002/StartupManager-(startup-shutdown)-int.1.st

Looking through the comments I find

StatupManager

New simple startUp shutDown protocol

classes implement #startUpPriority #shutDownPriority to register.
Note: this code could be hosted on a different class, such as SmalltalkImage,

The startUp and shutdownLists are compiled by looking at all implementors of:'

startUpPriority and #shutDownPriority'

Priorities are: #first #earliest #earlier #early #normal #late #later #latest #last'

As you can imagine this was very much a first attempt at resolving these problems.

Keith



Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

keithy

On 30 Apr 2019, at 0:15, Keith wrote:

Years ago I was trying to rationalise all the various functionality of Smalltalk/SmalltalkImage across
forks. I also wanted to support a scheme that would handle being bootstrapped from sources.

i.e. the startup process may load in or unload a number of classes from sources at an early stage, and when the time came to think about #startUp they may not have been #initialised, (the #startUp might be their initialisation).

So I vaguely recollect that when I had a go at re-doing the startuplist I removed this responsibility to a class of its own, called StartupManager, and removed the class var that holds the list in favour of a voting system.

I found some code hiding away (somewhat obfuscated)

https://bazaar.launchpad.net/~keithy/cuis/System-Support_StartupManager/revision/1#StartupManager-into-Cuis2/1-System-Support-StartupManager.install/0002/StartupManager-(startup-shutdown)-int.1.st

Looking through the comments I find

StatupManager

New simple startUp shutDown protocol

classes implement #startUpPriority #shutDownPriority to register.
Note: this code could be hosted on a different class, such as SmalltalkImage,

The startUp and shutdownLists are compiled by looking at all implementors of:'
#startUpPriority and #shutDownPriority'
Priorities are: #first #earliest #earlier #early #normal #late #later #latest #last'

As you can imagine this was very much a first attempt at resolving these problems.

Keith

One of the other goals was to support removable/loadable UI in the bootstrap process

I found this code in there, which indicates that the vote was essentially on a numeric 0-999 scale.

StartupManager class methodsFor: 'system-startup-shutdown' stamp: 'kph 2/4/2010 16:44'!"

priorities

^ IdentityDictionary new

at: #first put: 0; "reserved for Delay"
at: #earliest put: 10;
at: #earlier put: 100;
at: #early put: 200;
at: #normal put: 500;
at: #late put: 800;
at: #later put: 900;
at: #latest put: 990;
at: #last put: 999; "reserved for Delay"
yourself.

and some code, sorting on given priority value, followed by class name.

startUpList

| priorities list |

priorities := self class priorities.
list := SortedCollection sortBlock: [ :a :b |
a value = b value
ifFalse: [ a value <= b value]
ifTrue: [ a key name <= b key name ] ].'

self systemNavigation allClassesRespondingTo: #startUpPriority
do: [ :cl | list add: (cl -> (priorities at: cl startUpPriority ifAbsent: [ cl startUpPriority ] )) ].

^ list



Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

keithy
In reply to this post by timrowledge


On 29 Apr 2019, at 23:14, tim Rowledge wrote:

Hi marcel -

On 2019-04-28, at 11:40 PM, Marcel Taeumel <[hidden email]> wrote:
command-line scripts are executed *after* all other start-up calls were made using a deferred UI message. There is no need to fiddle around with the order in the start-up list. See:

SmalltalkImage >> #processStartUpList:
AutoStart class >> #startUp: (last line)
ProjectLauncher >> #startUp
ProjectLauncher >> #startUpAfterLogin

I see that; but then we have to work out why the stdin/out/err filehandles need (re)initialising. FileStream class>>startUp: (true) is supposed to do it as part of the normal startup sequence but I had to add it at the beginning of my doit-file. Not to mention why does it seem to not work at all on Windows? And also, there is still the point that things are not in the requested/required order in the StartUp list.

As an extra excitement, how shall we allow for having startup files that want to avoid the UI starting up - say to support the idea of using Squeak for quick jobs as part of scripting? I'm not at all sure what a good answer would be here, it seems at first thought that we'd need either have two ways to specify the files in the commandline (say, -earlyfilein & -uifilein, which are both horrible and should not be used!) or to have some tags in the files to say where sections get evaluated - perhaps [preUI] & [postUI].

This was the functionality of my InstallSeries code.

The idea was to aim to load a project as a series of file ins, from a hierarchy of directories whose structure would indicate the priority, such as #preUI, "I am the UI" and #postUI.

The file out scheme, would create InstallSeries compatible changesets according to specific slice definitions, such as "methods in the image categorised as (startup-shutdown)." Thus a slice definition could be applied to more than one image or fork, for import or export.

The aim was to patch each fork (pharo squeak cuis et al) at an early stage in the bootstrap so that subsequent slices of functionality could be held in common. I think I got as far as loading Seaside in Cuis.

Keith



Reply | Threaded
Open this post in threaded view
|

Re: Lessons learned from (Re: Faster fibonacci)

marcel.taeumel
In reply to this post by timrowledge
Hi Tim,

a "GUI" that would represent a "headless" Squeak (instead of Morphic) could (or should?) also support a main loop with deferred messages. See SqueakShell. :-)

Best,
Marcel

Am 30.04.2019 00:15:05 schrieb tim Rowledge <[hidden email]>:

Hi marcel -

> On 2019-04-28, at 11:40 PM, Marcel Taeumel wrote:
> command-line scripts are executed *after* all other start-up calls were made using a deferred UI message. There is no need to fiddle around with the order in the start-up list. See:
>
> SmalltalkImage >> #processStartUpList:
> AutoStart class >> #startUp: (last line)
> ProjectLauncher >> #startUp
> ProjectLauncher >> #startUpAfterLogin

I see that; but then we have to work out why the stdin/out/err filehandles need (re)initialising. FileStream class>>startUp: (true) is supposed to do it as part of the normal startup sequence but I had to add it at the beginning of my doit-file. Not to mention why does it seem to not work at all on Windows? And also, there is still the point that things are not in the requested/required order in the StartUp list.

As an extra excitement, how shall we allow for having startup files that want to avoid the UI starting up - say to support the idea of using Squeak for quick jobs as part of scripting? I'm not at all sure what a good answer would be here, it seems at first thought that we'd need either have two ways to specify the files in the commandline (say, -earlyfilein & -uifilein, which are both horrible and should not be used!) or to have some tags in the files to say where sections get evaluated - perhaps [preUI] & [postUI].


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- Fell out of the family tree.





Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

timrowledge
In reply to this post by fniephaus
By sheer fluke I stumbled on an article that may be of interest here; apparently the 'ultimate multiplication' technique has now been found, building on the work of Karatsuba, Schönhage and Strassen, and lately Harvey & Van Der Hoeven.

Strange stuff but apparently achieving n log(n) steps for n digit multiplies.
https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/
and the original paper at https://hal.archives-ouvertes.fr/hal-02070778/document

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
"bOtHeR" said Pooh, mistaking the LSD tablet for aspirin



Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

Nicolas Cellier
Hi Tim,
That's what i wrote 16 mails above in th thread :)

Le jeu. 2 mai 2019 à 22:45, tim Rowledge <[hidden email]> a écrit :
By sheer fluke I stumbled on an article that may be of interest here; apparently the 'ultimate multiplication' technique has now been found, building on the work of Karatsuba, Schönhage and Strassen, and lately Harvey & Van Der Hoeven.

Strange stuff but apparently achieving n log(n) steps for n digit multiplies.
https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/
and the original paper at https://hal.archives-ouvertes.fr/hal-02070778/document

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
"bOtHeR" said Pooh, mistaking the LSD tablet for aspirin





Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

timrowledge


> On 2019-05-02, at 10:21 PM, Nicolas Cellier <[hidden email]> wrote:
>
> Hi Tim,
> That's what i wrote 16 mails above in th thread :)

I knew that, of course I did, absolutely, how could you possibly doubt me?

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- So dumb, he faxes face up.



Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

timrowledge
A small but valuable improvement in the fibonacci algorithm blatantly stolen from a python version by gkreidel on the Pi forums seems to be ~25% faster for 4784969 fibonacci

!Integer methodsFor: 'mathematical functions' stamp: 'tpr 5/6/2019 12:22'!
fibonacci
"derived from https://www.nayuki.io/page/fast-fibonacci-algorithms"
"4784969 fibonacci"
        | a b c |
        self <= 0 ifTrue: [^0]. "in case somebody tries an inappropriate number"
        a :=  0.
        b := 1.
                self highBit to: 2 by: -1 do:[:i||d e|
                d := ((b bitShift: 1) - a) * a.
                e := a squared + b squared.
                a := d.
                b := e.
                (self bitAt: i) = 1  ifTrue:[
                        c := a + b.
                        a := b.
                        b := c]
                ].
        ^self odd
                ifTrue:[a squared + b squared]
                ifFalse: [((b bitShift: 1) - a) * a]! !

About 75% of time goes on the #squared and 8% on WeakArray finalization.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- A room temperature IQ.



Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

timrowledge
In reply to this post by Nicolas Cellier
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; [hidden email]; http://www.rowledge.org/tim
Strange OpCodes: RIW: Re-Invent Wheel



Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

David T. Lewis

Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

Phil B
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.)

On Mon, Jan 27, 2020 at 8:28 PM David T. Lewis <[hidden email]> 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; [hidden email]; 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




Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

Eliot Miranda-2
Hi Phil,

On Mon, Jan 27, 2020 at 6:07 PM Phil B <[hidden email]> 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 <[hidden email]> 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; [hidden email]; 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


Reply | Threaded
Open this post in threaded view
|

Re: Faster fibonacci

Nicolas Cellier
Hi Phil,
It is essential. Without it, it's very difficult to have correctly rounded conversion float -> ascii decimal ->float.
Also, it may help to implement correctly rounded float functions.
GNU libc uses gmp.
Sometimes, you don't know the accuracy of a float calculus. There are several possible easy strategies like changing the rounding direction, or double the precision, and check the interval you obtain. It's far easier to implement multi precision with integer than with float (though possible).
Chryptography heavily rely on large integer arithmetics.
Symbolic computer algebra also rely on it (the p-adic factorization of polynomials may rapidly lead to huge integers).


Le mar. 28 janv. 2020 à 04:56, Eliot Miranda <[hidden email]> a écrit :
Hi Phil,

On Mon, Jan 27, 2020 at 6:07 PM Phil B <[hidden email]> 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 <[hidden email]> 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; [hidden email]; 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



12