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

[Robin Hankin]

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?>

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)


very best wishes

rksh


--
Robin Hankin
Uncertainty Analyst
National Oceanography Centre, Southampton
European Way, Southampton SO14 3ZH, UK
  tel  023-8059-7743