digitalmars.D.learn - Function that calculates in compile time when it can

• Minas Mina (14/14) Aug 06 2012 I want to write a fibonacci(n) function that calculates the
• Tobias Pankrath (5/20) Aug 06 2012 What exactly do you try to accomplish? Why can't you use CTFE
• Minas Mina (19/19) Aug 06 2012 Something like this:
• Philippe Sigaud (49/67) Aug 06 2012 Well, you're using the worst possible algorithm to calculate Fibonacci
• Minas Mina (3/90) Aug 06 2012 Thank you for your reply!
• Minas Mina (40/127) Aug 06 2012 Thank you for your reply!
• Philippe Sigaud (16/20) Aug 06 2012 I wonder if there is any rounding error going on with these pow, but
• Namespace (2/2) Aug 06 2012 Take a look into std.math:
• Minas Mina (18/20) Aug 06 2012 I found this:
• Eyyub (6/26) Aug 06 2012 Justly, you see a normal runtime function, and a CTFE function is
• Eyyub (2/6) Aug 06 2012 *compile time, sorry
• Philippe Sigaud (21/26) Aug 06 2012 Oh, I thought they were implemented as polynomial approximations.
• Russel Winder (17/20) Aug 06 2012 Memoization is a bit of a help it destroying that problem.
• Philippe Sigaud (7/12) Aug 06 2012 Memoization at compile-time is a bit tricky, though.
• Andrej Mitrovic (4/6) Aug 06 2012 I think TDPL had some use of the memoize template and used fibonacci
• Eyyub (6/8) Aug 06 2012 No, you can't.
• Minas Mina (12/21) Aug 06 2012 It's Ubuntu 12.04 running on an Intel i5.
• Tobias Pankrath (5/15) Aug 06 2012 That algorithm makes O(2^n) calls to fib. I think templates get
• Artur Skawina (16/33) Aug 06 2012 He wants the function to be evaluated at compile time if that is possibl...
• Marco Leise (5/21) Aug 07 2012 That's easy: http://dpaste.dzfl.pl/521f47a0
• Artur Skawina (25/46) Aug 08 2012 It's not a function, but a template - meaning not only does it require
```I want to write a fibonacci(n) function that calculates the
result.
a) if n is known at compile time, use a template
b) if not, use a normal function

I know how to write a template version:
template fib(ulong n)
{
static if( n < 2 )
const fib = n;
else
const fib = fib!(n-1) + fib!(n-2);
}

But how can I 'know' if n is known at compile time to make it use
the other version? (which I won't post 'cause it is fairly easy).
```
Aug 06 2012
```On Monday, 6 August 2012 at 12:21:38 UTC, Minas Mina wrote:
I want to write a fibonacci(n) function that calculates the
result.
a) if n is known at compile time, use a template
b) if not, use a normal function

I know how to write a template version:
template fib(ulong n)
{
static if( n < 2 )
const fib = n;
else
const fib = fib!(n-1) + fib!(n-2);
}

But how can I 'know' if n is known at compile time to make it
use the other version? (which I won't post 'cause it is fairly
easy).

What exactly do you try to accomplish? Why can't you use CTFE

You can check for compile time with

static if(__ctfe)
```
Aug 06 2012
```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.
```
Aug 06 2012
```On Mon, Aug 6, 2012 at 3:54 PM, Minas Mina <minas_mina1990 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
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 = 1;
temp = 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!
```
Aug 06 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 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
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 = 1;
temp = 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!

Haha, yeah, I knew I was using the worst possible algorithm. I
```
Aug 06 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 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
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 = 1;
temp = 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!

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.
```
Aug 06 2012
```On Mon, Aug 6, 2012 at 5:33 PM, Minas Mina <minas_mina1990 hotmail.co.uk> wrote:

// calcuated at O(1) woohoo!

return cast(ulong)(a * pow(r0, cast(double)n) + b * pow(r1,

I wonder if there is any rounding error going on with these pow, but
yes, even better this way.

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?

sin is a library function, it has no special rights your own function
doesn't as far as I know.

I'd say, put an if(__ctfe) in sin:

if (__ctfe)
{
pragma(msg, "Yep, CT");
return 2.0;
}
else
{
// standard sin code
}

And tell us the result :)
```
Aug 06 2012
```Take a look into std.math:
https://github.com/D-Programming-Language/phobos/blob/master/std/math.d
```
Aug 06 2012
```On Monday, 6 August 2012 at 15:56:52 UTC, Namespace wrote:
Take a look into std.math:
https://github.com/D-Programming-Language/phobos/blob/master/std/math.d

I found this:

real sin(real x)  safe pure nothrow; /* intrinsic */

And these:

creal sin(creal z)  safe pure nothrow
{
creal cs = expi(z.re);
creal csh = coshisinh(z.im);
return cs.im * csh.re + cs.re * csh.im * 1i;
}

/** ditto */
ireal sin(ireal y)  safe pure nothrow
{
return cosh(y.im)*1i;
}

I don't see anything about ctfe. Maybe I didn't understand well
and sin is not evaluated at compile time. Can someone clarify
this?
```
Aug 06 2012
```On Monday, 6 August 2012 at 16:17:22 UTC, Minas Mina wrote:
On Monday, 6 August 2012 at 15:56:52 UTC, Namespace wrote:
Take a look into std.math:
https://github.com/D-Programming-Language/phobos/blob/master/std/math.d

I found this:

real sin(real x)  safe pure nothrow; /* intrinsic */

And these:

creal sin(creal z)  safe pure nothrow
{
creal cs = expi(z.re);
creal csh = coshisinh(z.im);
return cs.im * csh.re + cs.re * csh.im * 1i;
}

/** ditto */
ireal sin(ireal y)  safe pure nothrow
{
return cosh(y.im)*1i;
}

I don't see anything about ctfe. Maybe I didn't understand well
and sin is not evaluated at compile time. Can someone clarify
this?

Justly, you see a normal runtime function, and a CTFE function is
a normal runtime function(with some restrictions) that can be
interpreted at runtime.

static res = sin(4); //compile time
auto res = sin(4); //runtime
```
Aug 06 2012
```On Monday, 6 August 2012 at 16:21:04 UTC, Eyyub wrote:
Justly, you see a normal runtime function, and a CTFE function
is
a normal runtime function(with some restrictions) that can be
interpreted at runtime.

*compile time, sorry
```
Aug 06 2012    Philippe Sigaud <philippe.sigaud gmail.com> writes:
```On Mon, Aug 6, 2012 at 6:17 PM, Minas Mina <minas_mina1990 hotmail.co.uk> wrote:

I found this:

real sin(real x)  safe pure nothrow; /* intrinsic */

I don't see anything about ctfe. Maybe I didn't understand well
and sin is not evaluated at compile time. Can someone clarify
this?

Oh, I thought they were implemented as polynomial approximations.

Never mind, you can test it with any function:

int foo(int i)
{
if (__ctfe)
{
pragma(msg, "CT");
return -1;
}
else
return 1;
}

void main()
{
auto i = foo(0);
static j = foo(0);
writeln(i); // 1
writeln(j); // -1
}

So, auto i doesn't provoke CT-evaluation (else it'd be -1).
```
Aug 06 2012
```On Mon, 2012-08-06 at 17:21 +0200, Philippe Sigaud wrote:
[=E2=80=A6]
Well, you're using the worst possible algorithm to calculate Fibonacci
(exponential time), so it's no wonder it's taking foverer :)

Memoization is a bit of a help it destroying that problem.

[=E2=80=A6]
Don't try fib(100) at runtime!

Of course the real problem is that quants and such folk often need
values of Fibonacci and factorial that cannot be held in an hardware
integer.
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Aug 06 2012
```On Mon, Aug 6, 2012 at 8:37 PM, Russel Winder <russel winder.org.uk> wrote:
On Mon, 2012-08-06 at 17:21 +0200, Philippe Sigaud wrote:
[=E2=80=A6]
Well, you're using the worst possible algorithm to calculate Fibonacci
(exponential time), so it's no wonder it's taking foverer :)

Memoization is a bit of a help it destroying that problem.

Memoization at compile-time is a bit tricky, though.

Which reminds me... What if someone wants Fibonacci values depending
on a runtime value, but would like them to be calculated really fast?
Use the "Sabalausky Trick" (aka Nick's Run-Time to Compile-Time Time
Machine): Pregenerate desired values at compile-time (for example here
in an array), to get O(1) fibonacci access at runtime.
```
Aug 06 2012    Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
```On 8/6/12, Philippe Sigaud <philippe.sigaud gmail.com> wrote:
Which reminds me... What if someone wants Fibonacci values depending
on a runtime value, but would like them to be calculated really fast?

I think TDPL had some use of the memoize template and used fibonacci
as sample code. It even used it internally for a recursive call. It's
somewhere in the book.
```
Aug 06 2012
```On Monday, 6 August 2012 at 13:46:14 UTC, Tobias Pankrath wrote:
You can check for compile time with

static if(__ctfe)

No, you can't.

__ctfe is a "CTFE-ed"(?) value.

But you can do something like that :
http://dpaste.dzfl.pl/e3f26239

Minas : I don't know if your PC is outdated, but it's weird. :/
```
Aug 06 2012
```On Monday, 6 August 2012 at 14:25:29 UTC, Eyyub wrote:
On Monday, 6 August 2012 at 13:46:14 UTC, Tobias Pankrath wrote:
You can check for compile time with

static if(__ctfe)

No, you can't.

__ctfe is a "CTFE-ed"(?) value.

But you can do something like that :
http://dpaste.dzfl.pl/e3f26239

Minas : I don't know if your PC is outdated, but it's weird. :/

It's Ubuntu 12.04 running on an Intel i5.

That's what I tried to calculate:
static x = fib(40);

ulong fib(ulong n)
{
if(n < 2)
return n;
else
return fib(n-1) +  fib(n-2);
}

Maybe because it has a lot of recursion?
```
Aug 06 2012
```On Monday, 6 August 2012 at 15:18:22 UTC, Minas Mina wrote:
That's what I tried to calculate:
static x = fib(40);

ulong fib(ulong n)
{
if(n < 2)
return n;
else
return fib(n-1) +  fib(n-2);
}

Maybe because it has a lot of recursion?

That algorithm makes O(2^n) calls to fib. I think templates get
only expanded
once for every set of parameters, so you get memoization build in
and thus it's faster in this case.
```
Aug 06 2012    Artur Skawina <art.08.09 gmail.com> writes:
```On 08/06/12 15:46, Tobias Pankrath wrote:
On Monday, 6 August 2012 at 12:21:38 UTC, Minas Mina wrote:
I want to write a fibonacci(n) function that calculates the result.
a) if n is known at compile time, use a template
b) if not, use a normal function

I know how to write a template version:
template fib(ulong n)
{
static if( n < 2 )
const fib = n;
else
const fib = fib!(n-1) + fib!(n-2);
}

But how can I 'know' if n is known at compile time to make it use the other
version? (which I won't post 'cause it is fairly easy).

What exactly do you try to accomplish? Why can't you use CTFE instead of a
template?

He wants the function to be evaluated at compile time if that is possible,
but at runtime if that can't be done; and *not* have to handle both cases
in every caller. Which I can't think of any way to do right now.

An "T fib(T)(enum T n)" overload that would enable cases like this (and
bearophiles ranged-integers) to work, has been proposed in the past (only
with 'static' instead of 'enum'; the latter fits better).
IOW a "fib(42)" call would map to more or less:

enum T c = 42;
fib(c);

and inside such an overload the argument 'n' would be treated just like if it

enum T n = 42;

ie it would be cfte'able and /then/ static-if and friends would be able to
handle the rest.

artur
```
Aug 06 2012
```Am Mon, 06 Aug 2012 14:21:37 +0200
schrieb "Minas Mina" <minas_mina1990 hotmail.co.uk>:

I want to write a fibonacci(n) function that calculates the
result.
a) if n is known at compile time, use a template
b) if not, use a normal function

I know how to write a template version:
template fib(ulong n)
{
static if( n < 2 )
const fib = n;
else
const fib = fib!(n-1) + fib!(n-2);
}

But how can I 'know' if n is known at compile time to make it use
the other version? (which I won't post 'cause it is fairly easy).

That's easy: http://dpaste.dzfl.pl/521f47a0

--
Marco
```
Aug 07 2012
```On 08/07/12 19:43, Marco Leise wrote:
Am Mon, 06 Aug 2012 14:21:37 +0200
schrieb "Minas Mina" <minas_mina1990 hotmail.co.uk>:

I want to write a fibonacci(n) function that calculates the
result.
a) if n is known at compile time, use a template
b) if not, use a normal function

I know how to write a template version:
template fib(ulong n)
{
static if( n < 2 )
const fib = n;
else
const fib = fib!(n-1) + fib!(n-2);
}

But how can I 'know' if n is known at compile time to make it use
the other version? (which I won't post 'cause it is fairly easy).

That's easy: http://dpaste.dzfl.pl/521f47a0

It's not a function, but a template - meaning not only does it require
a different syntax, but also that it can only be used with literals and
symbols. Ie 'fib!(expression_not_evaluable_at_ct)' like 'fib!(variable+1)'
will fail to compile.

artur

PS. Your code does not work with older compilers (like the 2.057 based
gdc that i'm using); this version works and is also more readable:

template isSymbol(alias S) {
enum isSymbol = __traits(compiles, __traits(parent, S));
}

template fib(alias N) {
static if (isSymbol!N) {
property typeof(N+N) fib(typeof(N) N = N) {
return N<2 ? N : fib(N-1)+fib(N-2);
}
}
else {
static if (N<2)
alias N fib;
else
enum fib = fib!(N-1)+fib!(N-2);
}
}
```
Aug 08 2012