http://d.puremagic.com/issues/show_bug.cgi?id=5765

           Summary: ^^ and << with BigInts
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-03-21 15:24:46 PDT ---
If I try to perform a 2^^10 with bigints I find some troubles (dmd 2.052):


import std.bigint;
void main() {
    BigInt p1 = BigInt(2) ^^ 10;         // OK
    BigInt p2 = BigInt(1) << 10;         // OK

    BigInt p3 = BigInt(2) ^^ BigInt(10); // Error
    BigInt p4 = 2 ^^ BigInt(10);         // Error

    BigInt p5 = BigInt(1) << BigInt(10); // Error
    BigInt p6 = 1 << BigInt(10);         // Error
}


I'd like those six lines to work, if possible. (I remember an enhancement request related to this, but I can't find it).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #1 from Don <clugdbug@yahoo.com.au> 2011-03-22 00:39:07 PDT ---
Those operations could easily be allowed. But it's not an accident that they're not currently implemented. The question is, is it a good idea?

anything ^^ BigInt  and anything << BigInt will ALWAYS overflow, if the BigInt doesn't actually fit into an int.

So except for a few toy cases, such as the example here, such operations are
always bugs in the user's code.
Do we really want to allow such a bug-prone operation which provides no useful
functionality?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #2 from bearophile_hugs@eml.cc 2011-03-22 02:29:39 PDT ---
Here n needs to be a BigInt, because of the second recursive call. So instead
of writing 2^^n you need to write BigInt(2)^^n.toInt() that's not natural (this
code will probably work in DMD 2.053 thanks to a -0 bug you have fixed):


import std.stdio, std.bigint;

/// Optimized Ackermann function
BigInt ackermann(int m, BigInt n) {
    if (m == 0) return n + 1;
    if (m == 1) return n + 2;
    if (m == 2) return 3 + n * 2;
    //if (m == 3) return 5 + 8 * (2 ^^ n - 1);
    if (m == 3) return 5 + 8 * (BigInt(2) ^^ n.toInt() - 1);
    if (n == 0)
        return ackermann(m - 1, BigInt(1));
    else
        return ackermann(m - 1, ackermann(m, n - 1));
}

void main() {
    writeln(ackermann(4, BigInt(2)));
}


Equivalent Python2.6 code that works:


def ackermann(m, n):
    """Optimized Ackermann function"""
    if m == 0: return n + 1
    if m == 1: return n + 2
    if m == 2: return 3 + n * 2
    if m == 3: return 5 + 8 * (2 ** n - 1)
    if n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))

assert len(str(ackermann(4, 2))) == 19729

--------------

Two little about BigInt (maybe it's wrong to put those in this bug report):

How do I perform the equivalent of str(ackermann(4, 2)) with BigInt?

The bottom of this page shows a duplication to me: http://www.digitalmars.com/d/2.0/phobos/std_bigint.html

The output format is controlled via formatString:
The output format is controlled via formatString: "d"     Decimal
"x"     Hexadecimal, lower case
"X"     Hexadecimal, upper case
"s"     Default formatting (same as "d")
null     Default formatting (same as "d")
"d"     Decimal
"x"     Hexadecimal, lower case
"X"     Hexadecimal, upper case
"s"     Default formatting (same as "d")
null     Default formatting (same as "d")

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #3 from Don <clugdbug@yahoo.com.au> 2011-03-23 03:42:32 PDT ---
OK, although I don't think that the case with Ackermann code is so bad. It's basically giving you a compile-time warning that the function blows up very, very easily. Having seen this, it becomes obvious that the m=4 case will blow up for n>2, and therefore that the m=5 will blow up for n>0, and the m>=6 will blow up for any n. Since this only leaves a total of 4 cases, A(4,0) = 13, A(4,1) = A(5,0) = 65533, and A(4,2), why not continue the optimization, and eliminate the recursion entirely? So I think it encourages you to write better quality code. I think it's quite bizarre to stop at m=3, so I don't find this example convincing.

The thing I'm really worried about is this:
BigInt a, b, c;

a = (a ^^ b) % c;
This is an attempt to do modular exponentiation, which comes up frequently in
cryptography. The code is mathematically correct, but completely wrong in
practice.
So I would rather give an informative static assert for the BigInt ^^ BigInt
case.
(Definitely, it shouldn't just fail the way it does now).


> How do I perform the equivalent of str(ackermann(4, 2)) with BigInt?

format("%d", ackermann(4,2))

>The bottom of this page shows a duplication to me: http://www.digitalmars.com/d/2.0/phobos/std_bigint.html

You're right. A new ddoc bug.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #4 from bearophile_hugs@eml.cc 2011-03-23 05:55:03 PDT ---
(In reply to comment #3)

> The thing I'm really worried about is this:
> BigInt a, b, c;
> 
> a = (a ^^ b) % c;
> This is an attempt to do modular exponentiation, which comes up frequently in
> cryptography. The code is mathematically correct, but completely wrong in
> practice.

In Python 2.6 the built-in pow function has a third optional argument, that's the modulus, that uses a more efficient algorithm to perform the powermod (note the second 6 that's not a multi-precision value):

>>> (20 ** 125) % 7
6L
>>> pow(20, 125, 7)
6

I suggest to add a similar function to std.math or std.bigint. Also the D compiler may recognize the (x^^y)%z pattern and replace it with a power mod function call.


> So I would rather give an informative static assert for the BigInt ^^ BigInt case.

Python allows you to use the power/shift with multi-precision numbers too, if you want. The multi-precision numbers can be used transparently, syntax-wise. If you have D templated code that you want to use with both BigInt and int you will have to use a static if to change the code from x^^y to BigInt(x)^^y.toInt() (or call a little pow template function that does the same, losing infix operator syntax again), this isn't good. BitInt are meant to work as integers, mostly. I'd like a D program to work with as few changes as possible if I replace int with BigInts or BigInts with ints (in some situations I may write the code with BigInts, see the results and then try to write the same with ints/longs, to spot the overflows).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #5 from Don <clugdbug@yahoo.com.au> 2011-03-23 06:57:19 PDT ---
(In reply to comment #4)
> (In reply to comment #3)
> 
> > The thing I'm really worried about is this:
> > BigInt a, b, c;
> > 
> > a = (a ^^ b) % c;
> > This is an attempt to do modular exponentiation, which comes up frequently in
> > cryptography. The code is mathematically correct, but completely wrong in
> > practice.

> I suggest to add a similar function to std.math or std.bigint.

Of course, that's what I was implying. Note that it is a totally different operation to ^^.

> Also the D
> compiler may recognize the (x^^y)%z pattern and replace it with a power mod
> function call.

I think that's asking too much.
Also note that it doesn't cover the two step pattern where someone does:
x = x ^^ y ;
x %= z;

 > > So I would rather give an informative static assert for the BigInt ^^
BigInt
> > case.
> 
> Python allows you to use the power/shift with multi-precision numbers too, if you want. The multi-precision numbers can be used transparently, syntax-wise. If you have D templated code that you want to use with both BigInt and int you will have to use a static if to change the code from x^^y to BigInt(x)^^y.toInt() (or call a little pow template function that does the same, losing infix operator syntax again), this isn't good.

That's a false consistency. T ^^ int  is the common operation, not T ^^ T. Really. BigInt ^^ BigInt isn't a BigInt. It's too big to be representable.

> BitInt are meant to
> work as integers, mostly. I'd like a D program to work with as few changes as
> possible if I replace int with BigInts or BigInts with ints (in some situations
> I may write the code with BigInts, see the results and then try to write the
> same with ints/longs, to spot the overflows).

So? These ones which currently don't compile, will definitely cause problems with ints/longs as well. You're just getting the error message at compile time rather than at run time.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #6 from bearophile_hugs@eml.cc 2011-03-23 10:55:03 PDT ---
(In reply to comment #5)

> That's a false consistency. T ^^ int  is the common operation, not T ^^ T. Really. BigInt ^^ BigInt isn't a BigInt. It's too big to be representable.

Python3 (and Lisp-family languages, and others) use multi-precision integers on default, but most people don't store large numbers in them, most times they store little numbers, and most people doesn't use them for cryptography.

I am not going to use D BigInts for cryptography. 99.9% times inside BigInts I'll keep numbers less than 63 bit long. I'd like to use BigInt as in Python to avoid the problems caused by int, because currently in D there are no integer overflow tests, because Walter doesn't want them.

The first and by a wide margin most important purpose of multi-precision integers is not to represent huge numbers or to do cryptography, but to free the mind of the programmer from being forced to think all the time about possible overflows breaking the code he/she is writing, freeing that part of attention, and allowing him/her to focus more on the algorithm instead. This is one of the causes that explain why Python is good to write prototypes, allowing to implement algorithms faster than most other languages (D included).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #7 from Don <clugdbug@yahoo.com.au> 2011-03-23 13:35:05 PDT ---
(In reply to comment #6)
> (In reply to comment #5)
> 
> > That's a false consistency. T ^^ int  is the common operation, not T ^^ T. Really. BigInt ^^ BigInt isn't a BigInt. It's too big to be representable.
> 
> Python3 (and Lisp-family languages, and others) use multi-precision integers on default, but most people don't store large numbers in them, most times they store little numbers, and most people doesn't use them for cryptography.

They are not system languages. The comparison is irrelevant.

> I am not going to use D BigInts for cryptography. 99.9% times inside BigInts I'll keep numbers less than 63 bit long. I'd like to use BigInt as in Python to avoid the problems caused by int, because currently in D there are no integer overflow tests, because Walter doesn't want them.

OK, now the truth comes out. You shouldn't be using BigInt for that. That's a very simple task.

> The first and by a wide margin most important purpose of multi-precision integers is not to represent huge numbers or to do cryptography, but to free the mind of the programmer from being forced to think all the time about possible overflows breaking the code he/she is writing, freeing that part of attention, and allowing him/her to focus more on the algorithm instead.

Sorry, the viewpoint that BigInt is a workaround for your personal hobby horse
(integer overflow) has ABSOLUTELY ZERO support from me.
BigInt is for arithemetic on big integers. It is not for "freeing the
programmers mind" of overflow.
A type that you can be used as a drop-in replacement for integers but will warn
of overflow, is 100 times simpler than BigInt. Why don't you just write it?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #8 from bearophile_hugs@eml.cc 2011-03-23 16:40:37 PDT ---
(In reply to comment #7)

> They are not system languages. The comparison is irrelevant.

Well, Lisp was used plenty as a system language. D wants to be a multi-purpose language, and it already has a multi-precision library, and I see no harm in using this library for purposes not anticipated by the BigInt author.


> A type that you can be used as a drop-in replacement for integers but will warn of overflow, is 100 times simpler than BigInt. Why don't you just write it?

Often I don't just want to watch for overflows, I'd also like the program to give a correct answer if for mistake one intermediate computation needs 70 bits long integers (and I don't know it). In the Project Euler (http://projecteuler.net/ ) there are usually ways to avoid multi-precision numbers, but if you are not careful it's not hard to have larger intermediate values. In this case 64 bit values give wrong results, while the small programs in Python give the correct result.

ShedSkin is a Python-->C++ compiler, recently it has added support for 64 bit integers too, this has allowed it to compile 131 out of 204 Python Euler solutions: http://shed-skin.blogspot.com/2010/05/shedskin-versus-psyco-for-131-project.html

Most of the solutions that can't be compiled with ShedSkin require multi-precision numbers. Often the final result is a 32 bit number, but intermediate values are larger than 64 bit, and ShedSkin gives a wrong result on them. This is an example why multi-precision computations are useful, to produce correct results. The point here is that overflow errors are not enough.

Thank you for your answers Don, and sorry for my insistent nature :-) Feel free to close this bug report when you see it fit.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #9 from bearophile_hugs@eml.cc 2011-05-09 15:23:08 PDT ---
See a working version, and the workarounds used: http://rosettacode.org/wiki/Ackermann_function#D

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------