log(n) exponentiation

Main idea behind this is
Be=B if e = 1
Be=B*Be-1 if e is odd
Be=X2 where X = Be/2 if e is even

Here’s the python code for the same.

#calculating x^n
def logNexp(x,n):
    #base conditions
    if n == 0:
        return 1
    if n == 1:
        return x

    #holding x in case n is odd
    temp = x

    x = logNexp(x,n>>1)
    x = x*x

    #if n is odd
    if (n&1):
        x = temp*x

    return x

you can try other variations also, check this at wiki

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s