[Issue 5765] ^^ and << with BigInts

[d-bugmail at puremagic.com]

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



--- Comment #2 from bearophile_hugs at 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: -------