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