On 02/02/2012 05:28 PM, xancorreu wrote:
> I get "segment violation" error with ./factorial 400000
> How can I resolve it?
>
> My code is:
>
> import std.stdio, std.bigint, std.string, std.conv, std.stream;
>
> BigInt recFactorial(int n) {
> if (n == 0)
> return BigInt(1);
> else
> return (BigInt(n) * recFactorial(n - 1));
> }
>
> void main(string[] args) {
> if (args.length != 2)
> writeln("Factorial requires a number");
> else
> try {
> writeln(recFactorial(std.conv.to!int(args[1])));
> } catch {
> writeln("Error");
> }
> }
>
>
>
> Thanks a lot,

import std.stdio, std.bigint, std.conv;

BigInt factorial(int n) {
    BigInt result=1;
    foreach(i;1..n) result*=i;
    return result;
}

void main(string[] args) {
    if (args.length != 2)
        writeln("Factorial requires a number");
    else
        try {
            writeln(factorial(std.conv.to!int(args[1])));
        } catch {
            writeln("Error");
        }
}

On Thu, Feb 02, 2012 at 10:55:06PM +0100, Timon Gehr wrote:
> On 02/02/2012 08:04 PM, xancorreu wrote:
[...]
> >For the other hand, how can increase the stack in linux?
[...]
> 
> I don't know, but it is best to just rewrite the code so that it does not use recursion.
> 
> (This kind of problem is exactly the reason why any language standard should mandate tail call optimization.)

Doesn't help badly-chosen implementations like:

	int fib(int n) {
		if (n <= 2) return 1;
		else return fib(n-2) + fib(n+1);
	}

There's not much the compiler can do to offset programmers choosing the wrong algorithm for the job. It can't replace educating programmers to not implement things a certain way unless they have to.


T

-- 
Philosophy: how to make a career out of daydreaming.

On Thu, Feb 02, 2012 at 02:47:22PM -0800, H. S. Teoh wrote: [...]
> 	int fib(int n) {
> 		if (n <= 2) return 1;
> 		else return fib(n-2) + fib(n+1);
[...]

Ugh. That should be fib(n-1), not fib(n+1). But no matter, such a thing
shouldn't ever be actually written and compiled, as Andrei says. :)


T

-- 
Change is inevitable, except from a vending machine.

On 02/02/2012 11:47 PM, H. S. Teoh wrote:
> On Thu, Feb 02, 2012 at 10:55:06PM +0100, Timon Gehr wrote:
>> On 02/02/2012 08:04 PM, xancorreu wrote:
> [...]
>>> For the other hand, how can increase the stack in linux?
> [...]
>>
>> I don't know, but it is best to just rewrite the code so that it does
>> not use recursion.
>>
>> (This kind of problem is exactly the reason why any language standard
>> should mandate tail call optimization.)
>
> Doesn't help badly-chosen implementations like:
>
> 	int fib(int n) {
> 		if (n<= 2) return 1;
> 		else return fib(n-2) + fib(n+1);
> 	}
>

This is not a tail-recursive function. And neither is recFactorial, my bad. Anyway, my point was that the compiler should not generate code that blows up on a (in principle) perfectly sane implementation.

> There's not much the compiler can do to offset programmers choosing the
> wrong algorithm for the job.

Agreed.

> It can't replace educating programmers to
> not implement things a certain way unless they have to.
>
>
> T
>

Or unless they feel like it.

LList!ulong fib(){
    LList!ulong r;
    r=cons(st(1UL),cons(st(1UL),lz(()=>zipWith((Lazy!ulong a, Lazy!ulong b)=>lz(()=>a+b),r,r.tail)())));
    return r;
}

xancorreu:

> But you "only" put a "in" in recFactorial function argument. What this mean? **Why** this is more efficient than mine?

It wasn't meant to improve performance. "in" turns a function argument to "input only" (and eventually scoped too). Generally when you program in D2 it's a good practice to use immutability where you can and where this doesn't cause other performance or typing problems. Immutability avoids bugs, allows a stronger purity (and I have seen DMD is often able to compiler a little more efficient program if you use immutability/constants everywhere they are a good fit). So 95% of the arguments of your program are better tagged with "in".

Bye,
bearophile

On Thursday, February 02, 2012 18:14:25 bearophile wrote:
> xancorreu:
> > But you "only" put a "in" in
> > recFactorial function argument. What this mean? **Why** this is more
> > efficient than mine?
> 
> It wasn't meant to improve performance. "in" turns a function argument to "input only" (and eventually scoped too). Generally when you program in D2 it's a good practice to use immutability where you can and where this doesn't cause other performance or typing problems. Immutability avoids bugs, allows a stronger purity (and I have seen DMD is often able to compiler a little more efficient program if you use immutability/constants everywhere they are a good fit). So 95% of the arguments of your program are better tagged with "in".

in is pointless on value types. All it does is make the function parameter const, which really doesn't do much for you, and in some instances, is really annoying. Personally, I see no point in using in unless the parameter is a reference type, and even then, it's often a bad idea with reference types, because in is really const scope, and the scope is problematic if you want to return anything from that variable. It's particularly problematic with arrays, since it's frequently desirable to return slices of them, and scope (and therefore in) would prevent that. It's useful in some instances (particularly with delegates), but I'd use in _very_ sparingly. It's almost always more trouble than it's worth IMHO.

- Jonathan M Davis

On 02/02/2012 03:10 PM, Timon Gehr wrote:

> LList!ulong fib(){
> LList!ulong r;
> r=cons(st(1UL),cons(st(1UL),lz(()=>zipWith((Lazy!ulong a, Lazy!ulong
> b)=>lz(()=>a+b),r,r.tail)())));
> return r;
> }

Sorry, wrong newsgroup. alt.comp.lang.perl is around the corner. :p

Ali

On Fri, Feb 03, 2012 at 12:10:01AM +0100, Timon Gehr wrote: [...]
> LList!ulong fib(){
>     LList!ulong r;
>     r=cons(st(1UL),cons(st(1UL),lz(()=>zipWith((Lazy!ulong a,
> Lazy!ulong b)=>lz(()=>a+b),r,r.tail)())));
>     return r;
> }

Whoa. A caching recursive definition of fibonacci. Impressive!

Now I wonder if we can do this with the Ackermann function... ;-)


T

-- 
"640K ought to be enough" -- Bill G., 1984.
"The Internet is not a primary goal for PC usage" -- Bill G., 1995.
"Linux has no impact on Microsoft's strategy" -- Bill G., 1999.

On Thu, Feb 02, 2012 at 03:26:52PM -0800, Ali Çehreli wrote:
> 
> On 02/02/2012 03:10 PM, Timon Gehr wrote:
> 
> > LList!ulong fib(){
> > LList!ulong r;
> > r=cons(st(1UL),cons(st(1UL),lz(()=>zipWith((Lazy!ulong a, Lazy!ulong
> > b)=>lz(()=>a+b),r,r.tail)())));
> > return r;
> > }
> 
> Sorry, wrong newsgroup. alt.comp.lang.perl is around the corner. :p
[...]

You mean alt.comp.lang.lisp. :-)


T

-- 
Why waste time learning, when ignorance is instantaneous? -- Hobbes, from Calvin & Hobbes

On 02/03/12 00:20, Jonathan M Davis wrote:
> in is pointless on value types. All it does is make the function parameter const, which really doesn't do much for you, and in some instances, is really annoying. Personally, I see no point in using in unless the parameter is a reference type, and even then, it's often a bad idea with reference types, because in is really const scope, and the scope is problematic if you want to return anything from that variable. It's particularly problematic with arrays, since it's frequently desirable to return slices of them, and scope (and therefore in) would prevent that. It's useful in some instances (particularly with delegates), but I'd use in _very_ sparingly. It's almost always more trouble than it's worth IMHO.

BTW, scope should have been the default for *all* reference type function arguments, with an explicit modifier, say "esc", required to let the thing escape. It's an all-or-nothing thing, just like immutable strings - not using it everywhere is painful, but once you switch everything over you get the benefits.

If it isn't obvious why - GC. The compiler can optimize the cases where it knows a newly allocated object can't escape and reduce or omit the GC overhead. And yes, it can also do this automatically - but that requires analyzing the whole call chain, which is a) not always possible and b) much more expensive.

artur