Tracking Issue for Integer::{ilog,ilog2,ilog10}

[yoshuawuyts]

Feature gate: #![feature(int_log)]
Stabilization report: #70887 (comment)

---

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 #80918 (comment). 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

• Implementation: Add Integer::log variants #80918
• Stabilization report Tracking Issue for Integer::{ilog,ilog2,ilog10} #70887 (comment)
• Final comment period (FCP)

Unresolved Questions

• Can we further optimize the ilog10 implementation? Add Integer::checked_{log,log2,log10} #70835 (comment)
• Can we make these methods const fn?
• Can we implement these types for NonZero{Int}? Add Integer::checked_{log,log2,log10} #70835 (comment)
  • Can we omit returning Option for ilog2/ilog10 on NonZero{Int}?
• Should the methods be called Integer::{ilog,ilog2,ilog10} instead? Add Integer::checked_{log,log2,log10} #70835 (comment) Tracking Issue for Integer::{ilog,ilog2,ilog10} #70887 (comment)

Implementation History

• Add Integer::checked_{log,log2,log10} #70835 - initial PR, closed due to inactivity
• Add Integer::log variants #80918 - attempt 2 to implement log methods, merged
• Add log2 and log10 to NonZeroU* #92956 - log methods for NonZero types
• Rename integer log* methods to ilog* #100332 - rename log methods to ilog
• Panic for invalid arguments of {integer primitive}::ilog{,2,10} in all modes #102578 - panic on invalid args

[leonardo-m]

Having those as const fn is going to be useful to initialize constants, etc.

[hanna-kruppe]

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.

[yoshuawuyts]

@hanna-kruppe This was brought up before, and was addressed in #70835 (comment):

(...) 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);

playground

The ecosystem contains extensions for e.g. integer::div_ceil which would round the value up. However these are not part of std, and if they were introduced they would likely use a _ceil suffix as well.

---

Does this make sense, or do you feel there is still missing something?

[hanna-kruppe]

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.

[scottmcm]

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.

[programmerjake]

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.

[tspiteri]

@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.)

[EdorianDark]

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.

[yoshuawuyts]

Regarding naming: I'm in favour of ilog2 because 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".

[EdorianDark]

@yoshuawuyts Are there any other functions for integers and floats with the same name, but return different results?

[yoshuawuyts]

@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

playground