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