Runtime: Add API to get bit length of BigInteger

[andrew-boyarshin]

Gets the number of bits required for shortest two's complement representation of a BigInteger instance without the sign bit.

The method returns the minimum non-negative number of bits in two's complement notation without the sign bit.

This method returns 0 _iff_ value of the BigInteger instance is equal to 0 or -1. For positive integers the return value is equal to the ordinary binary representation string length.

Java docs for equivalent method

Implementation implies zero impact on existing code, maintenance cost is expected to be low.

Current story

private static long SlowBitLength(BigInteger integer)
{
    return (long)Math.Ceiling(BigInteger.Log(integer.Sign < 0 ? -integer : integer + 1, 2.0));
}

• Slower
• Imprecise for huge (2^(32*int.MaxValue)) values (correct ± 1)

Proposed API

public struct BigInteger : <...>
{
    <...>
    public long GetBitLength();
    <...>
}

Sample results

Open Questions

• Should it be property, or method? It implies some computation, so it's cheap, not free. IsPowerOfTwo is a property and has approximately the same complexity. — Chosen method approach.

References

dotnet/runtime#29193 contains a similar method as one of the points, however this method is different.

Changelog

• [2019-11-02] Rewritten as method (was property initially).
• [2020-06-15] Fixed description to take two's complement representation as the basis.

[andrew-boyarshin]

@tannergooding It would be great to receive at least some initial feedback and "api-proposal" issue tag.

[tannergooding]

I think the premise, in general, is fine. Given that it isn't trivial to compute, it might be better to have it be called GetBitLength

[andrew-boyarshin]

Yeah, sounds reasonable. Updated API proposal:

public readonly struct BigInteger : <...>
{
    <...>
    public int GetBitLength();
    <...>
}

One more concern is int vs uint. From runtime perspective it is better to use uint to better express the semantics and make JIT more informed. Downside of it is that unsigned integer types have very sparse API coverage in CoreFX (even arrays have only signed indexers) due to them being non CLS-compliant. Despite me wishing to make this unsigned for JIT' sake, I still believe we should go with signed return type.

What's the next step for this proposal? Owner assignment? Cc'ing additional reviewers?

[tannergooding]

The next step is marking it api-ready-for-review (which I'll do after giving this a period for others to comment) and then reviewing it as part of the API review backlog.

API review typically happens once per week on Tuesday between 10 and noon Seattle Time. We don't review the backlog every Tuesday as sometimes there are dedicated review sessions for other APIs (such as the ARM Hardware Intrinsics, which we did this last Tuesday).

We also typically review the API backlog from oldest to newest.

[andrew-boyarshin]

@tannergooding sadly, System.Numerics is the unattractive area of .NET Libraries. Hardly anyone watches progress here (apart from .NET Team of course). Maybe it's time to mark this as api-ready-for-review? This way it will certainly gain at least some feedback.

[andrew-boyarshin]

@tannergooding it might be a great time to mark this as api-ready-for-review, otherwise it'll never be looked at.

[terrajobst]

Video

• Makes sense as proposed
• We considered GetBitCount() to be consistent with GetByteLength() but it seems confusing because it sounds like GetPopCount().

C# namespace System.Numerics { public struct BigInteger { public int GetBitLength(); } }

[andrew-boyarshin]

Turns out BigInteger is inconsistent with bit length being int or long. Correct return type is long (see #15925, yeah, it really can overflow!). @tannergooding @terrajobst does this change require additional API review?

[tannergooding]

It will need to get sign-off at a minimum. Given that we currently use int as the backing type, you only need an array that is 67 million elements before BitLength risks overflowing, so using long makes sense to me.

I'd suggest prepping the PR assuming that long is fine and I'll get sign-off either offline or in Tuesday's API review. CC @dotnet/fxdc

[stephentoub]

long makes sense

[andrew-boyarshin]

For API re-review:

1. long instead of int as the return type
2. Bit length is that of the two's-complement representation. This detail was discovered when testing against Java's BigInteger and thanks to @KalleOlaviNiemitalo. The only difference (w.r.t. the approved API proposal) is for negative power-of-2 numbers.

[tannergooding]

Brought this up first thing this morning and it was approved. I've unblocked the associated PR.