digitalmars.D.bugs - [Issue 2289] New: Stack overflow on very large BigInt to string.
- d-bugmail puremagic.com (31/31) Aug 17 2008 http://d.puremagic.com/issues/show_bug.cgi?id=2289
- d-bugmail puremagic.com (12/12) Aug 17 2008 http://d.puremagic.com/issues/show_bug.cgi?id=2289
- d-bugmail puremagic.com (5/5) Aug 17 2008 http://d.puremagic.com/issues/show_bug.cgi?id=2289
- d-bugmail puremagic.com (8/29) Aug 18 2008 http://d.puremagic.com/issues/show_bug.cgi?id=2289
- d-bugmail puremagic.com (4/4) Sep 02 2008 http://d.puremagic.com/issues/show_bug.cgi?id=2289
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
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
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
http://d.puremagic.com/issues/show_bug.cgi?id=2289import 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
http://d.puremagic.com/issues/show_bug.cgi?id=2289 Fixed dmd 2.019 --
Sep 02 2008