Implement log(10)

[meltinglava]

I have thought of 2 cases here. one is to know the len (size) of the base 10 output and second is for the 10^n written way of writeing numbers. might want base of e as well.

[cuviper]

I think I'd like to approach this as we have for sqrt etc. -- first with a new trait in num-integer, then implement it here. A trait Log or Logs could have fn log2(&self) -> u32 which is trivial, and fn log10 is also straightforward with http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10.

I'm not sure about natural log (base e) though. Is it useful to have a truncated ln like this? If you want the float value, it's probably easier to just convert your integer to a float and call ln().

[meltinglava]

I would say that there should be some discussion if we should floor or round this to closest int. On the one side floor will always give the len of the printed value, thow could be far mathematicly value.

I agree with the ln case as i cant see a use case for it.

[cuviper]

It seems to me that rounded log2 and log10 are similar to ln -- I'm not sure they're useful. But as a possible approach to implement these:

Given n = ⌊log2(x)⌋, we want to round up if x ≥ 2^(n + 0.5). That's x ≥ 2^((2n+1)/2), or x ≥ √(2^(2n+1)). We have Roots::sqrt, so we can implement this comparison if we're also careful about sqrt's trucation. (Overflow before the sqrt is also a problem for bounded integer types.) It's similar for log10, just changed to base 10, of course.

edit: Oh, we don't even need sqrt -- just check x² ≥ 2^(2n+1), which is also ⌊log2(x²)⌋ ≥ 2n+1.

[meltinglava]

I say we implement log10 rounded down, and leave room for future log_closest or something if it is needed. Think log10 is only one that is a candidate to be rounded to closest.

[cmpute]

I think a general log function with be pretty useful, 10 is just a special case for that.

[cmpute]

I just noticed that rust officially introduced log, log2, log10 for integer types, I think it will be great if similar API for bigint could be introduced.

[zeddash]

I need log10 as a way to get the length of the number, what's the alternative just loop through? log10 is absolutely useful for general programming just not particularly useful for actual maths

Also log10 needs to be rounded down, not to nearest as again it's not useful for maths but if it were to be rounded to nearest it would be unusuable

[cmpute]

I need log10 as a way to get the length of the number, what's the alternative just loop through? log10 is absolutely useful for general programming just not particularly useful for actual maths

Also log10 needs to be rounded down, not to nearest as again it's not useful for maths but if it were to be rounded to nearest it would be unusuable

FYI, this function is implemented in the dashu library: https://docs.rs/dashu/0.4.2/dashu/integer/struct.IBig.html, https://docs.rs/dashu/0.4.2/dashu/float/struct.Repr.html#method.digits

It's also easy to approximate log10 with log2 implementations if you don't need exact logarithm

[janmarthedal]

I think I'd like to approach this as we have for sqrt etc. -- first with a new trait in num-integer, then implement it here. A trait Log or Logs could have fn log2(&self) -> u32 which is trivial, and fn log10 is also straightforward with http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10.

Yes, I agree on this approach. How about calling the trait ILog to emphasize that they are integer/truncated logarithms?

[janmarthedal]

I am currently working on a PR for ilog, ilog2, ilog10 (and checked versions of those).

Since the method BigUint::bits returns a u64 it would make sense to use fn ilog2(self) -> u64 for BigUint's implementation. Rust's method signature for primitive ints is fn ilog2(self) -> u32, however. How should we deal with this?

[cuviper]

Since the method BigUint::bits returns a u64 it would make sense to use fn ilog2(self) -> u64 for BigUint's implementation. Rust's method signature for primitive ints is fn ilog2(self) -> u32, however. How should we deal with this?

It's an annoying possibility, but 2³² bits of a BigUint is only 512 MiB -- unwieldy, but definitely feasible even on 32-bit targets. So we should either use u64 everywhere, or we could make this an associated type, something like:

pub trait ILog {
    type Bits: Integer + Unsigned;
    ...
}

The advantage of an associated type is that it could even support exotic types with arbitrary bit sizes. For example, in my Project Euler solutions I have a bespoke SparseUint that only stores non-zero limbs, so it can store values that BigUint couldn't deal with due to memory limitations. For this, I would probably want type Bits = BigUint.

[cbeck88]

I got here because, I needed to take the log10 of a BigDecimal. I need to be able to do this to check when the numbers in a limited-precision system are getting too close to the configured precision limits and issue a warning before there is a problem.

• BigDecimal doesn't have log10, but I can split that into a BigInt and a scale which would be enough.
• BigUint and BigInt don't have it either unfortunately.

Instead what I did was, I used ToPrimitive::to_f64 and then used f64::log10 from the standard library.

It feels a bit lame though. Intuitively, it should be a lot easier to compute an accurate log10 from a BigDecimal than it would be from an f64, but I couldn't see an easy pre-existing way to actually do it and didn't have time to build it.