Hi,

I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd

That works for small number but after i got an error about limit recursion

how to work around this in my case ?

bioinfornatics:

> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>
> That works for small number but after i got an error about limit recursion

Instead of template recursion, have you tried regular code run at compile time?

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Bye,
bearophile

On Tuesday, 26 November 2013 at 20:29:00 UTC, bearophile wrote:
> bioinfornatics:
>
>> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>>
>> That works for small number but after i got an error about limit recursion
>
> Instead of template recursion, have you tried regular code run at compile time?
>
> http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
>
> Bye,
> bearophile

Thanks i will take a look

On Tuesday, 26 November 2013 at 20:50:13 UTC, bioinfornatics wrote:
> On Tuesday, 26 November 2013 at 20:29:00 UTC, bearophile wrote:
>> bioinfornatics:
>>
>>> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>>>
>>> That works for small number but after i got an error about limit recursion
>>
>> Instead of template recursion, have you tried regular code run at compile time?
>>
>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
>>
>> Bye,
>> bearophile
>
> Thanks i will take a look

this one seem to be interesting http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup

is like i do but use a table than me i used a recursive way. I go to try it :-)

On 2013-11-26 21:00:56 +0000, bioinfornatics said:

> On Tuesday, 26 November 2013 at 20:50:13 UTC, bioinfornatics wrote:
>> On Tuesday, 26 November 2013 at 20:29:00 UTC, bearophile wrote:
>>> bioinfornatics:
>>> 
>>>> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>>>> 
>>>> That works for small number but after i got an error about limit recursion
>>> 
>>> Instead of template recursion, have you tried regular code run at compile time?
>>> 
>>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
>>> 
>>> Bye,
>>> bearophile
>> 
>> Thanks i will take a look
> 
> this one seem to be interesting http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
> 
> is like i do but use a table than me i used a recursive way. I go to try it :-)

I think you just have a bug in your template code not terminating.   At most you should execute 4 times.   I think there's a problem with casting down from byte to bool.

However, not user if LesserType is what you're after, but this works:

template log2(ulong x)
{
 static if( x >> 8 )
 {
   enum log2 = log2!(x >> 8) + 8;
 }
 else static if( x >> 1)
 {
   enum log2 = log2!(x>>1) + 1;
 } else
 {
   enum log2 = 1;
 }
}

On Tuesday, 26 November 2013 at 21:18:29 UTC, Shammah Chancellor wrote:
> On 2013-11-26 21:00:56 +0000, bioinfornatics said:
>
>> On Tuesday, 26 November 2013 at 20:50:13 UTC, bioinfornatics wrote:
>>> On Tuesday, 26 November 2013 at 20:29:00 UTC, bearophile wrote:
>>>> bioinfornatics:
>>>> 
>>>>> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>>>>> 
>>>>> That works for small number but after i got an error about limit recursion
>>>> 
>>>> Instead of template recursion, have you tried regular code run at compile time?
>>>> 
>>>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
>>>> 
>>>> Bye,
>>>> bearophile
>>> 
>>> Thanks i will take a look
>> 
>> this one seem to be interesting http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
>> 
>> is like i do but use a table than me i used a recursive way. I go to try it :-)
>
> I think you just have a bug in your template code not terminating.   At most you should execute 4 times.   I think there's a problem with casting down from byte to bool.
>
> However, not user if LesserType is what you're after, but this works:
>
> template log2(ulong x)
> {
>  static if( x >> 8 )
>  {
>    enum log2 = log2!(x >> 8) + 8;
>  }
>  else static if( x >> 1)
>  {
>    enum log2 = log2!(x>>1) + 1;
>  } else
>  {
>    enum log2 = 1;
>  }
> }

Thanks your way is much easier to write, works fine :-)

On 2013-11-26 21:31:55 +0000, bioinfornatics said:

> On Tuesday, 26 November 2013 at 21:18:29 UTC, Shammah Chancellor wrote:
>> On 2013-11-26 21:00:56 +0000, bioinfornatics said:
>> 
>>> On Tuesday, 26 November 2013 at 20:50:13 UTC, bioinfornatics wrote:
>>>> On Tuesday, 26 November 2013 at 20:29:00 UTC, bearophile wrote:
>>>>> bioinfornatics:
>>>>> 
>>>>>> I wrote some template to compute at compile time how many bits is need for a number x. http://www.dpaste.dzfl.pl/99a842fd
>>>>>> 
>>>>>> That works for small number but after i got an error about limit recursion
>>>>> 
>>>>> Instead of template recursion, have you tried regular code run at compile time?
>>>>> 
>>>>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
>>>>> 
>>>>> Bye,
>>>>> bearophile
>>>> 
>>>> Thanks i will take a look
>>> 
>>> this one seem to be interesting http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
>>> 
>>> is like i do but use a table than me i used a recursive way. I go to try it :-)
>> 
>> I think you just have a bug in your template code not terminating.   At most you should execute 4 times.   I think there's a problem with casting down from byte to bool.
>> 
>> However, not user if LesserType is what you're after, but this works:
>> 
>> template log2(ulong x)
>> {
>> static if( x >> 8 )
>> {
>> enum log2 = log2!(x >> 8) + 8;
>> }
>> else static if( x >> 1)
>> {
>> enum log2 = log2!(x>>1) + 1;
>> } else
>> {
>> enum log2 = 1;
>> }
>> }
> 
> Thanks your way is much easier to write, works fine :-)

I would suggest turning it into a compile-time-function though as this will instantiate a large number of templates if you use is repetitively.   Remember that templates are cached by DMD.

int log2(const ulong x)
{
  if( x >> 8 )
 {
   return log2(x >> 8) + 8;
 }
 else if( x >> 1)
 {
   return log2(x>>1) + 1;
 } else
 {
   return 1;
 }
}

void main()
{
 pragma(msg, log2(1UL<<63));
}

Another one ctfe log2, integer and real versions:

[code]
module util.ctfelog2;

uint ctfe_ilog2(ulong arg) pure {
   assert(arg != 0);
   uint result = 0;
   while(arg >>= 1)
     result++;
   return result;
}

ulong ctfe_log2(real arg, uint fracBits) pure {
   import std.math : sqrt, SQRT2;
   uint intPart = ctfe_ilog2(cast(ulong)arg);
   ulong result = intPart;
   if(fracBits == 0 || arg == (1 << intPart))
     return result << fracBits;
   real sq = arg / (1 << intPart);
   for(uint i = fracBits; i; i--) {
     if(sq > 2) {
       result |= 1;
       sq /= 2;
     }
     sq *= sq;
     result <<= 1;
   }
   return result;
}

real ctfe_log2(real arg) pure {
   return ctfe_log2(arg, 56) / cast(real)(1UL << 56);
}

unittest {
   import std.math : log2, abs;
   for(real l = 1; l < 256; l += 0.3) {
     double d1 = ctfe_log2(l);
     double d2 = log2(l);
     assert(abs(d1 - d2) < (cast(real)1.0)/(1UL << 48));
   }
}
[/code]