www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Segfault games with factorials

reply "Darren" <darrenhobbs mac.com> writes:
I have the following code in fac.d (modified from the factorial 
examples on RosettaCode):


import std.bigint;

pure BigInt factorial(BigInt n) {
     static pure BigInt inner(BigInt n, BigInt acc) {
     	return n == 0 ? acc : inner(n - 1, acc * n);
     }
     return inner(n, BigInt("1"));
}

void main(string[] args) {
	import std.stdio;
	BigInt input = args[1];
	writeln(factorial(input));
	return;
}

It (more or less consistently) on my machine will calculate 'fac 
47610', and (more or less consistently) will core dump with a 
segfault on 'fac 47611'.

Interestingly, if I redirect stdout to a file it will usually 
manage to get to 47612.

To satisfy my own curiosity about what's happening, are there any 
resources I can use to analyse the core dump?

Thanks.
Jul 24 2014
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jul 24, 2014 at 01:14:40PM +0000, Darren via Digitalmars-d-learn wrote:

 I have the following code in fac.d (modified from the factorial
 examples on RosettaCode):
 

 import std.bigint;
 
 pure BigInt factorial(BigInt n) {
     static pure BigInt inner(BigInt n, BigInt acc) {
     	return n == 0 ? acc : inner(n - 1, acc * n);
     }
     return inner(n, BigInt("1"));
 }
 
 void main(string[] args) {
 	import std.stdio;
 	BigInt input = args[1];
 	writeln(factorial(input));
 	return;
 }
 
 It (more or less consistently) on my machine will calculate 'fac
 47610', and (more or less consistently) will core dump with a segfault
 on 'fac 47611'.


[...]

You're probably running out of stack space because of your recursive
function. Write it as a loop instead, and you should be able to go
farther:

	pure BigInt factorial(BigInt n) {
		auto result = BigInt(1);
		while (n > 1)
			result *= n;
		return result;
	}


T

-- 
Ignorance is bliss... until you suffer the consequences!
Jul 24 2014
parent reply "Darren" <darrenhobbs mac.com> writes:
On Thursday, 24 July 2014 at 14:39:12 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 On Thu, Jul 24, 2014 at 01:14:40PM +0000, Darren via 
 Digitalmars-d-learn wrote:

 I have the following code in fac.d (modified from the factorial
 examples on RosettaCode):
 

 import std.bigint;
 
 pure BigInt factorial(BigInt n) {
     static pure BigInt inner(BigInt n, BigInt acc) {
     	return n == 0 ? acc : inner(n - 1, acc * n);
     }
     return inner(n, BigInt("1"));
 }
 
 void main(string[] args) {
 	import std.stdio;
 	BigInt input = args[1];
 	writeln(factorial(input));
 	return;
 }
 
 It (more or less consistently) on my machine will calculate 
 'fac
 47610', and (more or less consistently) will core dump with a 
 segfault
 on 'fac 47611'.


 [...]

 You're probably running out of stack space because of your 
 recursive
 function. Write it as a loop instead, and you should be able to 
 go
 farther:

 	pure BigInt factorial(BigInt n) {
 		auto result = BigInt(1);
 		while (n > 1)
 			result *= n;
 		return result;
 	}


 T


It does seem that's the case. Which is odd, as I thought that DMD 
and LDC did TCO. Not in this case obviously.

PS. This was a slightly silly program, but in the general case, 
is there a way to use a core dump to diagnose a stack overflow?
Jul 24 2014
next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 24 July 2014 at 14:59:16 UTC, Darren wrote:

 On Thursday, 24 July 2014 at 14:39:12 UTC, H. S. Teoh via 
 Digitalmars-d-learn wrote:

 On Thu, Jul 24, 2014 at 01:14:40PM +0000, Darren via 
 Digitalmars-d-learn wrote:

 I have the following code in fac.d (modified from the 
 factorial
 examples on RosettaCode):
 

 import std.bigint;
 
 pure BigInt factorial(BigInt n) {
    static pure BigInt inner(BigInt n, BigInt acc) {
    	return n == 0 ? acc : inner(n - 1, acc * n);
    }
    return inner(n, BigInt("1"));
 }
 
 void main(string[] args) {
 	import std.stdio;
 	BigInt input = args[1];
 	writeln(factorial(input));
 	return;
 }
 
 It (more or less consistently) on my machine will calculate 
 'fac
 47610', and (more or less consistently) will core dump with a 
 segfault
 on 'fac 47611'.


 [...]

 You're probably running out of stack space because of your 
 recursive
 function. Write it as a loop instead, and you should be able 
 to go
 farther:

 	pure BigInt factorial(BigInt n) {
 		auto result = BigInt(1);
 		while (n > 1)
 			result *= n;
 		return result;
 	}


 T


 It does seem that's the case. Which is odd, as I thought that 
 DMD and LDC did TCO. Not in this case obviously.

 PS. This was a slightly silly program, but in the general case, 
 is there a way to use a core dump to diagnose a stack overflow?


A debugger should be able to tell you why the segfault occurred.
Jul 24 2014
prev sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Thursday, 24 July 2014 at 14:59:16 UTC, Darren wrote:

 It does seem that's the case. Which is odd, as I thought that 
 DMD and LDC did TCO. Not in this case obviously.


DMD doesn't do it with the :? operator: 
https://issues.dlang.org/show_bug.cgi?id=3713
Jul 24 2014