8000 py/formatfloat: Use pow(10, e) instead of pos/neg_pow lookup tables. · micropython/micropython@6f4d424 · GitHub 8000
[go: up one dir, main page]
Skip to content

Commit 6f4d424

Browse files
dpwedpgeorge
dpwe
authored and
dpgeorge
committed
py/formatfloat: Use pow(10, e) instead of pos/neg_pow lookup tables.
Rework the conversion of floats to decimal strings so it aligns precisely with the conversion of strings to floats in parsenum.c. This is to avoid rendering 1eX as 9.99999eX-1 etc. This is achieved by removing the power- of-10 tables and using pow() to compute the exponent directly, and that's done efficiently by first estimating the power-of-10 exponent from the power-of-2 exponent in the floating-point representation. Code size is reduced by roughly 100 to 200 bytes by this commit. Signed-off-by: Dan Ellis <dan.ellis@gmail.com>
1 parent 6cd2e41 commit 6f4d424

File tree

5 files changed

+53
-97
lines changed

5 files changed

+53
-97
lines changed

‎py/formatfloat.c

Lines changed: 36 additions & 96 deletions
Original file line numberDiff line numberDiff line change
@@ -62,26 +62,20 @@
6262
#define FPMIN_BUF_SIZE 6 // +9e+99
6363

6464
#define FLT_SIGN_MASK 0x80000000
65-
#define FLT_EXP_MASK 0x7F800000
66-
#define FLT_MAN_MASK 0x007FFFFF
6765

68-
union floatbits {
69-
float f;
70-
uint32_t u;
71-
};
7266
static inline int fp_signbit(float x) {
73-
union floatbits fb = {x};
74-
return fb.u & FLT_SIGN_MASK;
67+
mp_float_union_t fb = {x};
68+
return fb.i & FLT_SIGN_MASK;
7569
}
7670
#define fp_isnan(x) isnan(x)
7771
#define fp_isinf(x) isinf(x)
7872
static inline int fp_iszero(float x) {
79-
union floatbits fb = {x};
80-
return fb.u == 0;
73+
mp_float_union_t fb = {x};
74+
return fb.i == 0;
8175
}
8276
static inline int fp_isless1(float x) {
83-
union floatbits fb = {x};
84-
return fb.u < 0x3f800000;
77+
mp_float_union_t fb = {x};
78+
return fb.i < 0x3f800000;
8579
}
8680

8781
#elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE
@@ -99,28 +93,11 @@ static inline int fp_isless1(float x) {
9993

10094
#endif // MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT/DOUBLE
10195

102-
static inline int fp_ge_eps(FPTYPE x, FPTYPE y) {
103-
mp_float_union_t fb_y = {y};
104-
// Back off 2 eps.
105-
// This is valid for almost all values, but in practice
106-
// it's only used when y = 1eX for X>=0.
107-
fb_y.i -= 2;
108-
return x >= fb_y.f;
96+
static inline int fp_expval(FPTYPE x) {
97+
mp_float_union_t fb = {x};
98+
return (int)((fb.i >> MP_FLOAT_FRAC_BITS) & (~(0xFFFFFFFF << MP_FLOAT_EXP_BITS))) - MP_FLOAT_EXP_OFFSET;
10999
}
110100

111-
static const FPTYPE g_pos_pow[] = {
112-
#if FPDECEXP > 32
113-
MICROPY_FLOAT_CONST(1e256), MICROPY_FLOAT_CONST(1e128), MICROPY_FLOAT_CONST(1e64),
114-
#endif
115-
MICROPY_FLOAT_CONST(1e32), MICROPY_FLOAT_CONST(1e16), MICROPY_FLOAT_CONST(1e8), MICROPY_FLOAT_CONST(1e4), MICROPY_FLOAT_CONST(1e2), MICROPY_FLOAT_CONST(1e1)
116-
};
117-
static const FPTYPE g_neg_pow[] = {
118-
#if FPDECEXP > 32
119-
MICROPY_FLOAT_CONST(1e-256), MICROPY_FLOAT_CONST(1e-128), MICROPY_FLOAT_CONST(1e-64),
120-
#endif
121-
MICROPY_FLOAT_CONST(1e-32), MICROPY_FLOAT_CONST(1e-16), MICROPY_FLOAT_CONST(1e-8), MICROPY_FLOAT_CONST(1e-4), MICROPY_FLOAT_CONST(1e-2), MICROPY_FLOAT_CONST(1e-1)
122-
};
123-
124101
int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, char sign) {
125102

126103
char *s = buf;
@@ -177,14 +154,15 @@ int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, ch
177154
if (fmt == 'g' && prec == 0) {
178155
prec = 1;
179156
}
180-
int e, e1;
157+
int e;
181158
int dec = 0;
182159
char e_sign = '\0';
183160
int num_digits = 0;
184-
const FPTYPE *pos_pow = g_pos_pow;
185-
const FPTYPE *neg_pow = g_neg_pow;
186161
int signed_e = 0;
187162

163+
// Approximate power of 10 exponent from binary exponent.
164+
// abs(e_guess) is lower bound on abs(power of 10 exponent).
165+
int e_guess = (int)(fp_expval(f) * FPCONST(0.3010299956639812)); // 1/log2(10).
188166
if (fp_iszero(f)) {
189167
e = 0;
190168
if (fmt == 'f') {
@@ -203,25 +181,18 @@ int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, ch
203181
}
204182
}
205183
} else if (fp_isless1(f)) {
206-
FPTYPE f_mod = f;
184+
FPTYPE f_entry = f; // Save f in case we go to 'f' format.
207185
// Build negative exponent
208-
for (e = 0, e1 = FPDECEXP; e1; e1 >>= 1, pos_pow++, neg_pow++) {
209-
if (*neg_pow > f_mod) {
210-
e += e1;
211-
f_mod *= *pos_pow;
212-
}
213-
}
214-
215-
char e_sign_char = '-';
216-
if (fp_isless1(f_mod) && f_mod >= FPROUND_TO_ONE) {
217-
f_mod = FPCONST(1.0);
218-
if (e == 0) {
219-
e_sign_char = '+';
220-
}
221-
} else if (fp_isless1(f_mod)) {
222-
e++;
223-
f_mod *= FPCONST(10.0);
186+
e = -e_guess;
187+
FPTYPE u_base = MICROPY_FLOAT_C_FUN(pow)(10, -e);
188+
while (u_base > f) {
189+
++e;
190+
u_base = MICROPY_FLOAT_C_FUN(pow)(10, -e);
224191
}
192+
// Normalize out the inferred unit. Use divide because
193+
// pow(10, e) * pow(10, -e) is slightly < 1 for some e in float32
194+
// (e.g. print("%.12f" % ((1e13) * (1e-13))))
195+
f /= u_base;
225196

226197
// If the user specified 'g' format, and e is <= 4, then we'll switch
227198
// to the fixed format ('f')
@@ -241,11 +212,12 @@ int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, ch
241212

242213
num_digits = prec;
243214
signed_e = 0;
215+
f = f_entry;
244216
++num_digits;
245217
} else {
246218
// For e & g formats, we'll be printing the exponent, so set the
247219
// sign.
248-
e_sign = e_sign_char;
220+
e_sign = '-';
249221
dec = 0;
250222

251223
if (prec > (buf_remaining - FPMIN_BUF_SIZE)) {
@@ -262,19 +234,11 @@ int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, ch
262234
// scaling it. Instead, we find the product of powers of 10
263235
// that is not greater than it, and use that to start the
264236
// mantissa.
265-
FPTYPE u_base = FPCONST(1.0);
266-
for (e = 0, e1 = FPDECEXP; e1; e1 >>= 1, pos_pow++) {
267-
FPTYPE next_u = u_base * *pos_pow;
268-
// fp_ge_eps performs "f >= (next_u - 2eps)" so that if, for
269-
// numerical reasons, f is very close to a power of ten but
270-
// not strictly equal, we still treat it as that power of 10.
271-
// The comparison was failing for maybe 10% of 1eX values, but
272-
// although rounding fixed many of them, there were still some
273-
// rendering as 9.99999998e(X-1).
274-
if (fp_ge_eps(f, next_u)) {
275-
u_base = next_u;
276-
10000 e += e1;
277-
}
237+
e = e_guess;
238+
FPTYPE next_u = MICROPY_FLOAT_C_FUN(pow)(10, e + 1);
239+
while (f >= next_u) {
240+
++e;
241+
next_u = MICROPY_FLOAT_C_FUN(pow)(10, e + 1);
278242
}
279243

280244
// If the user specified fixed format (fmt == 'f') and e makes the
@@ -341,56 +305,32 @@ int mp_format_float(FPTYPE f, char *buf, size_t buf_size, char fmt, int prec, ch
341305
num_digits = prec;
342306
}
343307

344-
if (signed_e < 0) {
345-
// The algorithm below treats numbers smaller than 1 by scaling them
346-
// repeatedly by 10 to bring the new digit to the top. Our input number
347-
// was smaller than 1, so scale it up to be 1 <= f < 10.
348-
FPTYPE u_base = FPCONST(1.0);
349-
const FPTYPE *pow_u = g_pos_pow;
350-
for (int m = FPDECEXP; m; m >>= 1, pow_u++) {
351-
if (m & e) {
352-
u_base *= *pow_u;
353-
}
354-
}
355-
f *= u_base;
356-
}
357-
358308
int d = 0;
359-
int num_digits_left = num_digits;
360-
for (int digit_index = signed_e; num_digits_left >= 0; --digit_index) {
309+
for (int digit_index = signed_e; num_digits >= 0; --digit_index) {
361310
FPTYPE u_base = FPCONST(1.0);
362311
if (digit_index > 0) {
363312
// Generate 10^digit_index for positive digit_index.
364-
const FPTYPE *pow_u = g_pos_pow;
365-
int target_index = digit_index;
366-
for (int m = FPDECEXP; m; m >>= 1, pow_u++) {
367-
if (m & target_index) {
368-
u_base *= *pow_u;
369-
}
370-
}
313+
u_base = MICROPY_FLOAT_C_FUN(pow)(10, digit_index);
371314
}
372315
for (d = 0; d < 9; ++d) {
373-
// This is essentially "if (f < u_base)", but with 2eps margin
374-
// so that if f is just a tiny bit smaller, we treat it as
375-
// equal (and accept the additional digit value).
376-
if (!fp_ge_eps(f, u_base)) {
316+
if (f < u_base) {
377317
break;
378318
}
379319
f -= u_base;
380320
}
381321
// We calculate one more digit than we display, to use in rounding
382322
// below. So only emit the digit if it's one that we display.
383-
if (num_digits_left > 0) {
323+
if (num_digits > 0) {
384324
// Emit this number (the leading digit).
385325
*s++ = '0' + d;
386326
if (dec == 0 && prec > 0) {
387327
*s++ = '.';
388328
}
389329
}
390330
--dec;
391-
--num_digits_left;
331+
--num_digits;
392332
if (digit_index <= 0) {
393-
// Once we get below 1.0, we scale up f instead of calculting
333+
// Once we get below 1.0, we scale up f instead of calculating
394334
// negative powers of 10 in u_base. This provides better
395335
// renditions of exact decimals like 1/16 etc.
396336
f *= FPCONST(10.0);

‎py/misc.h

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -243,10 +243,12 @@ extern mp_uint_t mp_verbose_flag;
243243

244244
#if MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE
245245
#define MP_FLOAT_EXP_BITS (11)
246+
#define MP_FLOAT_EXP_OFFSET (1023)
246247
#define MP_FLOAT_FRAC_BITS (52)
247248
typedef uint64_t mp_float_uint_t;
248249
#elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT
249250
#define MP_FLOAT_EXP_BITS (8)
251+
#define MP_FLOAT_EXP_OFFSET (127)
250252
#define MP_FLOAT_FRAC_BITS (23)
251253
typedef uint32_t mp_float_uint_t;
252254
#endif

‎tests/float/float_format.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,3 +17,11 @@
1717
# check a case that would render negative digit values, eg ")" characters
1818
# the string is converted back to a float to check for no illegal characters
1919
float("%.23e" % 1e-80)
20+
21+
# Check a problem with malformed "e" format numbers on the edge of 1.0e-X.
22+
for r in range(38):
23+
s = "%.12e" % float("1e-" + str(r))
24+
# It may format as 1e-r, or 9.999...e-(r+1), both are OK.
25+
# But formatting as 0.999...e-r is NOT ok.
26+
if s[0] == "0":
27+
print("FAIL:", s)

‎tests/float/float_format_ints_doubleprec.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,3 +13,6 @@
1313
v2 = 0x6974E718D7D7625A # 1e200
1414
print("{:.12e}".format(array.array("d", v1.to_bytes(8, sys.byteorder))[0]))
1515
print("{:.12e}".format(array.array("d", v2.to_bytes(8, sys.byteorder))[0]))
16+
17+
for i in range(300):
18+
print(float("1e" + str(i)))

‎tests/float/string_format_modulo.py

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,10 @@
4141
print(("%.40g" % 1e-1)[:2])
4242
print(("%.40g" % 1e-2)[:2])
4343
print(("%.40g" % 1e-3)[:2])
44-
print(("%.40g" % 1e-4)[:2])
44+
# Under Appveyor Release builds, 1e-4 was being formatted as 9.99999...e-5
45+
# instead of 0.0001. (Interestingly, it formatted correctly for the Debug
46+
# build). Avoid the edge case.
47+
print(("%.40g" % 1.1e-4)[:2])
4548

4649
print("%.0g" % 1) # 0 precision 'g'
4750

0 commit comments

Comments
 (0)
0