Function that calculates in compile time when it can
Minas Mina
minas_mina1990 at hotmail.co.uk
Mon Aug 6 08:33:51 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. 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.
More information about the Digitalmars-d-learn
mailing list