On Monday, 6 August 2012 at 15:21:38 UTC, Philippe Sigaud wrote:
On Mon, Aug 6, 2012 at 3:54 PM, Minas Mina
<[email protected]> 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
