1

Try type this in your Python 3.3.2 IDLE, hopefully I'm not the only one wondering and im willing to understand why this is happening.

>>> n = 331
>>> d = 165.0 # float number
>>> a = 174
>>> 
>>> a**d % n
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    a**d % n
OverflowError: (34, 'Result too large')

>>> d = int(d)
>>> a**d % n
330

How exactly the floats work and why is this happening? Thank you.

dragons
  • 175
  • 1
  • 10
  • What is your question? – bmargulies Sep 21 '13 at 01:34
  • The largest possible float is about `1.7e308`. `174**165.0` is more than `1e330`. – Barmar Sep 21 '13 at 01:35
  • http://stackoverflow.com/questions/3477283/maximum-float-in-python – Barmar Sep 21 '13 at 01:35
  • 2
    I think the issue here is that Python integers have arbitrary precision, but floating point numbers don't. So `int ** int` produces an `int`, but `int ** float` produces a `float`, but the number is too large to fit in a `float`, as Barmar points out. – Sam Mussmann Sep 21 '13 at 01:36
  • 2
    It's worth noting that implementing `(x**y)%n` by actually computing `x**y`, then doing the `%` on it, is a bad idea in general. The intermediate values end up very large, which may mean overflowing your data type, losing precision (a `float` loses ones digits once you get past 2**53), and/or running much slower. And Python makes it easy to do things right: [`pow(x, y, n)`](http://docs.python.org/3.3/library/functions.html#pow). – abarnert Sep 21 '13 at 01:41
  • By the way, if this is part of a class assignment or a contest or something and you're not allowed to use `pow`, look up [modular exponentiation](http://en.wikipedia.org/wiki/Modular_exponentiation). If you just need to avoid overflow, repeated modular multiplication is sufficient; if you also use binary exponentiation, the result is usually faster to boot (although still not as fast as `pow`, at least in CPython, because it's using the same tricks, but coded in C). – abarnert Sep 23 '13 at 18:10

3 Answers3

7

A float is an IEEE 754 double-precision floating point number, which means there's a maximum value it can hold (a bit over 10**308).*

An int is an arbitrary-precision integer, which grows as many bytes as are needed to hold any value, so it can't overflow.

This is described in the documentation under Numeric Types - int, float, complex.

* Technically speaking, Python doesn't guarantee that it's an IEEE 754 double; it just says that it's usually a C double, and a C double is usually an IEEE 754 double… To see the actual limits on your platform, try sys.float_info.

abarnert
  • 354,177
  • 51
  • 601
  • 671
4

Your literal question was answered, but this is the answer you actually need ;-)

>>> pow(174, 165, 331)
330

Three-argument pow() is a very much more efficient way to do modular integer exponentiation. Internally, intermediate results don't get much larger than 331**2, allowing for speedy computation of cases that otherwise wouldn't even fit in your computer's memory:

>>> pow(174, 16500000000000000, 331)
1
Tim Peters
  • 67,464
  • 13
  • 126
  • 132
2

You can simplify this example like this:

>>> 174 ** 165
4904852668653442061187838611454760487366325533178167907397373456352519588599065423233131397167737319275486886361329161677812258960306827407802115863260150459380820490013634069124303872650922835858611923329022540954288392236014102680789978826970589917040720077612506146107358709021927731368382330643430619926067887419695817233322447181310154127711515923344426608176922624
>>> 174 ** 165.0
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    174 ** 165.0
OverflowError: (34, 'Result too large')

As you can see, it fails when you have a float as the exponent. To understand this, a look into the manual helps:

Integers have unlimited precision. Floating point numbers are usually implemented using double in C […] (source)

So essentially, you can do whatever you want with integers; but floats are restricted to the standard IEEE-754 limits.

poke
  • 369,085
  • 72
  • 557
  • 602