Mutable interface for BigInts

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2011-11-25T16:52:13Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=7013

CC List

• hsteoh

Description

When multi-precision numbers become large or quite large, the time spent managing their memory risk becoming an issue. To improve this situation the GNU multiprecision integer library allows for mutable numbers, that allow in-place modification.

There was a discussion about offering a mutable interface for the General Multiprecision PYthon project (GMPY) numbers too (see "Mutability... but not for now"):
http://gmpy.sourceforge.net/

So maybe it's useful to add a mutable interface to Phobos bigints. A simple way to do it is to add a "mutable" attribute that supports just few in-place operations like += -= *= /= ^^= &= |= (but not other operations like == that don't need mutability, to keep the situation semantically more clean):

auto x = BigInt("...");
x.mutable += BigInt("...");

[dlangBugzillaToGithub]

hsteoh commented on 2013-07-09T08:59:04Z

In latest git HEAD, the following works:

import std.bigint;
void main() {
        BigInt x = 123;
        BigInt y = 321;
        x += y;
        assert(x == 444);
}

Not sure what's happening under the hood, though. Is it making internal allocations?

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-07-09T09:57:35Z

(In reply to comment #1)
> In latest git HEAD, the following works:
> 
> import std.bigint;
> void main() {
>         BigInt x = 123;
>         BigInt y = 321;
>         x += y;
>         assert(x == 444);
> }
> 
> Not sure what's happening under the hood, though. Is it making internal
> allocations?

That code works, but it's not about what this enhancement request is about. When you perform x+=y; the data inside x probably doesn't change.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-07-09T09:58:59Z

(In reply to comment #2)

> When you perform x+=y; the data inside x probably doesn't change.

I meant the original x.

[dlangBugzillaToGithub]

hsteoh commented on 2013-07-09T10:07:34Z

You're right, I looked at the code for BigInt, every time you do +=, it allocates a new underlying buffer. That's pretty inefficient if you're using these operations in an inner loop.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-07-09T10:24:39Z

(In reply to comment #4)
> You're right, I looked at the code for BigInt, every time you do +=, it
> allocates a new underlying buffer. That's pretty inefficient if you're using
> these operations in an inner loop.

On the other hand I think a mutable integer is not what most people expect, and it can cause some undesired side effects (and bugs).

That's why I suggested to introduce a specific syntax that allows you to manage bigints as mutable buffers where max performance is needed, and keep their behavour clean on default. Generally I think it's better to perform tricky optimizations only on explicit request.

Some possible alternative syntaxes:

x.mutable += y;
x.mulAcc(y);
x.mutate!"+"(y);