
Boost : 
Subject: Re: [boost] [complex] Feedback and Potential Review Manager
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 20120502 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 powN 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk