Feature request: BigInteger.getBits

[danwallach]

Right now, there are primitive methods to get and set individual bits. It would be handy for my use case (accelerating modular exponentiation for bases that are frequently reused, like a generator) to be able to fetch multiple bits at once.

While a general purpose version of this would be equivalent to shifting right, masking, and returning another BigInteger, the algorithm I'm using only needs to digest somewhere between 8 and 16 bits at a time, so an API that returns a ULong or UInt would be perfect.

I could take a swing at building this for you, if you want, but I thought I'd see what you think about the idea first.

(I'm porting some code from Python that takes advantage of Gmpy's xmpz type, which has an operation equivalent to the getBits that I'm requesting. This particular acceleration is worth 10x performance with 4000 bit numbers.)

[gciatto]

I totally agree on implementing these methods and I would be glad to accept PR on this.

My only concern is about the unsigned integer types: as long as they require the @OptIn annotation, I'd rather not to include them the public API of kt-math.

Can you propose an implementation which does not require unsigned integer types?

[danwallach]

I guess we could have variants, like getIntBits and getLongBits which will max out at 31 or 63 bits, respectively? There are other performance issues going on here, but I'll make a separate issue for that.

[gciatto]

Yes, overloads may be definitely an option.
After I see how you plan to implement these methods I can perhaps say something intelligent about optimizations.

BTW, BigInteger uses int arrays behind the scenes, so my guess is that working with Ints may be the most efficient way.