Re: gawk bug

[Andrew J. Schorr]

On Mon, Jun 13, 2005 at 03:21:11PM -0700, John H. DuBois III wrote:
> $ time gawk 'BEGIN{j=1; j^=-1; print j}'
> 1
> 
> user    0m9.60s
> 
> $ time gawk 'BEGIN{j=1; j=j^-1; print j}'
> 1
> 
> user    0m0.00s

Interesting.  The difference is in the Node_assign_exp vs. Node_exp
code in eval.c.

For Node_exp, it says:

        case Node_exp:
                if ((lx = x2) == x2 && lx >= 0) {       /* integer exponent */
                        if (lx == 0)
                                x = 1;
                        else if (lx == 1)
                                x = x1;
                        else {
                                /* doing it this way should be more precise */
                                for (x = x1; --lx; )
                                        x *= x1;
                        }
                } else
                        x = pow((double) x1, (double) x2);
                return tmp_number(x);

Whereas for Node_assign_exp, it says:

                if ((ltemp = rval) == rval) {   /* integer exponent */
                        if (ltemp == 0)
                                *lhs = make_number((AWKNUM) 1);
                        else if (ltemp == 1)
                                *lhs = make_number(lval);
                        else {
                                /* doing it this way should be more precise */
                                for (t1 = t2 = lval; --ltemp; )
                                        t1 *= t2;
                                *lhs = make_number(t1);
                        }
                } else
                        *lhs = make_number((AWKNUM) pow((double) lval, (double) 
rval));


The difference is that Node_exp checks for a non-negative exponent, whereas
Node_assign_exp omits that check.  So the 'for' loop takes quite some time
to run.

Note that using a large integer exponent also takes a lot of time:

bash-2.05b$ time gawk 'BEGIN{j=1; j=j^2000000000; print j}'                   
1

real    0m4.120s
bash-2.05b$ time gawk 'BEGIN{j=1; j^=2000000000; print j}'
1

real    0m4.133s

A quick patch for the original problem would be to change the Node_assign_exp
code to check for a non-negative exponent.

But beyond that, I think there are 2 issues here: 1. the same function should
be used in both places; and 2. the exponentiation algorithm is not very good,
instead exponentiation by squaring should be used:

   http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Regards,
Andy