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

[EdorianDark]

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

[yoshuawuyts]

@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

playground

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.

[tesuji]

What about voting for the name in internals.rust-lang.org/ ?

[EdorianDark]

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?

[yoshuawuyts]

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.

@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:

1. None are implemented as methods on number types, they're all standalone functions.
2. They all implement float-based logarithm.
3. 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.

[EdorianDark]

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?

[programmerjake]

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.

[programmerjake]

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.

[m-ou-se]

The original PR was never merged, which means that this isn't tracking anything at the moment. Closing this for now.

[yoshuawuyts]

The original PR was approved by the libs team, but when attempting to merge failed on bors. I've re-filed the PR in #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 (:

[tspiteri]

@m-ou-se Should this be reopened now that #80918 has been merged?

[yoshuawuyts]

@rust-lang/libs-api can we start an FCP on this? There are no blocking concerns; all we're missing is one more checkmark from a libs-api team member on #70887 (comment). Thanks!

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

[blueglyph]

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.

@jhpratt, it was interesting to see your comment.

For information, I wasn't aware of this discussion. I needed a fast log10(u64) function for a project and I decided to make a small crate to share it, extending it to a method for all integer primitives (ilog). It happens to use the (initial) algorithm you mentioned, that I already knew and which is indeed fast.

Little clarifications:

• the functions are named log10 and log2, initially because the name was more natural and I didn't see any conflict, but also because I was aware of experimental ilog10 and ilog2 methods in 1.65
• I developed it a few days ago in 1.65, and only later when testing it with 1.64 did I see a warning about potential future name conflicts, which lead me to this discussion. Those log* methods of 1.64 were renamed to ilog* in 1.65. So I don't think there should be any conflict with these methods.

Feel free to use the code if you like, but I understand from earlier comments that the algorithm with corrective tables is not desired.