CODEWITHSUNDEEP
python
Thomas Esch
Thomas Esch

Reputation: 159

How is exponentiation implemented in Python?

I am able to compute any normally computable fibonnaci number (unless the result becomes to large) in a constant time using Binet's formula ie closed solution formula to compute fibonnaci numbers. Here is my code:

for the non-recursive implementation of fibonnaci:

gr = (1 + 5**0.5) / 2
def gfib(n):
    return int(((gr**n - (1-gr)**n) / 5**0.5))

I understand a^n indicates exponential run time complexity, however this is not the case when the code is run in python, as this computes the nth fibonnaci number instantly. I've done some research on how exponents are implemented in python (maybe exponentiation by squaring?) to give the constant time solution that I get, but haven't found a definitive answer. Any ideas?

Upvotes: 12

Views: 5048

Answers (3)

thikonom
thikonom

Reputation: 4267

You can find the implementation at CPython's source code for the log_pow function.

Upvotes: 5

Raymond Hettinger
Raymond Hettinger

Reputation: 226764

The float.__pow__() method uses C's libm which takes full advantage of hardware support for binary floating point arithmetic. The latter represents numbers using logarithms. The logarithmic representation makes it possible to implement exponentation will just a single multiplication.

Executive summary: Float exponentation is implemented in hardware and runs at nearly constant speed due to the magic of logarithms.

Upvotes: 13

Brendan Long
Brendan Long

Reputation: 54312

Exponents for integers can be calculated much more efficiently than you think. Here's what Wikipedia has to say about it:

The simplest method of computing bⁿ requires n−1 multiplication operations, but it can be computed more efficiently than that, as illustrated by the following example. To compute 2¹⁰⁰, note that 100 = 64 + 32 + 4. Compute the following in order:

2² = 4
(2²)² = 2⁴ = 16
(2⁴)² = 2⁸ = 256
(2⁸)² = 2¹⁶ = 65,536
(2¹⁶)² = 2³² = 4,294,967,296
(2³²)² = 2⁶⁴ = 18,446,744,073,709,551,616
2⁶⁴ × 2³² × 2⁴ = 2¹⁰⁰ = 1,267,650,600,228,229,401,496,703,205,376

This series of steps only requires 8 multiplication operations instead of 99 (since the last product above takes 2 multiplications).

In general, the number of multiplication operations required to compute bⁿ can be reduced to Θ(log n) by using exponentiation by squaring or (more generally) addition-chain exponentiation. Finding the minimal sequence of multiplications (the minimal-length addition chain for the exponent) for bⁿ is a difficult problem for which no efficient algorithms are currently known (see Subset sum problem), but many reasonably efficient heuristic algorithms are available.[29]

The page of exponentation by squaring is hard to summarize, but it's basically the idea that 2⁸ == (2⁴)² == (2²)²)², so instead of calculating 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256, you can calculate 2 × 2 = 4; 4 × 4 = 16; 16 × 16 = 256.

Upvotes: 10

Related Questions