home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3436 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.9 KB
  1. Path: sparky!uunet!spool.mu.edu!uwm.edu!csd4.csd.uwm.edu!markh
  2. From: markh@csd4.csd.uwm.edu (Mark)
  3. Newsgroups: comp.programming
  4. Subject: Re: Arbitrary precision with large bases
  5. Date: 8 Jan 1993 01:00:14 GMT
  6. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  7. Lines: 52
  8. Message-ID: <1iijmuINNmh4@uwm.edu>
  9. References: <1icne6INNpjb@uwm.edu> <martin.726311424@bert>
  10. NNTP-Posting-Host: 129.89.7.4
  11.  
  12. In article <martin.726311424@bert> martin@math.rwth-aachen.de (  Martin Schoenert) writes:
  13. >Base 2^32 has the following advantages.
  14. >
  15. >a)  the larger the base the fewer digits any given integer has in this
  16. >    base.  Since (for example) the performance of the multiplication
  17. >    is proportional to the product of the number of digits of the
  18. >    operands it is always a win to use larger bases (though the win
  19. >    with base 2^32 over base 10^9 is only about 12.5%).
  20. >
  21. >b)  many modern processors have a 32bit x 32bit -> 64bit instruction.
  22. >    This instruction cannot directly be used from within C, so one needs
  23. >    a little bit of assembler.  However if one does that one gets
  24. >    AB div BASE and AB mod BASE with one instruction.
  25.  
  26. These are disadvantages too.  If you want extra room for work space in
  27. intermediate calculations (such as adding two digits in base 2^N) in a portable
  28. manner, you should really use 2^31 or 2^30 as the base instead.
  29.  
  30. The advantages of 2^30 (or 10^9) are that (1) it's (almost) equal to a perfect
  31. power of 2, it (almost) factors evenly into two equal factors (both (almost)
  32. equal to 2^15) which comes in handy for multiplication, and it's a perfect
  33. cube, which comes in handy for division.
  34.  
  35. >With respect to aspect (2).  Knuth shows that if you normalize the
  36. >divisor such that its leading digit is larger than or equal to BASE/2 and
  37. >compute an appoximation of a digit of the quotient by dividing the
  38. >leading three digits of the remainder by the leading two digits of the
  39. >divisor the approximation is at most too large by 1 *independent* of the
  40. >base.  It is easy to detect if the digit is too large and make the
  41. >appropriate corrections.
  42.  
  43. Another way to normalize, with a base that is a perfect cube (N^3) is to
  44. (1) normalize the divisor so that its leading digit lies between N and N^2 - 1,
  45. and (2) always arrange so that the dividend's leading digit never exceed N
  46. times the divisor's leading digit (divide by N if need be).
  47.  
  48. This will likewise guarantee that the approximation never be off by more than
  49. 1.
  50.  
  51. Also, it's easier to underestimate the quotient's digit, rather than
  52. overestimate it.  Then division just consists of shifts and subtracts -- no
  53. corrections and no backtracking.  The basic algorithm becomes:
  54.  
  55. remainder = dividend; quotient = 0;
  56. while (1) {
  57.    if (divisor > remainder) {
  58.       multiply quotient and remainder by N
  59.    } else {
  60.       digit = leading_digit(remainder) / (leading_digit(divisor) + 1)
  61.       remainder -= digit*divisor; quotient += digit
  62.    }
  63. }
  64.