Geek asks and answers

An exponential multiplication algorithm that works in O (n) time?

I am reading a tutorial on algorithms and I am confused by this question:

Suppose we want to calculate the value x ^ y, where x and y are positive integers with m and n bits, respectively. One way to solve the problem is to perform multiplications of y - 1 by x. Can you give a more efficient algorithm that uses only the O (n) multiplication steps?

Will it be a separation and conquest algorithm? Multiplying y-1 by x will be done in theta (n) to the right? .. I don't know where to start this question

+3
source share
3 answers

Use simple recursion to divide and subdue. Here I post more as pseudo code.

x^y :=
    base case: if y==1 return x;
        if y%2==0:  
            then (x^2)^(y/2;
        else 
            x.(x^2)^((y-1)/2);
+1
source

:

x ^ z : z = (2 ^ 0, 2 ^ 1, 2 ^ 2,..., 2 ^ (n-1))

1 n x ^ (2 ^ (i + 1)) = x ^ (2 ^ i) * x ^ (2 ^ i).

n x ^ y:

result = 1
for i=0 to n-1:
    if the i'th bit in y is on:
        result *= x^(2^i)
return result

O (n)

+2

y-1 x^y = x * x^(y-1). , , y 1 y-1.

- y "". y, x^y = x^(2*y/2) = (x^2)^(y/2). y, x^y = x^(2*y/2+1) = x * (x^2)^(y/2).

, y, x^2 x.

:

Power(x, y)=
    1 if y = 0
    x if y = 1
    Power(x * x, y / 2) if y even
    x * Power(x * x, y / 2) if y odd

y . y = b0 + 2.b1 + 4.b2 + 8.b3...

From the properties of exposure it follows:

x^y = x^b0 . x^(2.b1) . x^(4.b2) . x^(8.b2)... 
    = x^b0 . (x^2)^b1 . (x^4)^b2 . (x^8)^b3...

You can get the desired powers of x by squaring, and the binary expansion of y tells you which powers to multiply.

0
source

More articles:


All Articles