🚀 go-pugleaf

In article <martin.722176263@bert> martin@math.rwth-aachen.de (  Martin Schoenert) writes:

   1)  I want to write a *large integer arithmetic package in C*  that  lets
       me work with integers of several  hundred  or  thousands  of  digits.
       For the  sake of  discussion  let  us assume that  I  am  really only
       interested in addition and multiplication of such integers (I include
       addition only to avoid  that people tell me that I should use modular
       techniques).

   [...]

   If 'TypDigit' is the  type of a digit and 'TypTwoDigits'  is an  unsigned
   integer type twice as wide, I can write

       TypDigit            a;
       TypDigit            b;
       TypTwoDigits        product
       ...
       product = (TypTwoDigits)a * (TypTwoDigits)b;

Good, that's a nice way of parameterizing it.

   The largest unsigned integer type which ANSI gives me is 'unsigned long'.
   With almost all processors and C compilers I know 'unsigned long' is just
   as wide as an register (usually this means 32 bit,  but  not  necessarily
   so).  Please don't tell me that I should buy a C compiler where 'unsigned
   long'  is  twice  as  wide as an register, unless you can tell me which C
   compilers for 80386, MIPS, and Sparc systems have this feature.

   Now most modern processors *do* have  an instruction that  multiplies two
   registers  and puts the  result into a register pair or a set of  special
   registers.

Yes, you are completely right. This is a shortcoming of current
implementations of C for 32bit workstations. They should provide a
64bit integral type, precisely for this reason. (They should probably
also provide an inline function to take advantage of addition with
carry).

   2)  I want to write a portable package that can be used with  every  ANSI
       conforming compiler.  That means that I  cannot  use  extension  such
       as GNU C 'asm' statements, I cannot  use  nonstandard  integer  types
       such as 'long long'.
   
   3)  I want to make the functions in this  package  as  fast  as possible,
       since I am going to use them a lot.

   Of course if one  is  willing to drop requirement 3),  one has a lot more
   options.  One could  use 'asm' code (this is what  GNU  GMP does with GNU
   CC), 'long  long' integer types, or use a small assembler kernel (this is
   what BigNum, PARI, and my arithmetic do).

I think it might well be worth trying to standardize an interface to
arithmetic that provides you with access to the low-level arithmetic
primitives that you need. However, in order to make your code truly
portable, you will need to come up with an interface that takes into
account that there are machines with odd word sizes. Such a facility
needs to have a much more abstract and much more task-specific than a
general facility for accessing "low-level features". That is precisely
why I think that Rubin and Silverman are barking up the wrong tree.

					Thomas.