Function that calculates in compile time when it can

Minas Mina minas_mina1990 at hotmail.co.uk
Mon Aug 6 08:25:21 PDT 2012


On Monday, 6 August 2012 at 15:21:38 UTC, Philippe Sigaud wrote:
> On Mon, Aug 6, 2012 at 3:54 PM, Minas Mina 
> <minas_mina1990 at hotmail.co.uk> wrote:
>> Something like this:
>>
>>
>> template fib(ulong n)
>> {
>>         static if( n < 2 )
>>                 const fib = n;
>>         else
>>                 const fib = fib!(n-1) + fib!(n-2);
>>
>>         if( n < 2)
>>                 return n;
>>         return fib(n-1) + fib(n-2);
>> }
>>
>> It doesn't work of course, as I am in a template and trying to 
>> "return"
>> something.
>>
>> CTFE? Is that "compile time function evaluation"? If yes, it's 
>> really
>> slow...
>
>> If I try:
>> static x = fib(40); // fib is a normal function
>>
>> it takes forever and makes my pc run really slowly.
>
> Well, you're using the worst possible algorithm to calculate 
> Fibonacci
> (exponential time), so it's no wonder it's taking foverer :)
> Then, you've to know that CT calculation is far slower than 
> runtime
> calculation. My experience on this is about an order of 
> magnitude
> slower, and even more. On the machine I'm currently on, fib(30) 
> is
> calculated instantaneously at runtime, but it takes 4-6s at CT.
> Fib(40) aloready takes 4-6 s at runtime, so I won't test at CT 
> :)
>
> To come back to your question. __ctfe should be used with a 
> standard
> (non-static) if.
> Here I implement to Fibonacci algos, one linear in n at CT, one
> exponential ar RT.
> That's just to show that a good algo at CT can run circles 
> around a
> bad algo at RT.
> At compile-time, getting fib(100) is instantaneous, while 
> getting only
> fib(40) at RT takes a few seconds on my machine.
>
> import std.conv: to;
> import std.stdio;
>
> long fib(size_t n)
> {
> 	if(__ctfe) // compile-time, linear, sustained development
> 	{
> 		long[] temp = new long[](n+1); // dynamic array during CTFE, 
> D rox
> 		temp[0] = 1;
> 		temp[1] = 1;
> 		size_t p = 1;
> 		while (p < n)
> 		{
> 			++p;
> 			temp[p] = temp[p-1]+temp[p-2];
> 		}
> 		return -temp[p]; // '-' as an indication that this indeed 
> took place at CT
> 	}
> 	else // runtime, exponential, woohoo baby!
> 	{	
> 		if (n == 0 || n == 1)
> 		        return 1;
> 		else
> 			return fib(n-1)+fib(n-2);
> 	}
> }
>
> void main()
> {
> 	enum f1 = fib(100); // CT
> 	pragma(msg, "At CT, fib(100) = " ~to!string(f1)); // will be < 
> 0 as a flag
> 	auto f2 = fib(40); // RT
> 	writeln("At RT, fib(40) = ", f2);
> }
>
> Don't try fib(100) at runtime!

Thank you for your reply!

Haha, yeah, I knew I was using the worst possible algorithm. I


More information about the Digitalmars-d-learn mailing list