[I] arrow-buffer: implement log for i256 [arrow-rs]

["theirix (via GitHub)" <gi...@apache.org>]

theirix opened a new issue, #9452:
URL: https://github.com/apache/arrow-rs/issues/9452

   **Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
   <!--
   A clear and concise description of what the problem is. Ex. I'm always frustrated when [...] 
   (This section helps Arrow developers understand the context and *why* for this feature, in addition to  the *what*)
   -->
   
   **Describe the solution you'd like**
   
   i256 doesn't implement ilog/ilog2/ilog10 while other numeric types (standard integers and a wide type `u128` ) do.
   Example: https://doc.rust-lang.org/nightly/core/primitive.u128.html#method.ilog
   
   **Describe alternatives you've considered**
   <!--
   A clear and concise description of any alternative solutions or features you've considered.
   -->
   
   **Additional context**
   
   
   Follow-up to #8976 
   


-- 
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: github-unsubscribe@arrow.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [I] arrow-buffer: implement log for i256 [arrow-rs]

["Whatsonyourmind (via GitHub)" <gi...@apache.org>]

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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [I] arrow-buffer: implement log for i256 [arrow-rs]

["theirix (via GitHub)" <gi...@apache.org>]

theirix commented on issue #9452:
URL: https://github.com/apache/arrow-rs/issues/9452#issuecomment-3937187785

   take


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [I] arrow-buffer: implement log for i256 [arrow-rs]

["alamb (via GitHub)" <gi...@apache.org>]

alamb closed issue #9452: arrow-buffer: implement log for i256
URL: https://github.com/apache/arrow-rs/issues/9452


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org