Expose a BigInteger.Builder to help avoid so many copies/allocations

[tannergooding]

Rationale

System.Numerics.BigInteger is an immutable struct that frequently works with "big data". This can cause it to be very ineffecient to use given that you need to create a new immutable struct for every operation. As such, I propose we expose a new BigInteger.Builder type which allows for multiple operations to be performed on a mutable class before ultimately serializing the final result back to a regular BigInteger. This pattern has been used to good affect in other types, such as those in System.Collections.Immutable.

Proposed API

namespace System.Numerics
{
    public partial struct BigInteger
    {
        // Should there be a CreateBuilder method which takes an initial capacity?

        public static Builder CreateBuilder();
        public static Builder CreateBuilder(byte[] value);
        public static Builder CreateBuilder(decimal value);
        public static Builder CreateBuilder(double value);
        public static Builder CreateBuilder(int value);
        public static Builder CreateBuilder(long value);
        public static Builder CreateBuilder(float value);
        public static Builder CreateBuilder(uint value);
        public static Builder CreateBuilder(ulong value);
        public static Builder CreateBuilder(BigInteger value);

        public sealed class Builder : IFormattable, IComparable, IComparable<BigInteger.Builder>, IEquatable<BigInteger.Builder>
        {
            // Already in BigInteger

                public bool IsEven { get; }
                public bool IsOne { get; }
                public bool IsPowerOfTwo { get; }
                public bool IsZero { get; }

                public int Sign { get; }

                public static Builder Abs(Builder value);
                public static Builder Add(Builder left, Builder right);
                public static int Compare(Builder left, Builder right);
                public static Builder Divide(Builder dividend, Builder divisor);
                public static Builder DivRem(Builder dividend, Builder divisor, out Builder remainder);
                public static Builder GreatestCommonDivisor(Builder left, Builder right);
                public static Builder Log(Builder value);
                public static double Log(Builder value, double baseValue);
                public static Builder Log10(Builder value);
                public static Builder Max(Builder left, Builder right);
                public static Builder Min(Builder left, Builder right);
                public static Builder ModPow(Builder value, Builder exponent, Builder modulus);
                public static Builder Multiply(Builder left, Builder right);
                public static Builder Negate(Builder value);
                public static Builder Pow(Builder value, int exponent);
                public static Builder Remainder(Builder dividend, Builder divisor);
                public static Builder Subtract(Builder value, int shift);

                public int CompareTo(Builder other);
                public override Equals(object other);
                public bool Equals(Builder other);
                public int GetByteCount(bool isUnsigned = false);
                public override int GetHashCode();
                public byte[] ToByteArray(bool isUnsigned = false, bool isBigEndian = false);
                public override string ToString();

            // Not listed

                // All the operators, including:
                //   * Explicit Casts
                //   * Implicit Casts
                //   * Comparison (>, >=, <, <=, ==, !=)

                // Parse methods

            // Not in BigInteger

                public static Builder BitwiseAnd(Builder left, Builder right);
                public static Builder BitwiseOr(Builder left, Builder right);
                public static Builder Decrement(Builder value);
                public static Builder Increment(Builder value);
                public static Builder LeftShift(Builder value, int shift);
                public static Builder Modulus(Builder dividend, Builder divisor);
                public static Builder OnesComplement(Builder value);
                public static Builder RightShift(Builder value, int shift);
                public static Builder Xor(Builder left, Builder right);

                public BigInteger ToBigInteger();
        }
    }
}

Open Questions

How should the builder handle taking an existing BigInteger as an input? We don't want to force creation of a Builder as that could copy unecessarily.

Should the Builder be a class, as other builders have been. What about a ref struct which might help with lifetime and allow usage of the stack, rather than force array allocations...

Should the APIs be exposed in a more "builder" oriented manner (instance methods that return 'self')?

[svick]

How do the binary operations behave? Is the return value guaranteed to be the same instance as the first operand? Or should both operands be considered invalid after those operations? Either way, I think it's going to be unintuitive and instance methods would make the mutations much clearer.

What is the expected usage pattern? Just the method name thanks to using static? (I think that e.g. BigInteger.Abs is mostly reasonable, but BigInteger.Builder.Abs is quite verbose.)

Maybe an example would help. Consider the following variation of computing an arithmetic series:

BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d) =>
    (2 * a1 + (n - 1) * d) * n / 2;

How would you do the same thing using BigInteger.Builder?

How should the builder handle taking an existing BigInteger as an input? We don't want to force creation of a Builder as that could copy unnecessarily.

Maybe it doesn't have to copy, if you use copy-on-write? When you create a Builder from BigInteger, it reuses its backing array and remembers that it's not allowed to mutate it. When a mutation is performed on that Builder, then it will allocate its own array.

[tannergooding]

How do the binary operations behave? Is the return value guaranteed to be the same instance as the first operand? Or should both operands be considered invalid after those operations? Either way, I think it's going to be unintuitive and instance methods would make the mutations much clearer.

Right, this is why I called out that the APIs should possibly be exposed in a more "builder" oriented manner... Essentially, we will need to either:

• Have a fluent design with instance methods (can't really use operators)
• Have a design where the user can explicitly specify the destination builder. This could potentially be returned as the result as well, but we can't really utilize operators
• Have a "RMW" design where the left operand is also the destination (potentially confusing design, also potentially inefficient when the user has an ultimate destination but multiple sub-operations)

Maybe it doesn't have to copy, if you use copy-on-write?

That might work, could probably do this fairly easily as well....

[verelpode]

I'll write my full comments when I get a chance, but for now, here's a design that is worthwhile to consider:

class Builder
{
    public void Multiply(Builder left, Builder right);
}

Yes, although it may seem surprising, that is indeed a non-static method and I intentionally wrote "void" return type. The result of the multiplication is stored into this, the same instance. In the following example, the result of the multiplication is stored into "r".

Builder x = new Builder(123456);
Builder y = new Builder(50000);
Builder r = new Builder();
r.Multiply(x, y);

I'm not saying this is the one true way, rather I'm saying, at least consider this design, even if it initially seems different than what you're traditionally accustomed to. Sometimes an idea seems unlikeable at first because it different to an old habit, but after you get used to it, you might end up liking it and discovering that it has advantages, even if it seemed strange at first.

[svick]

@verelpode

With that design, would you be allowed to write r.Multiply(r, x); (effectively r *= x;)? Or even r.Multiply(r, r);?

[verelpode]

@svick Good question. Yes, in my opinion, it should be written not to malfunction nor throw exception when any of r, x, y is the same instance as any of r, x, y, otherwise the reliability would be unsatisfactory. I've done some work in this area and my experience was that this ability is easy enough to support, if you implement it by simply loading the operand fields into local variables and then work with the local variables instead of the operand fields directly. As simple as this:

public void Multiply(Builder inOperandA, Builder inOperandB)
{
    uint[] a_bits = inOperandA._bits;
    uint[] b_bits = inOperandB._bits;
    int a_sign = inOperandA._sign;
    int b_sign = inOperandB._sign;
    ...
}

As a pleasing side-effect, this use of local variables also tends to help the compiler (or CIL-to-x64 compiler) optimize the generated code. Sometimes it also reduces the amount of additional work necessary to make something thread-safe.

[verelpode]

Maybe an example would help. Consider the following variation of computing an arithmetic series: BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d) => (2 a1 + (n - 1) d) * n / 2; How would you do the same thing using BigInteger.Builder?

I agree, this example certainly helps. If the design is as I proposed, then the following demonstrates an optimized implementation of the above expression.

BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d)
{
    var r = new BigInteger.Builder();
    r.Multiply(2, a1);   // r = 2 * a1;

    var t = new BigInteger.Builder();
    t.SubtractOne(n);    // t = n - 1;
    t.Multiply(t, d);    // t = t * d;
    r.Add(r, t);         // r = r + t;

    r.Multiply(r, n);    // r = r * n;
    r.Divide(r, 2);      // r = r / 2;
    return r.ToBigInteger();
}

In addition to having Builder.Multiply(BigInteger, BigInteger), consider also having MultiplyBy and DivideBy methods that are simply one-liner shortcuts that invoke Multiply or Divide. Thus the above example would be simplified to:

BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d)
{
    var r = new BigInteger.Builder();
    r.Multiply(2, a1);   // r = 2 * a1;

    var t = new BigInteger.Builder();
    t.SubtractOne(n);    // t = n - 1;
    t.MultiplyBy(d);     // t *= d;
    r.AddWith(t);        // r += t;

    r.MultiplyBy(n);     // r *= n;
    r.DivideBy(2);       // r /= 2;
    return r.ToBigInteger();
}

class Builder
{
    public void Add(BigInteger operandA, BigInteger operandB) { ... }
    public void Multiply(BigInteger operandA, BigInteger operandB) { ... }
    public void Divide(BigInteger operandA, BigInteger operandB) { ... }

    public void AddWith(BigInteger operand)
    {
        this.Add(this, operand);
    }

    public void MultiplyBy(BigInteger operand)
    {
        this.Multiply(this, operand);
    }

    public void DivideBy(BigInteger operand)
    {
        this.Divide(this, operand);
    }
}

[verelpode]

If the design is as I said except now with the idea of making each method finish with return this;, then ArithmeticSeries could be written as:

BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d)
{
    var r = BigInteger.Builder.New(2).MultiplyBy(a1);
    r.AddWith( BigInteger.Builder.New(n).Decrement().MultiplyBy(d) );
    return r.MultiplyBy(n).DivideBy(2).ToBigInteger();
}

Or if you really want to write it all on a single line, then the following is also valid, although not necessarily better in terms of code readability/maintainability.

BigInteger ArithmeticSeries(BigInteger n, BigInteger a1, BigInteger d)
{
    return BigInteger.Builder.New(2).MultiplyBy(a1).AddWith( BigInteger.Builder.New(n).Decrement().MultiplyBy(d) ).MultiplyBy(n).DivideBy(2).ToBigInteger();
}

[Clockwork-Muse]

@verelpode -

I've done some work in this area and my experience was that this ability is easy enough to support, if you implement it by simply loading the operand fields into local variables and then work with the local variables instead of the operand fields directly. As simple as this:

Doing something like that would require a copy of the underlying data, since copying the pointer wouldn't have a material effect on the outcome. Now, you would only have to copy in the case that the operands were the same, and I'd actually only copy the "result" operand (and set it at the end of the operation), since that's the only one that would be modified.

Sometimes it also reduces the amount of additional work necessary to make something thread-safe.

Builders are almost never thread-safe, nor do most usecases warrant that. The main problem is the fact that interleaving calls to a mutable piece of data is inherently dangerous, even if the internal representation doesn't tear or otherwise protects itself from corruption.

If the design is as I said except now with the idea of making each method finish with return this...

At this point (and I would personally prefer a this-returning type), do we really have a Builder, as opposed to a MutableBigInteger?

[svick]

@verelpode

I like the example in your last post: it looks fairly close to the original expression (which makes it easier to understand) and it has only one mutable variable, which I think makes it easier to write the code correctly (because you're unlikely to mutate the wrong variable).

Though I note that you're exclusively using the By versions of operations. And if you limit yourself to just those, I think your proposal is effectively the same as the original proposal from @tannergooding, except with instance methods, as suggested in the last open question.

@Clockwork-Muse

At this point (and I would personally prefer a this-returning type), do we really have a Builder, as opposed to a MutableBigInteger?

StringBuilder uses that approach, so it would not be unprecedented to call such type a Builder. Though e.g. ImmutableList<T>.Builder does not.

[verelpode]

@Clockwork-Muse

Doing something like that would require a copy of the underlying data, since copying the pointer wouldn't have a material effect on the outcome. Now, you would only have to copy in the case that the operands were the same

No, that's incorrect or inaccurate or "not necessarily true", depending on the precise implementation details. For example, have a look at the preexisting source code of System.Numerics.BigIntegerBuilder.Mul. Here's the start of it:

// Multiply reg1 times reg2, putting the result in 'this'. This version never shares memory
// with either of the operands. This is useful when performing a series of arithmetic operations
// and large working buffers are allocated up front.
public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) {

Builders are almost never thread-safe,

I didn't say that loading fields into local variables make things thread-safe, rather I said that it's a step in the direction of thread safety -- it tends to reduce the amount of additional work necessary to make something thread-safe.

[verelpode]

@svick

if you limit yourself to just those, I think your proposal is effectively the same as the original proposal from @tannergooding, except with instance methods, as suggested in the last open question.

True, @tannergooding may well have already thought of practically the same thing. Nevertheless I think it was still useful to work through your ArithmeticSeries example and explain in more detail, in order to decide the best way to go.

[Clockwork-Muse]

@verelpode -

No, that's incorrect or inaccurate or "not necessarily true", depending on the precise implementation details. For example, have a look at the preexisting source code of System.Numerics.BigIntegerBuilder.Mul. Here's the start of it:

I was speaking about attempting to use the this object as either of the operands, I should have been a little clearer.

[verelpode]

@Clockwork-Muse OK, I could have been clearer too, and I might have made it sound easier than it is in reality. Anyway, the important points are:

1. It's not difficult to permit either operand to be the same instance as the other operand OR the same instance as this, but yes it is important to mention and remember this issue in order to prevent a faulty implementation.
2. Duplication of an operand's underlying data/array is not necessarily required, even when it is the same instance as the other operand or this, depending on how the algorithm is written. For example, see System.Numerics.BigIntegerBuilder.Mul(ref BigIntegerBuilder, ref BigIntegerBuilder) and other big-integer math algorithms that don't destructively interfere. When an algorithm modifies an array element but never again reads that array element, it can succeed even when it is the same instance as the other operand or this, even without prior duplication, but it depends on which math operation it is, addition including subtraction, or multiplication, or division, and which algorithm is used.
3. In the case when the operands are BigInteger not Builder, then BigInteger is immutable thus merely copying the pointer is as good as copying the underlying data. It seems to be not-yet-decided whether the operands will be BigInteger or Builder or both supported.

"Double buffering" is another technique that can potentially be used to eliminate prior duplication of operands. The Builder has 2 buffers, one in use, one not in use, and it alternates between them. The result of a math operation is stored in whichever buffer is not currently in-use, and the in-use and not-in-use status of the 2 buffers is swapped.

[verelpode]

@svick mentioned previously that BigInteger recently received a new constructor that accepts Span<byte>. Let's put the same constructor in Builder, but not only byte, please let's also support UInt32. Byte is good in relation to binary serialization/deserialization purposes, whereas UInt32 is good for importing big integer data that was generated at runtime and that has nothing to do with serialization. Thus:

public Builder (ReadOnlySpan<byte> value, bool isUnsigned = false, bool isBigEndian = false);
public Builder (ReadOnlySpan<UInt32> value, bool isUnsigned = false);
public Builder (ReadOnlySpan<UInt64> value, bool isUnsigned = false);
public Builder (ReadOnlySpan<native int> value, bool isUnsigned = false);

In my opinion, the "isBigEndian" parameter is only applicable for byte not UInt32 (I wrote more details about this in a previous comment.)

Setting a Builder to ReadOnlySpan<byte> shouldn't be limited to the constructor. Thus I suggest that the constructors invoke public SetValue methods as follows:

public Builder (ReadOnlySpan<byte> value, bool isUnsigned = false, bool isBigEndian = false)
{
    this.SetValue(value, isUnsigned, isBigEndian);
}
public Builder (ReadOnlySpan<UInt32> value, bool isUnsigned = false)
{
    this.SetValue(value, isUnsigned);
}
public Builder (ReadOnlySpan<UInt64> value, bool isUnsigned = false)
{
    this.SetValue(value, isUnsigned);
}
public Builder (ReadOnlySpan<native int> value, bool isUnsigned = false)
{
    this.SetValue(value, isUnsigned);
}

public void SetValue(ReadOnlySpan<byte> value, bool isUnsigned = false, bool isBigEndian = false) { ... }
public void SetValue(ReadOnlySpan<UInt32> value, bool isUnsigned = false) { ... }
public void SetValue(ReadOnlySpan<UInt64> value, bool isUnsigned = false) { ... }
public void SetValue(ReadOnlySpan<native int> value, bool isUnsigned = false) { ... }

public void SetValue(Int32 value) { ... }
public void SetValue(UInt32 value) { ... }
public void SetValue(Int64 value) { ... }
public void SetValue(UInt64 value) { ... }

public void SetValue(UInt8 value) { this.SetValue((UInt32)value); }
public void SetValue(UInt16 value) { this.SetValue((UInt32)value); }

Although the SetValue(UInt8) and SetValue(UInt16) appear completely superfluous at first glance, they're not.

[verelpode]

I like the example in your last post: it looks fairly close to the original expression

I might end up with the same preference as you, but here's something to consider: Although that ArithmeticSeries example was helpful and a good start (I'm not criticizing it), it may be worthwhile to work through another example; this time an example that suits real modern software engineering practices as opposed to an artificial example similar to what mathematicians and math teachers produce.

Unfortunately math teachers continue to use a very old style that causes never-ending difficulties and complaints from students. In the beginning of software engineering, the old problematic mathematical style was copied into software engineering, but in modern software engineering, especially in teamwork, it is increasingly recognized that it is bad practice to obscurely name variables, parameters, or fields as "q1" and "q2" instead of something meaningful such as "remainingDistance" and "estimatedDistance".

In the past, "q1" and "q2" were viewed as intelligent because people thought:
"I understand nothing of what he wrote therefore he must be super intelligent. The more complex and difficult it is to understand, the smarter it must be. When I write something, I'll likewise write it in a way that is impressively obscure and complex."

Nowadays the attitude in professional software engineering is increasingly becoming like this:
"Obscure names such as q1 and q2 cause difficulties for team members / coworkers and long-term maintainability of code. Our team runs better when the code is clear and easy to understand, as much as possible/practical. Whenever possible, a simple-but-effective solution is impressive and intelligent. Artificial complexity causes problems such as increased rate of mistakes/bugs, additional cost and delay to produce the next version, and difficulty transferring code between coworkers."

I was shocked when I heard a university mathematics professor say proudly: "And this is exactly the same today as it was 200 years ago!"

I was shocked because he said it with pride and joy, whereas I thought: "Aren't you the least bit embarrassed about having made no progress, no advancements, no improvements during the last 200 years? I'd reconsider before I'd proudly announce no changes after 200 years."

My point is, we are software engineers not mathematics professors, therefore let's design BigInteger.Builder to suit modern professional software engineering practices, not to suit badly-written math textbooks that torment poor university students year after year after year.

[Clockwork-Muse]

In the past, "q1" and "q2" were viewed as intelligent because people thought: "I understand nothing of what he wrote therefore he must be super intelligent. The more complex and difficult it is to understand, the smarter it must be. When I write something, I'll likewise write it in a way that is impressively obscure and complex."

....I don't think this was ever actually true.

Discounting the common practice of short variable names for loop counters (which should probably be changed to more descriptive names in many cases, although I doubt they were ever intended to look complex), in some older languages there was literally a maximum length that the parser/linker would accept:

early linkers which required variable names to be restricted to 6 characters to save memory. A later "advance" allowed longer variable names to be used for human comprehensibility, but where only the first few characters were significant. In some versions of BASIC such as TRS-80 Level 2 Basic, long names were allowed, but only the first two letters were significant. This feature permitted erroneous behaviour that could be difficult to debug, for example when names such as "VALUE" and "VAT" were used and intended to be distinct.

(BASIC isn't the only language with a restriction like this - many punchcard/columnar-based languages would be restricted due to the input/storage medium!)

And while it's true that at least some of the tradition for short variable names comes from mathematics, there variable names aren't intended to obscure things, but rather most of the time it's intended as an abstraction, and you just want "something that's not a digit".

[verelpode]

Sure, sometimes I use single-letter names as well, especially "i" in "for" loops. I don't want to be an extremist against single-letter names. It's a judgement call. The preference for descriptive names is only a guideline, not a hard rule from an extremist who can only see black and white and nothing in-between.

Good point re some early languages being incapable of longer names, but the problem of artificial obscurity also pops up in languages that do support long names. I can't speak for your experiences, but in my experience, I have personally experienced cases of artificially-introduced obscurity/complexity. Fake complexity intended to impress. I have encountered real people who are elitist and view obscurity as a sign of intelligence and simplicity as a sign of a plebeian. (Not svick. I know svick wasn't doing that.)

At this point (and I would personally prefer a this-returning type), do we really have a Builder, as opposed to a MutableBigInteger?

I prefer the name "Builder" because it indicates that instances of Builder are intended/designed to have a relatively short lifespan, whereas instances of immutable BigInteger are suitable for long-term storage of values. In contrast, if Builder is named "MutableBigInteger", then it sounds like it's suitable for long-term storage but it likely won't be (depending on how it's implemented).

For example, if a Builder implementation happened to use the aforementioned double-buffering technique to avoid operand duplications, then a Builder instance can contain 2 arrays and this is satisfactory for a Builder but not for a MutableBigInteger. If a MutableBigInteger is stored for a long time and it contains a large secondary array/buffer that is unused, then it's a design defect.

Likewise in general, if any Builder class is named "Builder", then the implementation has the freedom to store any temporary objects that may be helpful in private fields of Builder. This implementation freedom and optimization freedom is cancelled if Builder is named "MutableBigInteger" because the lifetime/scope of "MutableBigInteger" becomes unclearly defined.

The reason for having 2 classes -- one immutable and one Builder -- is a clearly defined reason with a well-known advantage, whereas if we have "ImmutableX" and "MutableX", then the design has an awkward question such as: Why not just use "MutableX" for everything and delete "ImmutableX" entirely? Thus a design of "ImmutableX" plus "MutableX" is harder to justify than "ImmutableX" plus "ImmutableX.Builder". I'd stick with Tanner's naming regardless of whether the methods do return this;

If the Builder pattern is claimed to be wrong, then it would mean that System.String can be deleted and System.Text.StringBuilder used instead, in all places where strings are used.

[verelpode]

To be consistent with BitwiseAnd and BitwiseOr, I suggest renaming Xor to BitwiseExclusiveOr. Nowadays VS/IntelliSense makes it easy to use full names. See also System.Linq.Expressions.Expression.ExclusiveOr and ExclusiveOrAssign. "And", "Or", and "Exclusive Or" are all the same category -- they're all boolean logic functions therefore it'd be good to name them consistently with each other.

LeftShift and RightShift could be renamed to BitwiseShiftLeft and BitwiseShiftRight. (Alternatively BitwiseShiftUp (left) and BitwiseShiftDown (right) are better names except for being non-traditional. I expect that people will want to stick with the traditional names in this case.)

I notice the proposed API contains both Remainder AND Modulus. Is that intentional somehow?

I suggest renaming Builder.Pow to Power (or maybe RaiseBy) because "pow()" is an obsolete function name from the "bad old days" of plain C -- the Wild Wild West of programming -- the medieval middle ages of software -- the Dark Ages. Even when RAM was much smaller than it is today, there was no justifiable logical reason for truncating the name of this function by removing the last 2 bytes/chars.

Note if Builder.Multiply will not exist and only Builder.MultiplyBy will exist, then the Power method would operate likewise and would be named something like RaiseBy I guess.

Unfortunately System.Math.Pow continues the bad practice from C, but there is no good reason why BigInteger.Builder should perpetuate this bad practice just because System.Math contains some unfortunate naming. Anyway possibly this issue will be side-stepped via AddWith, MultiplyBy, DivideBy, RaiseBy, etc.

Last night I had a nightmare about the bad old days. I dreamed that I was forced to write a huge section of an app using plain old C. I woke up screaming and drenched in sweat. I grabbed the phone and immediately called the emergency hotline and exclaimed anxiously: "I'm deathly worried about having a huge C section!!" The guy replied calmly: "Don't worry. You're a man. Men don't have C sections."

[tannergooding]

To be consistent with BitwiseAnd and BitwiseOr, I suggest renaming Xor to BitwiseExclusiveOr.

There are pre-existing "friendly" names that exist for all the standard operators. The names I used above follow that: https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/operator-overloads

I notice the proposed API contains both Remainder AND Modulus. Is that intentional somehow?

Remainder and Modulus are different functions and have different behaviors when dealing with negative numbers.

I suggest renaming Builder.Pow to Power (or maybe RaiseBy) because "pow()" is an obsolete function

This is still the standard name used by most spec's, frameworks, and languages (including .NET). It is also the name used by the existing BigInteger class. Having consistency is generally considered better and it will likely not change.

At this point (and I would personally prefer a this-returning type), do we really have a Builder, as opposed to a MutableBigInteger?

The builder pattern and calling the mutable version "Builder" is an existing convention we have.

[tannergooding]

The conversations above have covered some great points so far. I'll try to collect the points covered so far and updated the original post sometime soon (including examples of the different suggested patterns).

[verelpode]

Should Builder accept operands of type Builder or BigInteger or both? Following I've written an incomplete example implementation that demonstrates one way of allowing the operand of MultiplyBy to be Builder, BigInteger, uint, or UInt64 (signed int would also be supported but is not shown here).

This is implemented as a wrapper around the preexisting internal struct System.Numerics.BigIntegerBuilder, which I renamed to SBigIntegerBuilder in this example for clarity.

This already supports copy-on-write via the preexisting System.Numerics.BigIntegerBuilder._fWritable.

This isn't intended to be a real nor proper implementation. It is only an example of what is possible. This does contain bugs -- for example, it doesn't even try to calculate the correct sign of the multiplication result. Likewise yes one must be careful to prevent malfunction when the operand is the same instance as this and there exists more than one solution to that issue.

public class Builder
{
    private SBigIntegerBuilder _internalBuilder;

    public Builder MultiplyBy(Builder inOperand)
    {
        _internalBuilder.Mul(ref inOperand._internalBuilder);
        return this;
    }

    public Builder MultiplyBy(BigInteger inOperand)
    {
        SBigIntegerBuilder operandAsSBuilder = new SBigIntegerBuilder(inOperand);
        _internalBuilder.Mul(ref operandAsSBuilder);
        return this;
    }

    public Builder MultiplyBy(uint inOperand)
    {
        SBigIntegerBuilder operandAsSBuilder = new SBigIntegerBuilder();
        operandAsSBuilder.Set(inOperand);
        _internalBuilder.Mul(ref operandAsSBuilder);
        return this;
    }

    public Builder MultiplyBy(UInt64 inOperand)
    {
        SBigIntegerBuilder operandAsSBuilder = new SBigIntegerBuilder();
        operandAsSBuilder.Set(inOperand);
        _internalBuilder.Mul(ref operandAsSBuilder);
        return this;
    }

} // class Builder

[verelpode]

The idea of "MultiplyBy" with return this; was liked. Although the English language makes the "By" naming easy for multiplication and division, unfortunately English does not make it so easy for subtraction. Therefore note the following difference between SubtractWith versus SubtractFrom. The many peculiarities of English and other natural languages. Here is a list of potential names, not without some flaws.

r.Increment()       means r = r + 1;
r.Decrement()       means r = r - 1;
r.AddWith(b)        means r = r + b;
r.SubtractWith(b)   means r = r - b;
r.SubtractFrom(b)   means r = b - r;
r.MultiplyBy(b)     means r = r * b;
r.DivideBy(divisor) means r = r / divisor;
r.DivideToRemainderBy(b) means remainder of r divided by b;
r.RaiseBy(exponent)  means r = r ** exponent; means r = Power(r, exponent);
r.PowerModulo(exponent, modulus)  means DivRemainder(Power(value, exponent), modulus);

r.MakePositive()     means r = abs(r);
r.MakeNegative()     means r = -abs(r);
r.InvertSign()       means r = -r;

r.BitwiseAndWith(b)  means r = r & b;
r.BitwiseOrWith(b)   means r = r | b;
r.BitwiseExclusiveOrWith(b) means r = r ^ b;
r.OnesComplement()   means r = -(r + 1);
r.BitwiseShiftLeft(amount)  means r = r << amount;
r.BitwiseShiftRight(amount) means r = r >> amount;

r.SelectLowest(b)    means r = min(r, b);
r.SelectHighest(b)   means r = max(r, b);

r.GreatestCommonDivisor(b) means r = GCD(r, b);
r.NaturalLogarithm() means r = BigInteger.Log(r);
r.Logarithm10()      means r = BigInteger.Log10(r);
r.Logarithm(base)    means r = BigInteger.Log(r, base);

Yes I deliberately included a couple of names that provoke controversy and quarrel because on one hand they are better names but on the other hand, many people find it impossibly difficult to change old ingrained habits/traditions even when the tradition is something as wildly nuts as drinking car fuel (ethanol) every weekend as if it's perfectly normal for everyone to drink car fuel. Cheers :-)

[verelpode]

Remainder and Modulus are different functions and have different behaviors when dealing with negative numbers.

Aha, I didn't realize that. In that case, shouldn't the Modulus method be renamed to Modulo? Here's the definition of "modulus" in Oxford English Dictionary:

Mathematics: 1 another term for absolute value 1.1 The positive square root of the sum of the squares of the real and imaginary parts of a complex number. 2 A constant factor or ratio. 3 A number used as a divisor for considering numbers in sets, numbers being considered congruent when giving the same remainder when divided by a particular modulus.

Definitions 1 and 1.1 are also examples of the problem that I mentioned -- elitism and deliberate obfuscation -- and such behavior is unprofessional and bad for teamwork and should not be adopted into software engineering. Definition 3 is the nearest to what BigInteger needs but it says that the "modulus" is the divisor, which would mean that where the Builder proposal currently says....

public static Builder Modulus(Builder dividend, Builder divisor);

...the "divisor" parameter is also known as "modulus", but let's keep the name "divisor" because the name "modulus" makes no sense.

"Modulo operation" in Wikipedia says the same as Oxford -- that the divisor is sometimes called modulus:

In computing, the modulo operation finds the remainder after division of one number by another (sometimes called modulus).

• Name of the operation: Modulo
• Name of the divisor: Divisor or modulus
• Name of the result: Remainder

Mathematical terminology is a minefield and desperately needs to be updated but as I mentioned, unfortunately the attitude is that it's impressive to have 200 years without progress/changes, and that "obfuscation = super intelligent".

C# "Operator Overloads" doesn't actually say that the modulo operation should be called modulus. It says that the "Friendly Name" is "Mod or Remainder" therefore it suggests Builder.Mod or Builder.Remainder not Builder.Modulus. Unfortunately the metadata name is "op_Modulus" but that's irrelevant because that's a hidden internal compiler-generated name that the C# compiler stores into a compiled Assembly, not normally visible to the user of the C# language. Builder.Mod isn't a hidden internal compiler-generated name, therefore the internal "op_Modulus" can be ignored.

See also the preexisting BigInteger.ModPow method:

public static BigInteger ModPow(BigInteger value, BigInteger exponent,BigInteger modulus)

This "modulus" parameter in BigInteger.ModPow is consistent with OED and Wikipedia, whereas the proposed Builder.Modulus method is not.
Damn, I only wanted to write a short message about this topic.

[FiniteReality]

Since there's a way to get a byte[] from the Builder, shouldn't there be a way to get a Span from the builder? BigInteger has TryWriteBytes, so I'm guessing this was missed.

[verelpode]

@FiniteReality I agree. This should be supported in both directions. For the direction Span-to-BigInteger, see my previous comment, and for the direction BigInteger-to-Span, I suggest the following methods. What do you think?

class Builder
{
    public int CopyTo(Span<byte> destination, bool isUnsigned = false, bool isBigEndian = false);
    public int CopyTo(Span<UInt32> destination, bool isUnsigned = false);
    public int CopyTo(Span<UInt64> destination, bool isUnsigned = false);

    // Span might be unsupported in some environments, therefore also support arrays directly:
    public int CopyTo(byte[] destination, int destinationIndex, bool isUnsigned = false, bool isBigEndian = false);
    public int CopyTo(UInt32[] destination, int destinationIndex, bool isUnsigned = false);
    public int CopyTo(UInt64[] destination, int destinationIndex, bool isUnsigned = false);
}

struct BigInteger
{
    // BigInteger and BigInteger.Builder should both have the same "CopyTo" methods.
    public int CopyTo(...);
}

The name CopyTo is consistent with System.Collections.Generic.ICollection<T>.CopyTo(T[] array, int arrayIndex).

I defined CopyTo to return int. It should return the number of elements copied/written to the destination span or array, which may be less than the length of the span. If the span length (or remaining array length) is insufficient, then do nothing and throw exception. When copying to a byte array or span, CopyTo should return the same as Builder.GetByteCount. When copying to a UInt32 array or span, the measurement unit of destinationIndex and the return value are elements not bytes, thus CopyTo(Span<UInt32>, ...) returns a length equalling Builder.GetByteCount(...) / sizeof(UInt32).

In my opinion, Span<UInt32> and Span<UInt64> should be supported, not only Span<byte>, because byte is for serialization/deserialization purposes whereas UInt32 and UInt64 are for importing/exporting data generated at runtime unrelated to serialization.

[verelpode]

I also suggest adding the following "TryConvertTo" methods to both of BigInteger.Builder and BigInteger. These methods attempt to typecast/convert the BigInteger or BigInteger.Builder without throwing System.OverflowException, unlike the existing typecast operators in BigInteger. The following methods should return false if conversion is unsucccessful (meaning return false if the BigInteger does not fit within the specified smaller integer type).

public bool TryConvertTo(out Int32 outValue);
public bool TryConvertTo(out Int64 outValue);
public bool TryConvertTo(out UInt32 outValue);
public bool TryConvertTo(out UInt64 outValue);

// The following would throw exception when conversion is unsucccessful:
public Int32 ConvertToInt32();
public Int64 ConvertToInt64();
public UInt32 ConvertToUInt32();
public UInt64 ConvertToUInt64();

Alternatively "TryConvertTo" could be named "TryConvert".

Actually I prefer to make the "TryConvertTo" methods return a nullable integer (as follows) instead of boolean and output parameter, but I changed the proposal to bool+out because @tannergooding wanted it. I don't agree but I've accepted Tanner's decision, so the proposal is now boolean+out, whereas the previous proposal was:

public Int32? TryConvertToInt32();
public Int64? TryConvertToInt64();
public UInt32? TryConvertToUInt32();
public UInt64? TryConvertToUInt64();

public Int32 ConvertToInt32();
public Int64 ConvertToInt64();
public UInt32 ConvertToUInt32();
public UInt64 ConvertToUInt64();

In the case of converting to unsigned UInt64, if the BigInteger is less than zero (UInt64.MinValue) or greater than UInt64.MaxValue, then TryConvertTo(out UInt64) would return false.

For 128-bit integers, the following TryConvertToInt128 method would return true if the conversion is successful. The sign would be output separately via the boolean "outNegative" parameter (I've found that separated sign is quite useful), thus the "outLowPart" and "outHighPart" parameters are in-effect set to what would be the result of BigInteger.Abs.

public bool TryConvertToInt128(out UInt64 outLowPart, out UInt64 outHighPart, out bool outNegative)
{
    outNegative = (_sign < 0);
    ...
}

// Conversion to unsigned 128-bit integer:
public bool TryConvertToUInt128(out UInt64 outLowPart, out UInt64 outHighPart)
{
    bool neg;
    return (this.TryConvertToInt128(out outLowPart, out outHighPart, out neg) && !neg);
}

// Conversion to signed 128-bit integer with high part represented as signed 64-bit integer:
public bool TryConvertToInt128(out UInt64 outLowPart, out Int64 outHighPart)
{
    UInt64 unsignedHighPart;
    bool neg;
    if (this.TryConvertToUInt128(out outLowPart, out unsignedHighPart, out neg))
    {
        if (neg)
        {
            if (unsignedHighPart <= unchecked((UInt64)Int64.MinValue))
            {
                outHighPart = unchecked(-(Int64)unsignedHighPart);
                return true; // success
            }
        }
        else if ((unsignedHighPart >> 64) == 0)
        {
            outHighPart = unchecked((Int64)unsignedHighPart);
            return true; // success
        }
    }
    outLowPart = 0;
    outHighPart = 0;
    return false; // unsuccessful
}

If desired, TryConvertTo could also be supported for floating-point as follows.

public bool TryConvertTo(out double outValue);
public bool TryConvertTo(out single outValue);
public bool TryConvertTo(out decimal outValue);

public double ConvertToFloat64();
public single ConvertToFloat32();
public decimal ConvertToDecimal();

Note TryConvertTo(out double) etc should only return exactly converted values. If the BigInteger would be inexactly/approx represented by float64 (System.Double), then null should be returned. If you want an inexact conversion to float64, then use the preexisting public static explicit operator Double(BigInteger value) that is already present in BigInteger. Alternatively, if desired, TryConvertTo(out double) might have a parameter to control exact versus inexact conversion, as follows:

public bool TryConvertTo(out double outValue, bool approximation = false);
public bool TryConvertTo(out single outValue, bool approximation = false);
public bool TryConvertTo(out decimal outValue, bool approximation = false);

For reference, previously @tannergooding mentioned "ConvertTo" methods in addition to the "TryConvertTo":

We should likely also consider exposing plain ConvertToX methods for contrast (as I believe the non-throwing methods would be the explicit casts otherwise).

[tannergooding]

Just wanted to say, as much as there are some great ideas for new APIs, they need to be split out into a separate proposal.

The initial proposal for the BigInteger.Builder should just try to provide parity with the existing BigInteger struct. This simplifies the review process and will give it a higher chance of being merged.

The entirely new APIs can then be reviewed/processed independently (which also makes their review simpler and gives them a higher chance of being accepted) with the assumption that they will either also make it into the builder (whether accepted/merged before or after the builder).

[verelpode]

I thought further about this issue: On one hand, the idea of "MultiplyBy" with return this; was liked, and it works well with multiplication etc., but not with certain other special operations such as Builder.GreatestCommonDivisor, therefore I suggest the following API where suitable operations are represented in "By" form whereas other operations are represented in "return void" form.

public Builder MultiplyBy(Builder operand);
public Builder MultiplyBy(BigInteger operand);
public Builder MultiplyBy(Int32 operand);
public Builder MultiplyBy(Int64 operand);

public Builder DivideBy(Builder operand);
public Builder DivideBy(BigInteger operand);
public Builder DivideBy(Int32 operand);
public Builder DivideBy(Int64 operand);

public Builder RaiseBy(Int32 exponent);
...
public Builder Increment();
public Builder Decrement();
...
public Builder InvertSign(); // will be renamed to "Negate" unfortunately.
public Builder MakePositive(); // will be renamed to "Abs" unfortunately.
public Builder MakeNegative();
public Builder OnesComplement();
...

And the following non-static methods return void/nothing and store the result into this. Any preexisting value in this is ignored and overwritten.

public void GreatestCommonDivisor(Builder left, Builder right);
public void PowerModulo(Builder value, Builder exponent, Builder modulus);
public void SelectLowest(Builder operandA, Builder operandB);
public void SelectLowest(Builder operandA, Builder operandB, Builder operandC);
public void SelectHighest(Builder operandA, Builder operandB);
public void SelectHighest(Builder operandA, Builder operandB, Builder operandC);

If desired, both the MultiplyBy and Multiply patterns could be supported as follows, with MultiplyBy implemented by invoking this.Multiply.

public void Multiply(Builder operandA, Builder operandB) { ... }

public Builder MultiplyBy(Builder operand)
{
    this.Multiply(this, operand);
    return this;
}

public Builder MultiplyBy(BigInteger operand) { ... }
public Builder MultiplyBy(Int32 operand) { ... }
public Builder MultiplyBy(Int64 operand) { ... }

static/non-instance 3-parameter forms might also be supported as follows, and the methods with 1 and 2 parameters are implemented by invoking the 3-parameter method.

// Non-instance method:
public static void Multiply(Builder destination, Builder operandA, Builder operandB) { ... }

// Per-instance methods:
public void Multiply(Builder operandA, Builder operandB)
{
    Builder.Multiply(this, operandA, operandB);
}

public Builder MultiplyBy(Builder operand)
{
    Builder.Multiply(this, this, operand);
    return this;
}

public Builder MultiplyBy(BigInteger operand) { ... }
public Builder MultiplyBy(Int32 operand) { ... }
public Builder MultiplyBy(Int64 operand) { ... }

Re the overloads to conveniently support the operand being any of Builder, BigInteger, Int32, Int64, these convenient shortcuts would probably only be supported with MultiplyBy(operand) not Multiply(a,b) and not Multiply(dest,a,b), because the 2-param and 3-param methods would produce too many combinations. See also the SetValue methods that I proposed in a previous message:

class Builder
{
    public void SetValue(Int32 value) { ... }
    public void SetValue(UInt32 value) { ... }
    public void SetValue(Int64 value) { ... }
    public void SetValue(UInt64 value) { ... }

    // The following may serve as tiny optimizations but it depends on the internal details of Builder.
    public void SetValue(UInt8 value) { this.SetValue((UInt32)value); }
    public void SetValue(UInt16 value) { this.SetValue((UInt32)value); }
}

[verelpode]

@tannergooding

The entirely new APIs can then be reviewed/processed independently

OK. When you update the Builder proposal, you could place the summary/API of the separate proposal in a commented-out section like follows:

class Builder
{
    public Builder MultiplyBy(Builder operand);
    ...

    /*
    The following methods are also proposed but will be finalized via a separate proposal.
    ...
    ...
    */
}

The reason for summarizing the separate proposal in a commented-out section is this: Sometimes a design appears good when we see and consider only the small picture, but it no longer appears good when we see the big picture. Thus I suggest that "Stage 1" is decided with inclusion of a summary of the ideas in "Stage 2" even though "Stage 2" will be implemented via a separate proposal. This way we avoid losing the big picture, yet still gain the advantages of separation that you mentioned.

[bazzilic]

Is there any movement on this?

[tannergooding]

This will end up on the general backlog of issues so it might be a bit before it gets to API review, reviewed, approved, and implemented.

Given its nature, it likely would benefit from a prototype being built to vet that it works as intended. I would be fine with that happening in dotnet/corefxlab under the System.Numerics.Experimental project if someone (or multiple people) want to give it a go.

The experimental package would then be useable and would help ensure any API surface we took to API review was correct and that we weren't missing anything obvious.

[JasonBock]

FWIW I just ran into this (sort of). I'm doing multiple multiplications of BigInteger values, and I'm seeing allocations for every single one, even though I really only need "one" BigInteger value. If there was a "Builder" type that would reduce the allocations (and stay performant) that would be a really nice addition. I hope this doesn't stay on the backlog too long :)

[tannergooding]

This won't happen for .NET 6, but this is one of the things I want to address in the near future

[koszeggy]

Apart from building a new value without many allocations, it would also be useful to access the inner bytes of an already built BigInteger, without calling the allocating ToByteArray method:

public partial struct BigInteger
{
    // could be an indexer just like on string and StringBuilder but since .NET Core 2.1 we have more parameters
    public byte GetByte(int index, bool isUnsigned = false, bool isBigEndian = false);
}

And of course, this could appear also on the Builder class. The isUnsigned and isBigEndian parameters work like in the ToByteArray and GetByteCount methods.

---

Edit: Maybe the Builder could expose the actual little endian raw data in two's component format via a writable indexer:

// Only in Builder: to access the actual raw content:
public byte this[int index] { get; set; } // accesses _sign for small values
public int RawLength { get; }

[izilla]

Any movement on this?