Make BigInteger bit shift and power methods compatible with BigInteger values

[JansthcirlU]

Background and Motivation

The BigInteger struct is very useful to perform arithmetic operations beyond the traditional int and long ranges, but I've noticed that the bitwise shift and integer power methods do not accept a BigInteger value, which seems rather inconsistent. The strength of the struct lies in its boundlessness, so restricting bit shifts and powers of BigInteger values to just integers seems to be a missed opportunity.

Proposed API

public readonly struct BigInteger : ...
{
    ...
    public static BigInteger operator <<(BigInteger value, BigInteger shift) { ... }
    public static BigInteger operator >>(BigInteger value, BigInteger shift) { ... }
    public static BigInteger Pow(BigInteger value, BigInteger exponent) { ... }
    ...
}

Usage Examples

// Example big integers used in a project centred around big integers
BigInteger bigThree = new BigInteger(3);
BigInteger bigFour = new BigInteger(4);
BigInteger bigOneHundredAndTwelve = new BigInteger(112);

// Bitwise shift by a big integer
BigInteger bigFortyEight = bigThree << bigFour; // == 48, equal to 3 << 4
BigInteger bigSeven = bigOneHundredAndTwelve >> bigFour; // == 7, equal to 112 >> 4

// Big integer raised to a big integer power
BigInteger bigSixtyFour = BigInteger.Power(bigFour, bigThree); // == 64, equal to 4³

Alternative Designs

I'm personally not familiar enough with bit manipulation to propose an implementation, let alone alternative designs to make my suggestion work. I figured it could be useful to open an issue regardless, to discuss the feasibility of this suggestion.

Risks

Since this suggestion would meddle with bitwise operations, I can imagine memory management would get rather messy very quickly. Although it's theoretically already possible to create unwieldy BigInteger values with just the int based methods, manipulating the BigInteger's nitty gritty directly seems more error-prone.

[ghost]

Tagging subscribers to this area: @tannergooding, @pgovind
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and Motivation

The BigInteger struct is very useful to perform arithmetic operations beyond the traditional int and long ranges, but I've noticed that the bitwise shift and integer power methods do not accept a BigInteger value, which seems rather inconsistent. The strength of the struct lies in its boundlessness, so restricting bit shifts and powers of BigInteger values to just integers seems to be a missed opportunity.

Proposed API

public readonly struct BigInteger : ...
{
    ...
    public static BigInteger operator <<(BigInteger value, BigInteger shift) { ... }
    public static BigInteger operator >>(BigInteger value, BigInteger shift) { ... }
    public static BigInteger Pow(BigInteger value, BigInteger exponent) { ... }
    ...
}

Usage Examples

// Example big integers used in a project centred around big integers
BigInteger bigThree = new BigInteger(3);
BigInteger bigFour = new BigInteger(4);
BigInteger bigOneHundredAndTwelve = new BigInteger(112);

// Bitwise shift by a big integer
BigInteger bigFortyEight = bigThree << bigFour; // == 48, equal to 3 << 4
BigInteger bigSeven = bigOneHundredAndTwelve >> bigFour; // == 7, equal to 112 >> 4

// Big integer raised to a big integer power
BigInteger bigSixtyFour = BigInteger.Power(bigFour, bigThree); // == 64, equal to 4³

Alternative Designs

I'm personally not familiar enough with bit manipulation to propose an implementation, let alone alternative designs to make my suggestion work. I figured it could be useful to open an issue regardless, to discuss the feasibility of this suggestion.

Risks

Since this suggestion would meddle with bitwise operations, I can imagine memory management would get rather messy very quickly. Although it's theoretically already possible to create unwieldy BigInteger values with just the int based methods, manipulating the BigInteger's nitty gritty directly seems more error-prone.

Author:	JansthcirlU
Assignees:	-
Labels:	api-suggestion, area-System.Numerics, untriaged
Milestone:	-

[stephentoub]

but I've noticed that the bitwise shift and integer power methods do not accept a BigInteger value, which seems rather inconsistent

Can you share your scenario in which you need to shift by more than two billion bits?

[john-h-k]

This is actually impossible, lol. The rhs of a shift operator overload must be int

[tannergooding]

I don't think there is a scenario where we need to represent a value larger than 2^2147483647 (and in fact, .NET won't let us because of memory/size limitations of arrays😄).

Likewise, C# requires the RHS of a user-defined shift operator to be int. It can't be uint, long, ulong, nint, or nuint.
That being said, there is benefit to allowing the RHS to be one of these other values in that it can simplify the overall algorithm.

It is not uncommon, for example, to have 1u << (uint arithmetic), particularly with certain interop or performance oriented code. The resulting shift is still, ultimately, between 0-31 (or 0-63 for long/ulong, or 0-bound for larger types) and so is well-defined by C#, the language simply disallows it and requires you to insert a needless cast to int: 1u << (int)(uint arithmetic).

The same could be said for BigInteger. That is, you may have done some complex set of calculations and what you ultimately have is a positive integer that is far less than 2 billion and is therefore "in range", but due to limitations of the language you are forced to downcast to int before doing the shift.

There are proposals such as dotnet/csharplang#4431 that discuss expanding the C# limitations here and I recently raised it to Mads as part of the static abstracts in interfaces work; particularly as IL and other languages do not have this limitation.

[JansthcirlU]

I agree that representing a number greater than 2^2147483647 will pretty much never be required, but I was more concerned with the consistency of the struct, because all other operators and methods do allow BigInteger values.

I wasn't aware that bit shifts only worked with integer values, that was poor research on my part. Should I close this issue and create a new one just for the the BigInteger.Power(BigInteger, BigInteger) suggestion?

[tannergooding]

Closing this as unactionable unless the language takes dotnet/csharplang#4666

If the language does add support, we should be able to reopen and consider this.