www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5765] New: ^^ and << with BigInts

reply d-bugmail puremagic.com writes:
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



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: -------
Mar 21 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765


Don <clugdbug yahoo.com.au> changed:

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



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: -------
Mar 22 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765




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: -------
Mar 22 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765




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: -------
Mar 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765







 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: -------
Mar 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765







 

 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: -------
Mar 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765







 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: -------
Mar 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765







 

 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: -------
Mar 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765







 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: -------
Mar 23 2011
prev sibling parent reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5765




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: -------
May 09 2011
parent reply "Stian Pedersen" <stian.pedersen gmail.com> writes:
Hi

Whats the status on a BigInt implementation of modular 
exponentiation?
May 03 2012
parent bearophile <bearophileHUGS lycos.com> writes:
Stian Pedersen:


 Whats the status on a BigInt implementation of modular 
 exponentiation?


Better to ask such questions in D.learn.
The answer: I think there is no code yet to perform powmod efficiently in
Phobos.

Bye,
bearophile
May 03 2012