Dean:

Thanks for getting the references together; I was just about to do it 
and your list is better anyway. I'd add:

	6) Multiple Precision Arithmetic, chapter 4.3 of Knuth's The 
Art of Computer Programming, Volume 2, Third Edition.


Various ramblings about other posts to this thread:

* I don't find the current implementation of large integers to be 
very useful; even with occasional use, it's like hitting a brick wall.

* Space/performance tradeoff - I'd like to see what this is before 
making decisions. I'm interested in both large Squeak systems on 
high-end desktop machines AND tiny Squeak systems running in my 
wristwatch or shirt pocket. It might well be that the space hit is 
not that large and that fast LargeInteger support on a tiny machine 
might be very useful, especially if the machine lacks good 
floating-point support.

* Simple implementations: I'd much prefer a very high-performance 
implementation. I don't want to take a huge hit when an integer 
exceeds 30 bits. IE, if it's going to be done it would be good if the 
final version was extremely fast.

* Optimizing special cases:  There are lots of applications where one 
only needs 32 or 64 bits. (See below). These cases probably should be 
special.

* Other users of integers: For example, the random number generator 
in Squeak uses floating-point to get around the 30 bit small integer 
limit. Virtually all well-tested generators are for 32 bit integers 
and it is a very major bit of work to create a 30 bit generator. Dan 
and I found a major performance improvement using floating-point 
numbers as 'integers' when generating random numbers. If large 
integers handled 32-bit integers well, then the algorithm could be 
switched back, especially on small machines where floating-point 
support is poor or missing.

Dave


At 13:07 -0500 11/1/99, Dean_Swan at Mitel.COM wrote:
>From:  Dean Swan at MITEL on 11/01/99 01:07 PM
>
>Before anybody gets too far along on this, I'd like to encourage folks to look
>at a few references for work already done in the area of multiple precision
>arithmetic:
>
>     1) "Multiple-Precision Arithmetic in C", Kaliski, Burton S., Jr., Dr.
>Dobb's Journal, August 1992
>     2) "The Z80180 and Big-number Arithmetic", Kaliski, Burton S., Jr., Dr.
>Dobb's Journal, September 1993
>     3) "Arbirtrary Precision Floating Point Arithmetic", Moteller, Frederick
>C., Dr. Dobb's Journal, September 1993
>     3) "Using the Multiple Precision Library", Rogers, John, Dr. Dobb's
>Journal, January 1995
>     4) "Basic Arithmetic with Inifinite Integers", Hamilton, Jeffery W., Dr.
>Dobb's Journal January 1995
>     5) Chapter 20, Section 20.6 "Arithmetic at Arbitrary 
>Precision", Numerical
>Recipes in C, (c) 1988-1992 Cambridge University Press.
> 
>http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf/c20-6.pdf
>
>The first two of these references were written by the Cheif Scientist (at the
>time, I don't know if he still is) at RSA Laboratories, with cryptographic
>applications in mind, and he has some interesting things to say about
>performance.
>
>The _Numerical_Recipes_In_C_  (sorry about the _ underscores for those of you
>reading your mail with Celeste), shows a neat trick to do fast multiple
>precision multiplies using the FFT.  Since Squeak already has a pretty good
>implementation of the FFT, this may be worth looking at.  It may offer a very
>efficient way to do LargeInteger multiplies, without new primitives.
>
>A web search on 'multiple or arbitrary precision arithmetic' also will yeild
>lots of references (of varying quality, as usual).  Because of it's uses in
>cryptography, amongst other things, a lot of work has been done in the area of
>multiple precision arithmetic since the original implementation of the
>LargeInteger classes in Squeak.
>
>
>
>Also, just my opinion, but if people feel compelled to implement 
>primitives for
>this stuff, I would definitely like to see them implemented in Smalltalk, as
>plug-ins.  I think Squeak already has too many primitives (all in the name of
>performance, to be sure), and they just move the whole system 
>further away from
>one of Dan Ingalls' original design premises, that Smalltalk be a system that
>could be completely understood by a single person.  I would love to see some
>effort put into simplifying Squeak, without eliminating functionality, of
>course.  Especially since my ideal target environment is the Casio 
>E-105.  (BTW,
>I am making some progress on my Cursor/Sensor changes for the E-105. 
>I'll post
>an update in the near future).
>
>
>
>                              -Dean Swan
>
>                              dean_swan at mitel.com

_______________________________
David N. Smith
IBM T J Watson Research Center
Hawthorne, NY
_______________________________
Any opinions or recommendations
herein are those of the author
and not of his employer.