The binary method for finding a n is as follows: 1.) If n = 1 then return a. Oth

Question

The binary method for finding an is as follows:

1.) If n = 1 then return a.

Otherwise:

2.) If n is even, find an/2 recursively and return the square of the result.

3.) Finally, if n is odd, (bigger than 1), then n-1 is even and we can compute a(n-1)/2 recursively, square the result and multiply this result by yielding an for this case.

In cryptology, this is the only practical exponentiation method, since the exponents are usually very, very large (hundreds or even thousands of digits!). This assignment is to implement the binary method for exponentiation as a function. The program being used is Python. I just can't seem to understand this.

Explanation / Answer

def exp_by_squaring(x,n):
  
    if n<0:
      
        return exp_by_squaring(1/x, -n);
    elif n==0:
        return 1;
    elif n==1:
        return x;
    elif n%2==0:
        return exp_by_squaring(pow(x,2), n/2);

    else:
      
        return x*exp_by_squaring(pow(x,2), (n-1)/2)

print exp_by_squaring(7,3)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.