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_mina1...@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. It
was just for testing... I'm never going to use ctfe with
algorithms of that complexity again!
Ok, so I can use if(__ctfe) to define different behaviour(or not)
at compile time than at runtime. The way I want to use it,
however, I don't have to:
import std.stdio;
void main()
{
ulong f1 = fibonacci(50); // calculated at runtime
static f2 = fibonacci(50); // calculated at compile time
writeln(f);
}
// calcuated at O(1) woohoo!
ulong fibonacci(ulong n)
{
import std.math;
double
r0 = (1 + sqrt(5.0)) / 2.0,
r1 = (1 - sqrt(5.0)) / 2.0,
a = 1.0 / sqrt(5.0),
b = -1.0 / sqrt(5.0);
// fn = a*r0 + b*r1
return cast(ulong)(a * pow(r0, cast(double)n) + b * pow(r1,
cast(double)n));
}
What I was really looking for was to do something like the way
std.math.sin works. I read somewhere that if the argument is
available at compile time, it evaluates the result at compile
time.
So, if I do:
double f = sin(0.5); // calculated at compile time or not?
If it is calculated at compile time, how do I do it for my own
functions?
If not, I guess the only way is to use static or enum like you
guys showed me.
