[Q] Project: Better performance for LargeIntegers

Dean_Swan at Mitel.COM Dean_Swan at Mitel.COM
Mon Nov 1 18:07:58 UTC 1999



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





More information about the Squeak-dev mailing list