llvm / llvm-project / a87782c34d667d1c1a18fe82a9a7abfc72fd345b / . / libc / utils / mathtools / GenerateHPDConstants.py

from math import * | |

''' | |

This script is used to generate a table used by | |

libc/src/__support/high_precision_decimal.h. | |

For the ith entry in the table there are two values (indexed starting at 0). | |

The first value is the number of digits longer the second value would be if | |

multiplied by 2^i. | |

The second value is the smallest number that would create that number of | |

additional digits (which in base ten is always 5^i). Anything less creates one | |

fewer digit. | |

As an example, the 3rd entry in the table is {1, "125"}. This means that if | |

125 is multiplied by 2^3 = 8, it will have exactly one more digit. | |

Multiplying it out we get 125 * 8 = 1000. 125 is the smallest number that gives | |

that extra digit, for example 124 * 8 = 992, and all larger 3 digit numbers | |

also give only one extra digit when multiplied by 8, for example 8 * 999 = 7992. | |

This makes sense because 5^3 * 2^3 = 10^3, the smallest 4 digit number. | |

For numbers with more digits we can ignore the digits past what's in the second | |

value, since the most significant digits determine how many extra digits there | |

will be. Looking at the previous example, if we have 1000, and we look at just | |

the first 3 digits (since 125 has 3 digits), we see that 100 < 125, so we get | |

one fewer than 1 extra digits, which is 0. | |

Multiplying it out we get 1000 * 8 = 8000, which fits the expectation. | |

Another few quick examples: | |

For 1255, 125 !< 125, so 1 digit more: 1255 * 8 = 10040 | |

For 9999, 999 !< 125, so 1 digit more: 9999 * 8 = 79992 | |

Now let's try an example with the 10th entry: {4, "9765625"}. This one means | |

that 9765625 * 2^10 will have 4 extra digits. | |

Let's skip straight to the examples: | |

For 1, 1 < 9765625, so 4-1=3 extra digits: 1 * 2^10 = 1024, 1 digit to 4 digits is a difference of 3. | |

For 9765624, 9765624 < 9765625 so 3 extra digits: 9765624 * 1024 = 9999998976, 7 digits to 10 digits is a difference of 3. | |

For 9765625, 9765625 !< 9765625 so 4 extra digits: 9765625 * 1024 = 10000000000, 7 digits to 11 digits is a difference of 4. | |

For 9999999, 9999999 !< 9765625 so 4 extra digits: 9999999 * 1024 = 10239998976, 7 digits to 11 digits is a difference of 4. | |

For 12345678, 1234567 < 9765625 so 3 extra digits: 12345678 * 1024 = 12641974272, 8 digits to 11 digits is a difference of 3. | |

This is important when left shifting in the HPD class because it reads and | |

writes the number backwards, and to shift in place it needs to know where the | |

last digit should go. Since a binary left shift by i bits is the same as | |

multiplying by 2^i we know that looking up the ith element in the table will | |

tell us the number of additional digits. If the first digits of the number | |

being shifted are greater than or equal to the digits of 5^i (the second value | |

of each entry) then it is just the first value in the entry, else it is one | |

fewer. | |

''' | |

# Generate Left Shift Table | |

outStr = "" | |

for i in range(61): | |

tenToTheI = 10**i | |

fiveToTheI = 5**i | |

outStr += "{" | |

# The number of new digits that would be created by multiplying 5**i by 2**i | |

outStr += str(ceil(log10(tenToTheI) - log10(fiveToTheI))) | |

outStr += ', "' | |

if not i == 0: | |

outStr += str(fiveToTheI) | |

outStr += '"},\n' | |

print(outStr) |