www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - recursive template at ctfe

reply "bioinfornatics" <bioinfornatics fedoraproject.org> writes:
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 ?
Nov 26 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 26 2013
parent reply "bioinfornatics" <bioinfornatics fedoraproject.org> writes:
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
Nov 26 2013
parent reply "bioinfornatics" <bioinfornatics fedoraproject.org> writes:
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 :-)
Nov 26 2013
parent reply Shammah Chancellor <anonymous coward.com> writes:
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;
  }
}
Nov 26 2013
parent reply "bioinfornatics" <bioinfornatics fedoraproject.org> writes:
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 :-)
Nov 26 2013
parent Shammah Chancellor <anonymous coward.com> writes:
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));
}
Nov 26 2013
prev sibling parent "Shire" <degener_trash mail.ru> writes:
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]
Apr 06 2014