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