Whatsonyourmind commented on issue #9452:
URL: https://github.com/apache/arrow-rs/issues/9452#issuecomment-4182732993
For implementing `ilog`, `ilog2`, and `ilog10` on i256, here are the
efficient approaches:
**ilog2**: This is the simplest -- it's just the position of the highest set
bit minus 1. Since i256 is stored as `[u128; 2]` (or similar), check the high
limb first:
```rust
fn ilog2(self) -> u32 {
assert!(self > Self::ZERO, "logarithm of non-positive value");
if self.high() > 0 {
128 + self.high().ilog2() // delegate to u128::ilog2
} else {
self.low().ilog2()
}
}
```
**ilog10**: The standard approach uses the relationship `ilog10(x) =
ilog2(x) * log10(2)` as an initial estimate, then refines. Since `log10(2) ≈
0.30103`, we can use integer arithmetic:
```rust
fn ilog10(self) -> u32 {
assert!(self > Self::ZERO);
// Initial estimate: floor(ilog2(x) * log10(2))
// Use rational approximation: 30103/100000 ≈ log10(2)
let bit_len = self.ilog2();
let mut estimate = (bit_len as u64 * 30103) / 100000;
// The estimate may be off by 1, so verify and correct
let power = pow10_i256(estimate as u32);
if self >= pow10_i256(estimate as u32 + 1) {
estimate += 1;
}
estimate as u32
}
```
You'll need a `pow10_i256` helper. Since `10^77 < 2^256 < 10^78`, you only
need a lookup table of at most 78 entries, or compute via repeated squaring.
**ilog (general base)**: Use the change-of-base identity: `ilog_b(x) =
ilog2(x) / ilog2(b)` as initial estimate, then correct by comparing against
`b^estimate` and `b^(estimate+1)`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
