Logarithm instruction mlog needs discussion
#150
Comments
|
Its a problem in Rust stdlib: fn main() {
let b = 1000u64;
let c = 10u64;
let x = (b as f64).log(c as f64).floor() as u64;
// Truncate incorrectly to `2`
assert_eq!(2, x);
let b = 1000f64;
let c = 10f64;
let x = b.log(c);
// Result is some approximation to 3; 2.999~
assert!(2.9 < x && x < 3.0);
let b = 1000f64;
let x = b.log10();
// Bases 2 and 10 are more precise as in the language specs
assert_eq!(3.0, x);
}As I see, we have some alternatives
let b = 1000f64;
let c = 10f64;
let x = b.log(c) + f64::EPSILON;
assert_eq!(3.0, x);I favor option |
|
We should find a solution that avoids f64 if at all possible due to imprecision of floating point numbers. While epsilon fixes one edge case, there may be others it doesn't fix due to f64 precision. |
|
I do want to add context that one major use for |
|
I think the best solution would be to use the unstable The implementation behaves correctly for our use cases. For instance, it gives The impl boils down to some sanity checks for values, and then let mut n = 0;
let mut r = exp;
while r >= base {
r /= base;
n += 1;
}
return n;As we can see, worst case would likely be some small-but-hard-to-divide-with number. In the worst theoretical case, i.e. when division takes constant cycles, base is BenchmarkThe ilog-based code is a bit faster for small values, but even 16x slower for large exponent and small base. We can as the compiler to specialize for some common cases, making them them even faster. Also, if we special-case the smallest bases, those already reduce the worst-case execution time as well. This gives 5x worst case compared to the floating point, while making many common cases faster than the float impl. ResultsRunning with
Code#![feature(test, int_log)]
extern crate test;
use std::time::Instant;
const ROUNDS: usize = 10_000_000;
#[inline(always)]
const fn custom_log(exp: u64, base: u64) -> u32 {
let mut n = 0;
let mut r = exp;
while r >= base {
r /= base;
n += 1;
}
return n;
}
const fn custom(exp: u64, base: u64) -> Option<u32> {
if exp <= 0 || base <= 1 {
None
} else {
Some(match base {
2 => custom_log(exp, 2),
3 => custom_log(exp, 3),
4 => custom_log(exp, 4),
5 => custom_log(exp, 5),
10 => custom_log(exp, 10),
n => custom_log(exp, n),
})
}
}
fn main() {
print!("Exponent | ");
print!("Base | ");
print!("ilog timing | ");
print!("custom-impl timing | ");
print!("float timing | ");
print!("ilog/float timing |");
println!("custom/float timing");
println!("{}", "---------------------:|".repeat(7).strip_prefix("-").unwrap().strip_suffix(":|").unwrap());
for exp in [2, 3, 1_000, 1337, 2_147_483_647, u64::MAX] {
for base in [2, 3, 7, 10, 16, 1337, 2_147_483_647] {
assert_eq!(exp.checked_ilog(base), custom(exp, base));
let a_start = Instant::now();
for _ in 0..ROUNDS {
let b: u64 = test::black_box(exp);
let c: u64 = test::black_box(base);
test::black_box(b.checked_ilog(c));
}
let a_duration = a_start.elapsed();
let b_start = Instant::now();
for _ in 0..ROUNDS {
let b: u64 = test::black_box(exp);
let c: u64 = test::black_box(base);
test::black_box(custom(b, c));
}
let b_duration = b_start.elapsed();
let c_start = Instant::now();
for _ in 0..ROUNDS {
let b: u64 = test::black_box(exp);
let c: u64 = test::black_box(base);
test::black_box((b as f64).log(c as f64).floor());
}
let c_duration = c_start.elapsed();
let ratio1 = (a_duration.as_micros() as f64) / (c_duration.as_micros() as f64);
let ratio2 = (b_duration.as_micros() as f64) / (c_duration.as_micros() as f64);
println!("{exp:<20} | {base:<20} | {a_duration:>20.3?} | {b_duration:>20.3?}| {c_duration:>20.3?} | {ratio1:>16.4} | {ratio2:>16.4}");
}
}
}AlternativesIf this is not sufficiently fast and we still want the correct solution, maybe we could implement some proven-efficient algorithm, e.g. this one https://hal.archives-ouvertes.fr/hal-01227877/document |
|
Taking a performance hit here is acceptable since precision errors can accumulate and this may be used in financial contexts. We must prioritize numerical precision and correctness over performance. Taking a dependency on nightly will break too much tooling and external processes, and since we don't expect ilog to stay in nightly long I don't think it's worth the lift to make the process change now. Given it is likely temporary, I'm ok with copying the Rust impl for now until it has stabilized (unless there's some integer math library out there that has already done the same thing). Regarding alternate algorithms, extra perf is always nice but let's get a vetted implementation in place first and then optimize later. Regarding gas pricing, we'll need to bench this operation based on the worst case as variably pricing the log op based on the inputs could add more overhead and complicate things. |
I would expect that
assert(1000.logarithm(10) == 3);would pass, but it does not.Instead, logging
1000.logarithm(10)returns2,The testing I've done uses this implementation in sway:
Note that other cases are working as expected, i.e:
The text was updated successfully, but these errors were encountered: