On Fri, Mar 29, 2002 at 11:23:26PM -0700, Luke Palmer wrote:
> > Too late. I'm going there... :)
> Good for you. I was hoping transformations could make it :)
>
> Here's something I was wondering. Say you wanted to write a pow() macro
> (from a previous example) that would forward to C's pow() unless the
> exponent was an integer, in which case it would optimize to many *'s. If
That takes O(n) time. You can do it in O(log n) by evaluating pow (x, m)
as a product of one or more from the list x, x**2, x**4, x**8, x**16
[think of m as a binary number, and pick those terms corresponding to 1 bits]
Obviously x**8 is very easy to calculate from x**4 (and so on)
It seems to be less accurate than pow() for numbers where the intermediate
results overflows the floating point's precision, which is why perl 5.8 is
only going to be using it for "powers of 2" ** integer.
Basically 2**31 and 2**53 weren't integer accurate with long doubles on Irix.
2147483647.9999999999999999 is not what most perl programmers expect.
> it was called like so:
>
> pow(2.718, 2 * 6 / 3)
>
> Then the macro would not recieve 4 as the second argument, rather 2*6/3 in
> syntax tree form. Would the macro have to do its own constant folding? I
> hope not. So how could it check whether this thing was an integer? How
> could it differentiate that from pow(2.718, 2 * 6 / 5) ? Or would any
> constant folding take place before it was passed to the macro?
I'm not sure. The "obvious" way to do constant folding is to take the
expression, write it as an tree, and then if you have three nodes
constant op constant replace that with a node for the constant result.
Work your way up, until you come to a non-constant expression.
I guess that means that your pow() macro sits as a custom op in the tree
with an overloaded "constant fold"
As constant folding moves up the tree it turns 2 * 6 / 3 to 12 / 3
and then 4. pow (2.718, 4) then becomes the target of constant folding,
which will call the pow node's folding routine. Rather than evaluate an
answer, if it is able to substitutes in a revised set of ops
(based on its parameters, so here it's {2.718 * 2.718 * 2.718 * 2.718}
or probably better {my $a = 2.718; $a*=$a; return $a*=$a}).
If it can signal constant folding to be redone from the same place, then I
believe everything works.
If the arguments to your macro get constant folded, then the results
of your macro is evaluated and its result is constant folded
onwards. If your macro isn't given constants, then it is substituted
into the syntax tree at that point, and called correctly each time at
run time.
Nicholas Clark
--
Even better than the real thing: http://nms-cgi.sourceforge.net/
