Jump to page: 1 2 3
Thread overview
Function that calculates in compile time when it can
Aug 06, 2012
Minas Mina
Aug 06, 2012
Tobias Pankrath
Aug 06, 2012
Minas Mina
Aug 06, 2012
Philippe Sigaud
Aug 06, 2012
Minas Mina
Aug 06, 2012
Minas Mina
Aug 06, 2012
Philippe Sigaud
Aug 06, 2012
Namespace
Aug 06, 2012
Minas Mina
Aug 06, 2012
Eyyub
Aug 06, 2012
Eyyub
Aug 06, 2012
Philippe Sigaud
Aug 06, 2012
Russel Winder
Aug 06, 2012
Philippe Sigaud
Aug 06, 2012
Andrej Mitrovic
Aug 06, 2012
Eyyub
Aug 06, 2012
Minas Mina
Aug 06, 2012
Tobias Pankrath
Aug 06, 2012
Artur Skawina
Aug 07, 2012
Marco Leise
Aug 08, 2012
Artur Skawina
August 06, 2012
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).
August 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 instead of a template?

You can check for compile time with

static if(__ctfe)
August 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.
August 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. :/
August 06, 2012
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 had been defined as:

   enum T n = 42;

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

artur
August 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?
August 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
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!
August 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.

August 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
> 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
August 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
> 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.
« First   ‹ Prev
1 2 3