Python sqrt limit for very large numbers?

Asked 30/1, 2015 at 16:8 Answered 30/1, 2015 at 20:50

I'm working with very large numbers (1,000,000 digits) and I need to calculate their square root. I seem to be hitting on a limit in my code.

y = 10**309
x = y**0.5
print(x)

And I'm getting this error:

x = y**0.5
OverflowError: int too large to convert to float

The code works till 10**308. But beyond that it seems broken. I've checked this in command line as well. Same error. Can someone please help me?

If this is a Python limit, is there an alternate method I could use?

Sector answered 30/1, 2015 at 16:8 Comment(14)

Interestingly math.sqrt returns inf for anything larger than 10^308 – Interjacent 30/1, 2015 at 16:12

I think it should be doable with out current level of mathematics... but I have few hopes... and even fewer hopes that there already exist something ( even at mathematics level.. not programming) to help you with this. – Pinnatifid 30/1, 2015 at 16:19

sqrt and various functions in math are based on the math C library. That library normally only handles up to the limit of a C double, usually a 64 bit floating point number. 10^308 is the (absolute) maximum of a 64 bit floating point number (following the IEEE 754 standard). – Hypognathous 30/1, 2015 at 16:24

Note that digits and number size are not always the same thing: 10^309 has only 1 significant digit. So "very large numbers (1 million digits)" doesn't really apply here. – Hypognathous 30/1, 2015 at 16:26

Try moving this question to mathoverflow.net, may be some mathematician can give you some pointers... – Pinnatifid 30/1, 2015 at 16:26

You can simplify the problem though: divide your numbers by e.g. 10^100. The square root of 10^100 = 10^50. You can then use sqrt(a*b) = sqrt(a) * sqrt(b). – Hypognathous 30/1, 2015 at 16:27

;-) If you try to limit your prime sieve algorithm, you may as well use a rounded value. – Outfall 30/1, 2015 at 16:28

gmpy2 is, I believe, the state of the art for dealing with truly humongous numbers in Python (I'm biased because I originated its precursor gmpy, but haven't been active in either for a long while -- the current maintainers have done an awesome job). Try it out! – Wolbrom 30/1, 2015 at 16:32

Standard IEEE-754 doubles can only represent up to 10**308, regardless of significant digits, as OP discovered. You'll have to use a third-party library of some kind to handle bigger numbers. – Orderly 30/1, 2015 at 16:32

@LeeDanielCrocker, right, and gmpy2 Pythonically wraps just such libraries (GMP/MPIR, MPFR, &c -- see gmpy2.readthedocs.org/en/latest/intro.html ). – Wolbrom 30/1, 2015 at 16:39

@AlexMartelli, A quick test on my system shows that gmpy2.isqrt can calculate the integer square root of a 1,000,0000 digit number in less than 25 ms. – Yim 30/1, 2015 at 20:37

@Yim thanks, will try out the gmpy2 and update here how it goes. Although I do have one more question. Are the results accurate? – Sector 31/1, 2015 at 3:20

The results are accurate. You do need to use the proper function. isqrt calculates the integer square root. sqrt returns a multiple precision floating point value but you can increase the precision to any number of bits. – Yim 31/1, 2015 at 3:33

@casevh, thanks -- BTW Case's the "current maintainer" I praised above and in fact the initiator of gmpy2!-) – Wolbrom 31/1, 2015 at 5:56

Simplifiy your problem, using a bit of math.

Note that sqrt(a*b) = sqrt(a) * sqrt(b) (for real, positive numbers at least).

So, any number larger than, say, 10^100, divide by 10^100. That's a, and the result of the division is b, so that your original number = a * b. Then use the square root of 10^100 (= 10^50), multiply that by the square root of b, and you have your answer.

With your example:

import math
x = 10**309
a = 1e100
b = 1e209   # Note: you can't calculate this within Python; just use plain math here
y = 1e50 * math.sqrt(1e209)

Example for a not-so-round number:

x = 3.1415 * 1e309
a = 1e100
b = 3.1415e209   # Again, just subtract the exponent: 309 - 100
y = 1e50 * math.sqrt(3.1415e209)

Or for an integer that's not a power of 10, fully written out:

x = 707070
x = 70.707 * 1e4  # note: even number in exponent
x = 70.707e4
a = 1e2  # sqrt(1e2) = 1e1 = 10
b = 70.707e2
y = 10 * sqrt(70.707e2)

A few notes:

Python handles ridiculously large integer numbers without problems. For floating point numbers, it uses standard (C) conventions, and limits itself to 64 bit precision. You almost always get floating point numbers when taking a square root of something.
1e309 means 10**309, and 3.1415e209 means 3.1415 * 10**209. This is a standard programming convention.

Hypognathous answered 30/1, 2015 at 16:31 Comment(3)

I'm glad you reworked you first draft, I wasn't able to ask for that in time :-) – Outfall 30/1, 2015 at 16:37

HI @Evert, thanks for the idea... but 10^309 was just the high limit example. I'm working with all integers, not just 10s, 100s, or 1000s. So this solution while elegant , will not work for me. Thank you though. I appreciate you taking your time to answer :) – Sector 31/1, 2015 at 3:21

@SAnwar In case you didn't get the second example (which is simply a large integer that's not a power of 10), I've added another example which may be a bit more clear. – Hypognathous 31/1, 2015 at 12:4

You should use the gmpy2 module. It provides very fast multiple-precision arithmetic.

On my system, operations on million digit numbers are very fast.

In [8]: a=gmpy2.mpz('3'*1000000)

In [9]: %timeit gmpy2.isqrt(a)
10 loops, best of 3: 22.8 ms per loop

In [10]: %timeit (a+1)*(a-1)
10 loops, best of 3: 20.9 ms per loop

Working with 100,000,000 digit numbers only takes a few seconds.

In [20]: a.num_digits(10)
Out[20]: 99995229

In [21]: %timeit gmpy2.isqrt(a)
1 loops, best of 3: 5.05 s per loop

In [22]: %timeit (a+1)*(a-1)
1 loops, best of 3: 3.49 s per loop

Disclaimer: I'm the current maintainer of gmpy2.

Yim answered 30/1, 2015 at 20:50 Comment(0)

Based on what I think are similar questions, you can look into using the Decimal class.

Here is an example using what you have

>>> x = 10**309
>>> y =x**.5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float
>>> import decimal
>>> d = decimal.Decimal(x)
>>> d.sqrt()
Decimal('3.162277660168379331998893544E+154')
>>> float(d.sqrt())
3.1622776601683792e+154

May be helpful, it doesn't give you your error.

Procter answered 30/1, 2015 at 16:21 Comment(8)

Nopes... Current level of mathematics has no answer for this. – Pinnatifid 30/1, 2015 at 16:23

Was referring more to his specific example. In general I do not disagree that there are numbers that are too big for current computation. I'll add an edit. – Procter 30/1, 2015 at 16:26

@CSCFCEM, there are numbers too big to comfortably fit in memory (including the space needed for intermediate results processing them), but that, depending on your amounts of RAM, is many millions up to a few billion digits, not piddling hundreds! "Current level of mathematics" is perfectly fine -- just install gmpy2 and buy much more RAM!-) – Wolbrom 30/1, 2015 at 16:36

I agree @AlexMartelli. If I said something that makes it sound like I disagree, I'll be happy to correct it. – Procter 30/1, 2015 at 17:3

@CSCFCEM, "I do not disagree that there are numbers that are too big for current computation" is where it sounds you disagree, given Sarvesh's comment on "current level of mathematics" (?!). Sure, many specific formats used for numbers (e.g float) have specific limits (often imposed by hardware, never by "current mathematics" nor "current computation"!-), but the simple solution is, just use different formats (perfectly supported by current mathematics for current computation -- as long as you buy enough RAM:-). – Wolbrom 30/1, 2015 at 17:8

Ahh yes, I understand now. Perhaps I should have said "efficient computation"? I just didn't agree completely that (and it sounds like you agree with me) that "current level of mathematics has no answer for this." and was trying to create some middle ground. I understand that there is always more firepower available (bigger/better hardware), but for some users it may not be practicle to obtain. Cheers! – Procter 30/1, 2015 at 17:18

By current level of mathematics... I mean research done in finding out algorithms to perform these computations... Since these kind of numbers don't fit in memory... special algorithms are created to break down the problem into smaller doable chunks... If it were an addition problem.. you could have done it very easily... because there exist very very simple mathematics to break down addition... but for square root... I don't think any such mathematics theory exists. – Pinnatifid 30/1, 2015 at 17:33

@Procter Let alone efficiency... I am questioning the do-ability. – Pinnatifid 30/1, 2015 at 17:34

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags