Rust: Tracking Issue for Integer::{log,log2,log10}

[yoshuawuyts]

This is a tracking issue for the Integer::{log,log2,log10} methods.
The feature gate for the issue is #![feature(int_log)].

Steps

• [ ] Adjust documentation (see instructions on rustc-dev-guide)
• [ ] Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

• [ ] Can we further optimize the log10 implementation? https://github.com/rust-lang/rust/pull/70835#issuecomment-609976593
• [ ] Can we make these methods const fn?
• [ ] Can we implement these types for NonZero{Int}? https://github.com/rust-lang/rust/pull/70835#issuecomment-611336828
  
  
  
  • [ ] Can we omit returning Option for log2/log10 on NonZero{Int}?
  
  
• [ ] Should the methods be called Integer::{logi,logi2,logi10} instead? https://github.com/rust-lang/rust/pull/70835#issuecomment-611998098 https://github.com/rust-lang/rust/issues/70887#issuecomment-616580640

Implementation history

• Initial implementation in https://github.com/rust-lang/rust/pull/70835

[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 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);

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

[lzutao]

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.

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