1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
// Adapted from https://github.com/Alexhuszagh/rust-lexical.
//! Algorithms to efficiently convert strings to floats.
use super::bhcomp::*;
use super::cached::*;
use super::errors::*;
use super::float::ExtendedFloat;
use super::num::*;
use super::small_powers::*;
// FAST
// ----
/// Convert mantissa to exact value for a non-base2 power.
///
/// Returns the resulting float and if the value can be represented exactly.
pub(crate) fn fast_path<F>(mantissa: u64, exponent: i32) -> Option<F>
where
F: Float,
{
// `mantissa >> (F::MANTISSA_SIZE+1) != 0` effectively checks if the
// value has a no bits above the hidden bit, which is what we want.
let (min_exp, max_exp) = F::exponent_limit();
let shift_exp = F::mantissa_limit();
let mantissa_size = F::MANTISSA_SIZE + 1;
if mantissa == 0 {
Some(F::ZERO)
} else if mantissa >> mantissa_size != 0 {
// Would require truncation of the mantissa.
None
} else if exponent == 0 {
// 0 exponent, same as value, exact representation.
let float = F::as_cast(mantissa);
Some(float)
} else if exponent >= min_exp && exponent <= max_exp {
// Value can be exactly represented, return the value.
// Do not use powi, since powi can incrementally introduce
// error.
let float = F::as_cast(mantissa);
Some(float.pow10(exponent))
} else if exponent >= 0 && exponent <= max_exp + shift_exp {
// Check to see if we have a disguised fast-path, where the
// number of digits in the mantissa is very small, but and
// so digits can be shifted from the exponent to the mantissa.
// https://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/
let small_powers = POW10_64;
let shift = exponent - max_exp;
let power = small_powers[shift as usize];
// Compute the product of the power, if it overflows,
// prematurely return early, otherwise, if we didn't overshoot,
// we can get an exact value.
let value = mantissa.checked_mul(power)?;
if value >> mantissa_size != 0 {
None
} else {
// Use powi, since it's correct, and faster on
// the fast-path.
let float = F::as_cast(value);
Some(float.pow10(max_exp))
}
} else {
// Cannot be exactly represented, exponent too small or too big,
// would require truncation.
None
}
}
// MODERATE
// --------
/// Multiply the floating-point by the exponent.
///
/// Multiply by pre-calculated powers of the base, modify the extended-
/// float, and return if new value and if the value can be represented
/// accurately.
fn multiply_exponent_extended<F>(fp: &mut ExtendedFloat, exponent: i32, truncated: bool) -> bool
where
F: Float,
{
let powers = ExtendedFloat::get_powers();
let exponent = exponent.saturating_add(powers.bias);
let small_index = exponent % powers.step;
let large_index = exponent / powers.step;
if exponent < 0 {
// Guaranteed underflow (assign 0).
fp.mant = 0;
true
} else if large_index as usize >= powers.large.len() {
// Overflow (assign infinity)
fp.mant = 1 << 63;
fp.exp = 0x7FF;
true
} else {
// Within the valid exponent range, multiply by the large and small
// exponents and return the resulting value.
// Track errors to as a factor of unit in last-precision.
let mut errors: u32 = 0;
if truncated {
errors += u64::error_halfscale();
}
// Multiply by the small power.
// Check if we can directly multiply by an integer, if not,
// use extended-precision multiplication.
match fp
.mant
.overflowing_mul(powers.get_small_int(small_index as usize))
{
// Overflow, multiplication unsuccessful, go slow path.
(_, true) => {
fp.normalize();
fp.imul(&powers.get_small(small_index as usize));
errors += u64::error_halfscale();
}
// No overflow, multiplication successful.
(mant, false) => {
fp.mant = mant;
fp.normalize();
}
}
// Multiply by the large power
fp.imul(&powers.get_large(large_index as usize));
if errors > 0 {
errors += 1;
}
errors += u64::error_halfscale();
// Normalize the floating point (and the errors).
let shift = fp.normalize();
errors <<= shift;
u64::error_is_accurate::<F>(errors, fp)
}
}
/// Create a precise native float using an intermediate extended-precision float.
///
/// Return the float approximation and if the value can be accurately
/// represented with mantissa bits of precision.
#[inline]
pub(crate) fn moderate_path<F>(
mantissa: u64,
exponent: i32,
truncated: bool,
) -> (ExtendedFloat, bool)
where
F: Float,
{
let mut fp = ExtendedFloat {
mant: mantissa,
exp: 0,
};
let valid = multiply_exponent_extended::<F>(&mut fp, exponent, truncated);
(fp, valid)
}
// FALLBACK
// --------
/// Fallback path when the fast path does not work.
///
/// Uses the moderate path, if applicable, otherwise, uses the slow path
/// as required.
pub(crate) fn fallback_path<F>(
integer: &[u8],
fraction: &[u8],
mantissa: u64,
exponent: i32,
mantissa_exponent: i32,
truncated: bool,
) -> F
where
F: Float,
{
// Moderate path (use an extended 80-bit representation).
let (fp, valid) = moderate_path::<F>(mantissa, mantissa_exponent, truncated);
if valid {
return fp.into_float::<F>();
}
// Slow path, fast path didn't work.
let b = fp.into_downward_float::<F>();
if b.is_special() {
// We have a non-finite number, we get to leave early.
b
} else {
bhcomp(b, integer, fraction, exponent)
}
}
|
