Subject: Re: [boost] [complex] Feedback and Potential Review Manager
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2012-05-02 12:59:33
Le 02/05/12 08:12, Steven Watanabe a écrit :
> 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
>
>
You are right, when we decompose 255 as a product of prime numbers we get
x^255 = x^(3*5*17) = ((x^17)^5)^3
In order to compute x^p where p is prime we can use its pow 2 decomposition
3= 1+2^1
5= 1+2^2
17= 1*2^4
x^16=2^4 needs 4 *operations
x^17 = x * x^16
x^17 needs 5=1+4 *operations
(x^17)^5 = x^85 = (x^17)*(x^17)^4
x^85 needs 8=5+1+2 *operations
((x^17)^5)^3 = x^255 = x^85 * x^85 * x^85
x^255 = needs 10=8+2 *operations
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^68 = x^34 * x^34
x^85 = x^68 * x^17
x^255 = x^85 * x^85 * x^85
Of course in order to achieve this we need to know the prime factorization at compile time.
Best,
Vicente