CODEWITHSUNDEEP
pythondebuggingsum-of-digits
letfoolsdie
letfoolsdie

Reputation: 3

Sum of the series. What's wrong with this Python code?

I'm trying to write a program to find a sum of all multiples of 3 below given n. So far I came up with this solution (using formula for arithmetic series):

def sumof3(n):
    n = int((n-1)/3)
    return int((n/2)*(6+3*(n-1)))

It works pretty well but for some reason starts to fail with large numbers. For example, for n = 232471924 the return value is 9007199280122284, while it should be 9007199280122283.

Can anybody advise where's a bug here?

Upvotes: 0

Views: 130

Answers (3)

DSM
DSM

Reputation: 353459

Python has arbitrary-precision integers but standard limited (double) precision floats. In Python 3, the division of two integers with / produces a float, which means (e.g.) that 

>>> 10**50/10**25
1e+25
>>> int(10**50/10**25)
10000000000000000905969664

but if we work purely with integers using //, we get:

>>> 10**50//10**25
10000000000000000000000000

In your code, both (n-1)/3 and (n/2) will produce float output, which means that you've only got ~18 digits or so of precision. If we rework your function to work purely with integers:

def sumof3b(n):
    n = (n-1)//3
    return (6+3*(n-1))*n//2

Then we get agreement for the low values:

>>> all(sumof3(n) == sumof3b(n) for n in range(10**7))
True

but at high values we preserve the precision:

>>> n = 232471924
>>> sumof3(n) # bad
9007199280122284
>>> sumof3b(n) # good
9007199280122283

[Here we can reorder to make sure we're not losing any fractional data, but I sometimes find the fractions module comes in handy too.]

Upvotes: 3

Darth Kotik
Darth Kotik

Reputation: 2361

It's just too big for int

import sys
print int(sys.maxint)
print int(sys.maxint*2)

For me it prints 

2147483647
-2

Dumb me! Misunderstud the question! Sorry!

Upvotes: 0

br3w5
br3w5

Reputation: 4583

This is an example of a round-off error:

Squeezing infinitely many real numbers into a finite number of bits requires an approximate representation. Although there are infinitely many integers, in most programs the result of integer computations can be stored in 32 bits. In contrast, given any fixed number of bits, most calculations with real numbers will produce quantities that cannot be exactly represented using that many bits. Therefore the result of a floating-point calculation must often be rounded in order to fit back into its finite representation. This rounding error is the characteristic feature of floating-point computation.

You'll get close enough to where you want to be by doing the following:

def sumof3(n):
    n = float((n-1)/3)
    return int((n/2)*(6+3*(n-1)))

Or if you want to be more precise:

def sumof3(n):
    n = float((n-1)/3)
    return float((n/2)*(6+3*(n-1)))

Upvotes: 0

Related Questions