Function that calculates in compile time when it can

[Philippe Sigaud]

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!