Tue Mar 26 13:24:35 EDT 2013

Missing ordinary data-dependent loops for initialization

Example: integer power, e.g. as part of computation of 2^x.  For now
it could be hacked as part of p_pow.  Hmm... not really.  The
constraint that the input is an integer is too much.

They are a pain to implement, as every semantics needs a version.

This kind of looping is hard to do without an integer type..  Painted
into a corner.

Anyways, I couldn't resist.  Basic idea for a primitive:

/* Approximation to 2^x, accurate for "human" mapping.  FIXME: This is
   a bit of a hack since the core language can't do the conditional
   branching.  How to do this better?  */
OP p_pow2_approx(_ exp) {
    i_ n = p_ifloor(exp);
    if (unlikely(n < 0)) {
        return p_div(1, p_pow2_approx(-exp));
    _ x = exp - n;
    // approx 2^x on [0,1] as p(x) = 1 + 2/3 x + 1/3 x^2
    _ r0 = p_add(1, p_mul(x, p_add(2/3, p_mul(x, 1/3))));
    _ r1 = 1;
    _ pow2 = 1;
    while(n) {
        pow2 *= 2;
        if (n&1) r1 *= pow2;
        n >>= 1;
    return p_mul(r0, r1);

Though this has a while loop, so can't be done in parallel.  To do it
in parallel, unroll the loop a couple of times and limit the range of
exp.  Then still it is possible to use the approx over a larger range,
i.e. based on 2^x = (2^{x/n})^n.

It seems there are a lot of possibilities.

EDIT: Successive squaring seems to work quite well.  There is no need
for the p_pow2_approx hack so I'm removing it from the code.