How is exponentiation implemented in Python?

Question

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?

Hmm, none of the respondents here seem to have noticed that gr is a floating point value. There are a lot of upvotes for answers that have nothing to do with what the above code actually does. — Raymond Hettinger
– Raymond Hettinger, Commented Sep 11, 2012 at 21:59
Does this answer your question? How is ** implemented in Python? — izhang05
– izhang05, Commented Apr 26, 2020 at 20:35

Raymond Hettinger · Accepted Answer · 2012-11-28 07:25:07Z

13

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.

edited Nov 28, 2012 at 7:25

answered Sep 11, 2012 at 21:50

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Brendan Long · Accepted Answer · 2012-09-11 21:07:46Z

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.

I think the important point is that performing an exponentiation is not anywhere near exponential in complexity. Even a naive implementation of M**N is only O(N), not O(c**N) which is what exponential complexity would imply.

Eponymous · Accepted Answer · 2018-04-23 11:50:25Z

5

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

edited Apr 23, 2018 at 11:50

Eponymous

6,9684 gold badges46 silver badges46 bronze badges

answered Sep 11, 2012 at 20:51

thikonom

4,2673 gold badges30 silver badges30 bronze badges

1 Comment

David Wolever Over a year ago

Specifically, line 3378, long_pow.

Collectives™ on Stack Overflow

How is exponentiation implemented in Python?

3 Answers 3

Comments

1 Comment

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Linked

Related