[R] x*x*x*... vs x^n

[Duncan Murdoch]

On 6/29/2005 9:31 AM, Robin Hankin wrote:
> Hi  Duncan
> 
> 
> On Jun 29, 2005, at 02:04 pm, Duncan Murdoch wrote:
> 
>> On 6/29/2005 7:32 AM, Robin Hankin wrote:
>>
>>> Hi
>>> I have been wondering if there one can speed up calculating small  
>>> powers
>>> of numbers such as x^8 using multiplication.
>>> In addition, one can be a bit clever and calculate x^8 using only  
>>> 3  multiplies.
>>> look at this:
>>>  > f1 <- function(x){x*x*x*x*x*x*x*x}
>>>  > f2 <- function(x){x^8}
>>>  > f3 <- function(x){x2 <- x*x;x4 <- x2*x2;return(x4*x4)}
>>>
> 
> [snip]
> 
>>
>> If you look in src/main/arithmetic.c, you'll see that R does a  
>> general real-valued power (using C's pow() function) whenever  
>> either one of the args is real (except for a few special cases,  
>> e.g. non-numbers, or powers of 2 or 0.5).  There is an internal R  
>> function equivalent to your f3, but it is not used in the situation  
>> of real^integer (and in any case, x^8 is real^real).
>>
>> I suppose if you wanted to submit a patch someone would take a  
>> look, but the question is whether there is really any calculation  
>> whose execution time would be materially affected by this.  Most  
>> computations are not dominated by integer power calculations, so is  
>> this really worth the trouble?
>>
>> Duncan Murdoch
>>
> 
> 
> well, the Gnu Scientific Library has the pow_int() functions, which  
> are a generalization
> of f3(), so someone thinks so. I did a speed test of them but they  
> were much slower than
> R (for any of f1(), f2(), f3()):
> 
> library(gsl)
> system.time(ignore <- pow_int(a,8))
> [1] 1.07 1.11 3.08 0.00 0.00
> 
> <why the slow execution time?>

Shouldn't you ask the gsl maintainer that? :-)

> But I'm far more interested in the philosophy behind your comments.  I
> would say that it  definitely *is* worth the trouble because someone,
> somewhere, will want fast integer powers, and possibly use R for  
> nothing else.
> 
> Ken's point about matrix exponentiation is relevant here too.
> 
> This is a stated design consideration in Mathematica, I think.
> 
> (Of course, I'm not suggesting that other programming tasks be  
> suspended!  All I'm pointing
> out is that there may exist a user to whom fast integer powers are  
> very very important)

Then that user should submit the patch, not you.  But whoever does it 
should include an argument to convince an R core member that the change 
is worth looking at, and do it well enough that the patch is accepted.
Changes to the way R does arithmetic affect everyone, so they had better 
be done right, and checking them takes time.

Duncan Murdoch