libc/utils/mathtools/GenerateHPDConstants.py

   1 from math import *
   2
   3 """
   4 This script is used to generate a table used by
   5 libc/src/__support/high_precision_decimal.h.
   6
   7 For the ith entry in the table there are two values (indexed starting at 0).
   8 The first value is the number of digits longer the second value would be if
   9 multiplied by 2^i.
  10 The second value is the smallest number that would create that number of
  11 additional digits (which in base ten is always 5^i). Anything less creates one
  12 fewer digit.
  13
  14 As an example, the 3rd entry in the table is {1, "125"}. This means that if
  15 125 is multiplied by 2^3 = 8, it will have exactly one more digit.
  16 Multiplying it out we get 125 * 8 = 1000. 125 is the smallest number that gives
  17 that extra digit, for example 124 * 8 = 992, and all larger 3 digit numbers
  18 also give only one extra digit when multiplied by 8, for example 8 * 999 = 7992.
  19 This makes sense because 5^3 * 2^3 = 10^3, the smallest 4 digit number.
  20
  21 For numbers with more digits we can ignore the digits past what's in the second
  22 value, since the most significant digits determine how many extra digits there
  23 will be. Looking at the previous example, if we have 1000, and we look at just
  24 the first 3 digits (since 125 has 3 digits), we see that 100 < 125, so we get
  25 one fewer than 1 extra digits, which is 0.
  26 Multiplying it out we get 1000 * 8 = 8000, which fits the expectation.
  27 Another few quick examples:
  28 For 1255, 125 !< 125, so 1 digit more: 1255 * 8 = 10040
  29 For 9999, 999 !< 125, so 1 digit more: 9999 * 8 = 79992
  30
  31 Now let's try an example with the 10th entry: {4, "9765625"}. This one means
  32 that 9765625 * 2^10 will have 4 extra digits.
  33 Let's skip straight to the examples:
  34 For 1, 1 < 9765625, so 4-1=3 extra digits: 1 * 2^10 = 1024, 1 digit to 4 digits is a difference of 3.
  35 For 9765624, 9765624 < 9765625 so 3 extra digits: 9765624 * 1024 = 9999998976, 7 digits to 10 digits is a difference of 3.
  36 For 9765625, 9765625 !< 9765625 so 4 extra digits: 9765625 * 1024 = 10000000000, 7 digits to 11 digits is a difference of 4.
  37 For 9999999, 9999999 !< 9765625 so 4 extra digits: 9999999 * 1024 = 10239998976, 7 digits to 11 digits is a difference of 4.
  38 For 12345678, 1234567 < 9765625 so 3 extra digits: 12345678 * 1024 = 12641974272, 8 digits to 11 digits is a difference of 3.
  39
  40
  41 This is important when left shifting in the HPD class because it reads and
  42 writes the number backwards, and to shift in place it needs to know where the
  43 last digit should go. Since a binary left shift by i bits is the same as
  44 multiplying by 2^i we know that looking up the ith element in the table will
  45 tell us the number of additional digits. If the first digits of the number
  46 being shifted are greater than or equal to the digits of 5^i (the second value
  47 of each entry) then it is just the first value in the entry, else it is one
  48 fewer.
  49 """
  50
  51
  52 # Generate Left Shift Table
  53 outStr = ""
  54 for i in range(61):
  55     tenToTheI = 10**i
  56     fiveToTheI = 5**i
  57     outStr += "{"
  58     # The number of new digits that would be created by multiplying 5**i by 2**i
  59     outStr += str(ceil(log10(tenToTheI) - log10(fiveToTheI)))
  60     outStr += ', "'
  61     if not i == 0:
  62         outStr += str(fiveToTheI)
  63     outStr += '"},\n'
  64
  65 print(outStr)