fork/rust

git clone https://git.julia.blue/fork/rust

borsAuto merge of #66089 - Mark-Simulacrum:stable-next, r=Mark-Simulacrum4560ea788cb

1.39.0
3.4 KiB137 linesraw
1#!/usr/bin/env python2.7
2
3"""
4Generate powers of ten using William Clinger's ``AlgorithmM`` for use in
5decimal to floating point conversions.
6
7Specifically, computes and outputs (as Rust code) a table of 10^e for some
8range of exponents e. The output is one array of 64 bit significands and
9another array of corresponding base two exponents. The approximations are
10normalized and rounded perfectly, i.e., within 0.5 ULP of the true value.
11
12The representation ([u64], [i16]) instead of the more natural [(u64, i16)]
13is used because (u64, i16) has a ton of padding which would make the table
14even larger, and it's already uncomfortably large (6 KiB).
15"""
16from __future__ import print_function
17import sys
18from math import ceil, log
19from fractions import Fraction
20from collections import namedtuple
21
22
23N = 64  # Size of the significand field in bits
24MIN_SIG = 2 ** (N - 1)
25MAX_SIG = (2 ** N) - 1
26
27# Hand-rolled fp representation without arithmetic or any other operations.
28# The significand is normalized and always N bit, but the exponent is
29# unrestricted in range.
30Fp = namedtuple('Fp', 'sig exp')
31
32
33def algorithm_m(f, e):
34    assert f > 0
35    if e < 0:
36        u = f
37        v = 10 ** abs(e)
38    else:
39        u = f * 10 ** e
40        v = 1
41    k = 0
42    x = u // v
43    while True:
44        if x < MIN_SIG:
45            u <<= 1
46            k -= 1
47        elif x >= MAX_SIG:
48            v <<= 1
49            k += 1
50        else:
51            break
52        x = u // v
53    return ratio_to_float(u, v, k)
54
55
56def ratio_to_float(u, v, k):
57    q, r = divmod(u, v)
58    v_r = v - r
59    z = Fp(q, k)
60    if r < v_r:
61        return z
62    elif r > v_r:
63        return next_float(z)
64    elif q % 2 == 0:
65        return z
66    else:
67        return next_float(z)
68
69
70def next_float(z):
71    if z.sig == MAX_SIG:
72        return Fp(MIN_SIG, z.exp + 1)
73    else:
74        return Fp(z.sig + 1, z.exp)
75
76
77def error(f, e, z):
78    decimal = f * Fraction(10) ** e
79    binary = z.sig * Fraction(2) ** z.exp
80    abs_err = abs(decimal - binary)
81    # The unit in the last place has value z.exp
82    ulp_err = abs_err / Fraction(2) ** z.exp
83    return float(ulp_err)
84
85HEADER = """
86//! Tables of approximations of powers of ten.
87//! DO NOT MODIFY: Generated by `src/etc/dec2flt_table.py`
88"""
89
90
91def main():
92    print(HEADER.strip())
93    print()
94    print_proper_powers()
95    print()
96    print_short_powers(32, 24)
97    print()
98    print_short_powers(64, 53)
99
100
101def print_proper_powers():
102    MIN_E = -305
103    MAX_E = 305
104    e_range = range(MIN_E, MAX_E+1)
105    powers = []
106    for e in e_range:
107        z = algorithm_m(1, e)
108        err = error(1, e, z)
109        assert err < 0.5
110        powers.append(z)
111    print("pub const MIN_E: i16 = {};".format(MIN_E))
112    print("pub const MAX_E: i16 = {};".format(MAX_E))
113    print()
114    typ = "([u64; {0}], [i16; {0}])".format(len(powers))
115    print("pub const POWERS: ", typ, " = ([", sep='')
116    for z in powers:
117        print("    0x{:x},".format(z.sig))
118    print("], [")
119    for z in powers:
120        print("    {},".format(z.exp))
121    print("]);")
122
123
124def print_short_powers(num_bits, significand_size):
125    max_sig = 2**significand_size - 1
126    # The fast path bails out for exponents >= ceil(log5(max_sig))
127    max_e = int(ceil(log(max_sig, 5)))
128    e_range = range(max_e)
129    typ = "[f{}; {}]".format(num_bits, len(e_range))
130    print("pub const F", num_bits, "_SHORT_POWERS: ", typ, " = [", sep='')
131    for e in e_range:
132        print("    1e{},".format(e))
133    print("];")
134
135
136if __name__ == '__main__':
137    main()