Re: [boost] [complex] Feedback and Potential Review Manager

Subject: Re: [boost] [complex] Feedback and Potential Review Manager
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-05-02 02:12:57

AMDG

On 05/01/2012 02:52 PM, Christopher Kormanyos wrote:
> 
> 
>> I briefly glanced at your pow-N routines. Perhaps I'm wrong,
>> but I believe you are not doing binary splitting of the exponent
>> here.
> 
> My mistake. I apologize.
> 
> You are doing binary splitting of the exponent.
> But it looks like you still have a redundant multiplication step
> that could be removed with a recursive call. In particular, I believe
> your routine would need 14 multiplications to compute
> x^255, whereas only 7 would be needed with a recursive call.
> Basically, one needs to ask if the overhead of recursive
> call exceeds that of a multiply. I'll leave this one for the
> potential reviewers.
> 

I don't see how it's possible to compute
x^255 in 7 multiplies.  The best
I can come up with is 10:

x^2 = x * x
x^4 = x^2 * x^2
x^8 = x^4 * x^4
x^16 = x^8 * x^8
x^17 = x^16 * x
x^34 = x^17 * x^17
x^51 = x^34 * x^17
x^102 = x^51 * x^51
x^204 = x^102 * x^102
x^255 = x^204 * x^51

In Christ,
Steven Watanabe