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

           Summary: Stack overflow on very large BigInt to string.
           Product: D
           Version: 2.018
          Platform: PC
        OS/Version: Windows
            Status: NEW
          Severity: minor
          Priority: P4
         Component: Phobos
        AssignedTo: bugzilla@digitalmars.com
        ReportedBy: dsimcha@yahoo.com


import std.stdio, std.bigint;

void main() {
    auto result = factorial(10_000);
    writefln(stderr, "Calculated 10,000!");  //Works to this point.
    auto resultString = result.toString;  //Generates stack overflow.
}

BigInt factorial(uint N) {
    BigInt result = 1;
    for(uint i = 2; i <= N; i++) {
        result *= i;
    }
    return result;
}

Seems to happen at ~20k to 25k decimal digits.

A fairly minor bug, since it is very unlikely that too many people will run into it. (I only found it because I was testing the speed of std.bigint on very large numbers.)  If this can't be fixed easily, maybe just a better error message such as "Error:  Too many digits." would be good enough.


-- 

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


andrei@metalanguage.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED




------- Comment #1 from andrei@metalanguage.com  2008-08-17 14:58 -------
Thanks for the report. I could not reproduce the bug, but looked over the implementation of toString and it uses O(N) stack gratuitously. I replaced that implementation, and I'm pretty sure it solves the issue, so I'll preemptively close the bug.


-- 

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





------- Comment #2 from andrei@metalanguage.com  2008-08-17 15:07 -------
Oh, and I committed that to svn, so you can get and build phobos from dsource if in a hurry.


-- 

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





------- Comment #3 from clugdbug@yahoo.com.au  2008-08-18 03:38 -------
(In reply to comment #0)
> import std.stdio, std.bigint;
> 
> void main() {
>     auto result = factorial(10_000);
>     writefln(stderr, "Calculated 10,000!");  //Works to this point.
>     auto resultString = result.toString;  //Generates stack overflow.
> }
> 
> BigInt factorial(uint N) {
>     BigInt result = 1;
>     for(uint i = 2; i <= N; i++) {
>         result *= i;
>     }
>     return result;
> }
> 
> Seems to happen at ~20k to 25k decimal digits.
> 
> A fairly minor bug, since it is very unlikely that too many people will run into it. (I only found it because I was testing the speed of std.bigint on very large numbers.)

You'll find the speed of std.bigint is pretty awful. But don't worry, it will improve _signficantly_. The version in Tango (work in progress) is 40X faster for small numbers, rising to 100s of times faster as the number of digits increases.


-- 

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





------- Comment #4 from bugzilla@digitalmars.com  2008-09-03 01:41 -------
Fixed dmd 2.019


--