MROO has float rounding issues #260
Comments
|
I benchmarked the generally fast While the num-integer is a bit faster on the average case compared to the current floating point solution, it has some really bad edge cases. Benchmarks found over 70x runtime cases and I suspect even 100x would be possible. See The custom implementation seen below performs acceptably. For non-interesting inputs it's four times faster. Even in the worst case it only takes around three times longer than the current version. Custom error correctionfn custom(target: u64, nth_root: u32) -> u64 {
if nth_root == 0 {
panic!();
}
if nth_root == 1 || target <= 1 {
return target;
}
if nth_root > 64 {
// for any n>1, n**64 can never fit into u64
return 1;
}
if nth_root as u64 >= target {
return 1;
}
// Use floating point operation to get a guess for the starting point.
// This is at most off by one in either direction.
let guess = (target as f64).powf((nth_root as f64).recip()) as u64;
let Some(g1) = guess.checked_pow(nth_root) else {
// guess**nth_root >= 2**64 and target < 2**64
return guess - 1;
};
if target < g1 {
return guess - 1;
}
let Some(g2) = (guess + 1).checked_pow(nth_root) else {
// (guess + 1)**nth_root >= 2**64 and target < 2**64
return guess;
};
if target < g2 {
return guess;
}
guess + 1
}Results
|
|
Hey @Dentosal any idea what the main usage of time is on your benchmarks? Would be interesting to get some flamegraphs to compare the two. |
|
I can look into it, but flamegraphs are not going to help here, since the work is completely CPU-bound and inlined into a single function, |
|
My older implementation had a bug that it would produce incorrect values for some weird cases with big numbers like nroot(15455138536657945190, 2) and nroot(11875230360893570326, 27). These have now been fixed and updated in the earlier comment along with the benchmark. Unfortunately I'm unable to prove that the error is always small enough that my code is correct. However, I'm rather confident that it is. I have ran following tests for it, verifying it against the num_integer crate:
Also ran this through with my mathematician friend who assured me that the error in the initial guess will never exceed one to either direction. I verified the central points about that myself as well. Most importantly, 1024 is the largest absolute error when representing integers below 264 with f64, and in those cases the error will be about 0.00005, which is several magnitudes on the safe area. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Similarly to the MLOG issues discussed in #150, MROO also has floating point rounding issues. This is the only location of the vm still using floats.
For instance, calling MROO with values
mroo(647214625, 3), i.e. cube root of 647214625, gives 864.9999999999997 in floating point, while 865**3 == 647214625.I'll investigate the performance impact of handling this with integer-only operations.
The text was updated successfully, but these errors were encountered: