home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10959 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  3.7 KB
  1. Xref: sparky comp.arch:10959 comp.lang.misc:3813
  2. Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!life.ai.mit.edu!tmb
  3. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  4. Newsgroups: comp.arch,comp.lang.misc
  5. Subject: Re: how to advocate new software/hardware features (Re: Hardware Support for Numeric Algorithms)
  6. Date: 20 Nov 92 14:05:42
  7. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  8.     Perceptive)
  9. Lines: 62
  10. Message-ID: <TMB.92Nov20140542@arolla.idiap.ch>
  11. References: <TMB.92Nov14145619@pollux.idiap.ch> <Bxq7y0.IJ@mentor.cc.purdue.edu>
  12.     <mwm.2n6z@contessa.palo-alto.ca.us> <Bxr8vG.IpI@mentor.cc.purdue.edu>
  13.     <martin.721995695@bert> <martin.722176263@bert>
  14. Reply-To: tmb@idiap.ch
  15. NNTP-Posting-Host: arolla.idiap.ch
  16. In-reply-to: martin@math.rwth-aachen.de's message of 19 Nov 92 12:31:03 GMT
  17.  
  18. In article <martin.722176263@bert> martin@math.rwth-aachen.de (  Martin Schoenert) writes:
  19.  
  20.    1)  I want to write a *large integer arithmetic package in C*  that  lets
  21.        me work with integers of several  hundred  or  thousands  of  digits.
  22.        For the  sake of  discussion  let  us assume that  I  am  really only
  23.        interested in addition and multiplication of such integers (I include
  24.        addition only to avoid  that people tell me that I should use modular
  25.        techniques).
  26.  
  27.    [...]
  28.  
  29.    If 'TypDigit' is the  type of a digit and 'TypTwoDigits'  is an  unsigned
  30.    integer type twice as wide, I can write
  31.  
  32.        TypDigit            a;
  33.        TypDigit            b;
  34.        TypTwoDigits        product
  35.        ...
  36.        product = (TypTwoDigits)a * (TypTwoDigits)b;
  37.  
  38. Good, that's a nice way of parameterizing it.
  39.  
  40.    The largest unsigned integer type which ANSI gives me is 'unsigned long'.
  41.    With almost all processors and C compilers I know 'unsigned long' is just
  42.    as wide as an register (usually this means 32 bit,  but  not  necessarily
  43.    so).  Please don't tell me that I should buy a C compiler where 'unsigned
  44.    long'  is  twice  as  wide as an register, unless you can tell me which C
  45.    compilers for 80386, MIPS, and Sparc systems have this feature.
  46.  
  47.    Now most modern processors *do* have  an instruction that  multiplies two
  48.    registers  and puts the  result into a register pair or a set of  special
  49.    registers.
  50.  
  51. Yes, you are completely right. This is a shortcoming of current
  52. implementations of C for 32bit workstations. They should provide a
  53. 64bit integral type, precisely for this reason. (They should probably
  54. also provide an inline function to take advantage of addition with
  55. carry).
  56.  
  57.    2)  I want to write a portable package that can be used with  every  ANSI
  58.        conforming compiler.  That means that I  cannot  use  extension  such
  59.        as GNU C 'asm' statements, I cannot  use  nonstandard  integer  types
  60.        such as 'long long'.
  61.    
  62.    3)  I want to make the functions in this  package  as  fast  as possible,
  63.        since I am going to use them a lot.
  64.  
  65.    Of course if one  is  willing to drop requirement 3),  one has a lot more
  66.    options.  One could  use 'asm' code (this is what  GNU  GMP does with GNU
  67.    CC), 'long  long' integer types, or use a small assembler kernel (this is
  68.    what BigNum, PARI, and my arithmetic do).
  69.  
  70. I think it might well be worth trying to standardize an interface to
  71. arithmetic that provides you with access to the low-level arithmetic
  72. primitives that you need. However, in order to make your code truly
  73. portable, you will need to come up with an interface that takes into
  74. account that there are machines with odd word sizes. Such a facility
  75. needs to have a much more abstract and much more task-specific than a
  76. general facility for accessing "low-level features". That is precisely
  77. why I think that Rubin and Silverman are barking up the wrong tree.
  78.  
  79.                     Thomas.
  80.