overflow

[RMartins]

Can anybody tell me how can i avoid the overflow of this program?

from math import sqrt
f=lambda n: sum([int(i)*int(i) for i in str(n)])

L=[]
for n in range(0,10**20):
if sqrt(f(n))%1==0:# == float(int(sqrt(f(n)))):
L.append(n)

L.sort()
print "Número de quadrados perfeitos na lista:",len(L)
print L
y= lambda L: reduce(lambda x,y: x+y,L)
print y(L)

[jrcagle]

Yes, you want to use xrange() instead of range(). xrange() creates an 'iterator' that loops through one at a time, while range() creates the whole list in place.

from math import sqrt
f=lambda n: sum([int(i)*int(i) for i in str(n)])

L=[]
for n in range(0,10**8):
    if sqrt(f(n))%1==0:# == float(int(sqrt(f(n)))):
        L.append(n)

L.sort()
print "Número de quadrados perfeitos na lista:",len(L)
print L
print sum(L)  # reduce() is not necessary!

However, 10**20 is still too large even for xrange(), which expects integers rather than longs.

So then you do the loop by hand:

from math import sqrt
f=lambda n: sum([int(i)*int(i) for i in str(n)])

L=[]
n = 0
while n < 10**20:
    if sqrt(f(n))%1==0:# == float(int(sqrt(f(n)))):
        L.append(n)
    n += 1

L.sort()
print "Número de quadrados perfeitos na lista:",len(L)
print L
print sum(L)  # reduce() is not necessary!

BUT!!!!!!!

The second program, above, took three minutes to reach n = 5800000 = 5.8e+6. At that rate, going out to 10**20 will take about 6e+14 minutes, or 9.8e+7 years. Don't bother running it!

What's the purpose of your code?

Jeff

[BearofNH]

If you really need to count and sum the perfect squares up to 10^20, you could just as easily take all the numbers up to 10^10 and square them, thereby cutting your runtime by an order of magnitude or two...

You could observe that there are exactly 10^10 entries in the numbers from 1 to 10^10, give or take each of the endpoints.

And the sum of numbers from 1 to X is always X * (X+1) / 2 so for the numbers 1 thru 10^10 the answer will be 10^10 * (10^10+1) / 2 = 5 * 10^19 + 5 * 10^9 = 50000000005000000000. But maybe that would be cheating...

[RMartins]

It´s an exercise i have to do for college. The exercise is create a function that sum the square of the digits of a number and then see in how many numbers for [0,10^20] exist that are perfect squares.

Ex:

442 is a number in those conditions since 4^2+4^2+2^2=36 which is a perfect square.
111 is a number that is not in those conditions since 1^2+1^2+1^2=3 which isn´t a perfect square.

[Ene Uran]

Just a side note, you can use x**0.5 rather than math.sqrt(x) to speed things up:

import timeit

stmt = "math.sqrt(123456789)"
t = timeit.Timer( stmt, "import math" )
print "%s took %s microseconds/pass" % (stmt, t.timeit(1000000))


stmt = "123456789**0.5"
t = timeit.Timer( stmt)
print "%s took %s microseconds/pass" % (stmt, t.timeit(1000000))

"""
my result --->
math.sqrt(123456789) took 1.21041132 microseconds/pass
123456789**0.5 took 0.11569164 microseconds/pass
"""

[jrcagle]

Yeah, a factor of 10 speed-up is nice, Ene.

RMartins: something tells me that your prof wants a more clever plan than brute force. I'm not sure what that plan would be (yet), but iterating from 1 to 10^20 is computationally infeasible.

This loop takes 20 seconds:

for i in xrange(10**8):
   pass

which means that simply looping through 10**20 numbers would take 633000 years.

Jeff

Jeff

[G-Do]

Hi RMartins,

This has less to do with Python and more to do with mathematics, but I'll say it anyway.

As jrcagle said, 10**20 is a huge number of iterations to perform. Lucky for you, you won't need many more than 10**7. Actually, you'll only need to perform 10,015,005 computations, to be exact.

The reason for this is that addition is a commutative mathematical operation. In other words, if you know that 442 is a "match" because:

4**2 + 4**2 + 2**2 = 36

- then you also know that 244 and 424 are matches, because changing the order of the digits doesn't change the sum of the squares. In other words:

4**2 + 4**2 + 2**2 = 36 for 442
2**2 + 4**2 + 4**2 = 36 for 244
4**2 + 2**2 + 4**2 = 36 for 424

Once you figure out that one of these permutations is a match, you don't need to check the others - they are guaranteed to also be matches. Likewise, if you look at a number and see that it isn't a match, you know that its permutations are also not matches, and they don't even need to be checked. Incorporating this kind of logic into your program would dramatically cut down on the number of computations you need to perform: the total number of length-20 strings pulled from an alphabet of 10 characters, after all permutations are dismissed, is 10,015,005. How I arrived at that number, you can try to discover for yourself. I'll give you a hint: dynamic programming. :D

Of course, figuring out how to code the rest of it is an exercise best left for the reader, too, seeing as it's your HW!

Hope this helps!