rust-lang
Tracking Issue for Integer::{ilog,ilog2,ilog10}
Feature gate: #![feature(int_log)]
Stabilization report: https://github.com/rust-lang/rust/issues/70887#issuecomment-1210602692
This is a tracking issue for adding {checked_,}{ilog,ilog2,ilog10} methods to {u8,u16,u32,u64,u128}. A full rationale can be found in https://github.com/rust-lang/rust/pull/80918#issue-552884252. But in short: integer logarithms are fairly common, but require care to implement correctly, and effort to implement efficiently.
Because we expose log methods for floats it can be tempting for users to use that instead, which can lead to rounding errors. In the following example we're trying to calculate base10 for an integer. We might try and calculate the base2 for the values, and attempt a base swap to arrive at base10. However because we're performing intermediate rounding we arrive at the wrong result:
// log10(900) = ~2.95 = 2
dbg!(900f32.log10() as u64);
// log base change rule: logb(x) = logc(x) / logc(b)
// log2(900) / log2(10) = 9/3 = 3, which is incorrect!
dbg!((900f32.log2() as u64) / (10f32.log2() as u64));
Public API
// integer log
assert_eq!(5_u16.ilog(5), 1);
assert_eq!(2_u32.ilog2(), 1);
assert_eq!(10_u32.ilog10(), 1);
// checked integer log
assert_eq!(5_u16.checked_ilog(5), Some(1));
assert_eq!(2_u32.checked_ilog2(), Some(1));
assert_eq!(10_u32.checked_ilog10(), Some(1));
assert_eq!(0_u64.checked_ilog(5), None);
Steps / History
- [x] Implementation: https://github.com/rust-lang/rust/pull/80918
- [x] Stabilization report https://github.com/rust-lang/rust/issues/70887#issuecomment-1210602692
- [ ] Final comment period (FCP)
Unresolved Questions
- [x] Can we further optimize the
ilog10implementation? https://github.com/rust-lang/rust/pull/70835#issuecomment-609976593 - [x] Can we make these methods
const fn? - [x] Can we implement these types for
NonZero{Int}? https://github.com/rust-lang/rust/pull/70835#issuecomment-611336828- [x] Can we omit returning
Optionforilog2/ilog10onNonZero{Int}?
- [x] Can we omit returning
- [x] Should the methods be called
Integer::{ilog,ilog2,ilog10}instead? https://github.com/rust-lang/rust/pull/70835#issuecomment-611998098 https://github.com/rust-lang/rust/issues/70887#issuecomment-616580640
Implementation History
- https://github.com/rust-lang/rust/pull/70835 - initial PR, closed due to inactivity
- https://github.com/rust-lang/rust/pull/80918 - attempt 2 to implement
logmethods, merged - https://github.com/rust-lang/rust/pull/92956 -
logmethods forNonZerotypes - https://github.com/rust-lang/rust/pull/100332 - rename
logmethods toilog
Having those as const fn is going to be useful to initialize constants, etc.
Another idea for the naming bikeshed: log2_floor() etc. or some variation. Prevents mistakes w.r.t. whether it computes floor(log(n)) or ceil(log(n)) or something else. I am aware of the reasons why it's floor, but it was not immediately obvious to me when I first saw their signature, and I am most likely not alone.
@hanna-kruppe This was brought up before, and was addressed in https://github.com/rust-lang/rust/pull/70835#issuecomment-609795147:
(...) the proposal returns the floor (...)
That's an interesting statement. I was under the impression that integer operations always floor unless specified otherwise. For example integer division works the same way:
// 7/3 = ~2.33 = 2 assert_eq!(7u8 / 3u8, 2u8);The ecosystem contains extensions for e.g.
integer::div_ceilwhich would round the value up. However these are not part ofstd, and if they were introduced they would likely use a_ceilsuffix as well.
Does this make sense, or do you feel there is still missing something?
I am aware of that exchange, it gives one of the reasons for preferring floor semantics that I was referring to. I don't disagree with that being the chosen behavior, I just think making it explicit in the name would be helpful sometimes and not cause any harm otherwise. While it's true that all the methods in std that have to pick one prefer floor over ceil, I believe all of those methods are (variants of) integer division, so it might not be (or at least be perceived as) general convention for integer-valued computations but something specific to integer division.
Regarding naming: I'm in favour of ilog2 because it's also an operation that would make sense to provide on floating-point numbers. Precedent: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogFloat
EDIT: Also C99 https://en.cppreference.com/w/c/numeric/math and C++11 https://en.cppreference.com/w/cpp/numeric/math apparently also have ilogb and logb.
Regarding naming: I'm fine with ilog2 or the much more explicit floor_log2/ceil_log2 like is used in the algebraics library I wrote.
@scottmcm On the other hand, floating-point numbers currently have powi and powf, while integers have pow not powi. So it would be consistent with that to have integer functions called log and floating-point functions called something else. (I'm just mentioning this for completeness, I haven't got a preference either way yet.)
There are no other functions like floor_func, and I think adding floor_log2 would stand out.
I think ilog2 would be a better name.
Regarding naming: I'm in favour of
ilog2because it's also an operation that would make sense to provide on floating-point numbers.
@scottmcm This was brought up before in the PR. Reiterating my reasoning here:
I think Integer::{log,log2,log10} have the right names since all other methods on integers aren't prefixed with i either. For example Integer::div isn't called Integer::idiv yet still performs "integer division" which yields different results than if the numbers were cast to floats and then divided.
I think @tspiteri correctly points out that there doesn't appear to be a precedent for float-based operations on integers in the stdlib. But there is a precedent for integer-based operations on floats, suffixed with i for integer and f for float (e.g. f32::{powi, powf}). Unless we would expect to expose float-based counterparts to the log methods on integers in the future it seems to me that Integer::{log,log2,log10} are the most compatible with the existing naming scheme since no other method on integers currently uses a suffix (e.g. u32::pow).
However if we think people might wonder what kind of log operation this is, we could perhaps spell out in the documentation that this is indeed "integer logarithm".
@yoshuawuyts Are there any other functions for integers and floats with the same name, but return different results?
@EdorianDark yes, as I mentioned in an earlier comment multiplication (mul) and division (div) work much the same way:
assert_eq!((5.0 / 2.0) * 2.0, 5.0); // {mul, div} for floats
assert_eq!((5 / 2) * 2, 4); // {mul, div} for ints
@yoshuawuyts Yes am aware that the operators behave differently. But as far as I know there are up till now no functions with the same name and a completely different result.
@EdorianDark The same statement I shared above could be written as:
use std::ops::{Div, Mul};
assert_eq!(5_u32.div(2).mul(2), 4); // {mul, div} for ints
assert_eq!(5_f32.div(2.0).mul(2.0), 5.0); // {mul, div} for floats
We can observe the same methods being called with the same inputs yielding different results because one operates on floats, and the other on ints. Integers and floats have inherently different behavior which means there are many other examples possible -- but the div/mul example is a simple way to convey this.
The overarching point I'm trying to make with this example is that Integer::{log,log2,log10} behave consistently with Integer::mul, Integer::div and other operations. Unless there are extenuating factors such as anticipating we also would like to expose float-based logarithm operations on integers (for which there is no precedent), these seem like the most obvious names.
The functions mul and div are the functions implementing the operators, so they have to have the same name because of the design of the operators.
Maybe lets looks at what other languages do for log on an integer:
- C++: integer is cast to double and then log is called
- C: integer is cast to double and then log is called
- Python: uses the C functions
- Javascript: had only floats for a long time. The recently introduced BigInt does not have log.
- Java: int is implicitly converted to double and then log called
- C#: int is implicitly converted to double and then log called
Is there any example to call the integer logarithm log?
The functions
mulanddivare the functions implementing the operators, so they have to have the same name because of the design of the operators.
@EdorianDark I'm glad we can agree these methods have the same names but behave differently. Similar examples could be written for non-trait based methods such as u32::div_euclid vs f32::div_euclid.
Maybe lets looks at what other languages do for log on an integer:
@EdorianDark I think this is something worth exploring (and we already have, but to a lesser extent), but in this context it feels like a moving of the goal posts. But sure, let's take a look:
- C++:
std::log(double arg) - C:
log(double arg)(imported from<math.h>) - Python:
math.log(x) - JavaScript:
Math.log(x) - Java:
Math.log(double a) - C#:
Math.Log(double d);
These methods are different from Rust in several ways:
- None are implemented as methods on number types, they're all standalone functions.
- They all implement float-based logarithm.
- Operating on integers generally [1] relies on implicit casting.
In contrast Rust has the benefit of clear module hierarchies, operations scoped to their number types, and no implicit casting. The examples would be more relevant if they exposed int logarithms or were methods on numbers. But so far what we're discussing in this thread seems quite different.
So far the only plausible reason for naming these methods anything other Integer::{log, log2, log10} I've seen, would be if we also expect to expose float-based log on ints. In that case the naming ought to be Integer::{logi, logf, logi2, logf2, logi10, logf10} to match the precedent set by f32::{powi, powf}. But that would introduce a lot of methods, and there should be a clear motivation for why we would want to expose both variants.
[1]: C++ shows IntegralType arg in the docs with the purpose to show that if integers are passed they will be cast to floats first.
For operators like * or / and with them the functions mul and div the expectation is, that they operate within the the types of their arguments.
The logarithm is a continuous function defined on all positive real numbers. The examples I listed show, that the expectation for log is to behave like the logarithm, mapping into floating point numbers. How the functions get to there is an implementation detail.
In Rust there is now the possibility to let log into integers, but why would someone expect that?
Is there any prior art for implementing log with as a inter logarithm and not as logarithm?
I'd argue for not using just log, log2, or log10 for integer logarithm because, even if we never intend to add int -> float logarithms, quite a few other common programming languages (C, C++, Python, Java, JavaScript, etc.) use just plain log[2|10] to mean the float form and quite a lot of people will assume that Rust's variants are the same float functions without checking the docs because they share the same names, leading to confusion.
Integer division doesn't really have the same naming issue as integer logarithm, since there are quite a few other programming languages where integer division uses the same operator as float division (C, C++, Java, etc.) so is much less of a learning obstacle.
The original PR was never merged, which means that this isn't tracking anything at the moment. Closing this for now.
The original PR was approved by the libs team, but when attempting to merge failed on bors. I've re-filed the PR in https://github.com/rust-lang/rust/pull/80918 which include a fix which should make the failing tests pass.
Apologies for not doing this sooner; going from src/libcore -> library/core midway through trying to fix the PR left me feeling overwhelmed and not sure how to proceed. I'm feeling a bit more confident poking at the stdlib now, hence the attempt to retry the PR (:
#86930 (special case for integer log10) has been merged, which uses a different strategy from https://github.com/rust-lang/rust/pull/70835#issuecomment-609976593. I did a quick benchmark for u32, and while the strategy of the comment was indeed faster than the non-special-cased original, the actually committed PR was faster still:
test u32_comment ... bench: 1,377 ns/iter (+/- 51)
test u32_86930 ... bench: 734 ns/iter (+/- 8)
test u32_original ... bench: 1,725 ns/iter (+/- 53)
This should complete the task about optimizing log10.
With regard to base 10, I've found that using the approach followed here is approximately 10% faster on u32 using a crude benchmark. Presumably this holds for larger integers, but the current approach is faster on u8 and u16.
pub const fn log10_u32_proposed(x: u32) -> u32 {
const TABLE: &[u64] = &[
0x0000_0000_0000,
0x0000_0000_0000,
0x0000_0000_0000,
0x0000_FFFF_FFF6,
0x0001_0000_0000,
0x0001_0000_0000,
0x0001_FFFF_FF9C,
0x0002_0000_0000,
0x0002_0000_0000,
0x0002_FFFF_FC18,
0x0003_0000_0000,
0x0003_0000_0000,
0x0003_0000_0000,
0x0003_FFFF_D8F0,
0x0004_0000_0000,
0x0004_0000_0000,
0x0004_FFFE_7960,
0x0005_0000_0000,
0x0005_0000_0000,
0x0005_FFF0_BDC0,
0x0006_0000_0000,
0x0006_0000_0000,
0x0006_0000_0000,
0x0006_FF67_6980,
0x0007_0000_0000,
0x0007_0000_0000,
0x0007_FA0A_1F00,
0x0008_0000_0000,
0x0008_0000_0000,
0x0008_C465_3600,
0x0009_0000_0000,
0x0009_0000_0000,
];
((x as u64 + TABLE[31 - x.leading_zeros() as usize]) >> 32) as _
}
Happy to provide similar lookup tables for other integer types if desired.
I always find it hard to judge table lookups. In microbenchmarks they often look great since cache pressure isn't a concern.
Of course cache is huge for something like that. Just throwing it out there; it's plenty fast either way.
Currently, the return type for T::{log,log2,log10} is T (https://doc.rust-lang.org/nightly/std/primitive.u128.html#method.log2). Since the return value is at most 128, this is inefficient for at least u128. Methods such as T::{leading_zeros,count_ones} always return u32. I would suggest to also always return u32 here, making the API also more consistent.
I've just seen that in my code u32::log10 isn't inlined (in optimized builds), I don't know if this is OK:
mov r15, qword ptr [rip + core::num::int_log10::u32@GOTPCREL]
...
call r15