www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 2289] New: Stack overflow on very large BigInt to string.

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


--
Aug 17 2008
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2289


andrei metalanguage.com changed:

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





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.


--
Aug 17 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2289






Oh, and I committed that to svn, so you can get and build phobos from dsource
if in a hurry.


--
Aug 17 2008
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2289








 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.


--
Aug 18 2008
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2289






Fixed dmd 2.019


--
Sep 02 2008