Subject: Re: [boost] [complex] Feedback and Potential Review Manager
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-05-02 02:12:57
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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk