1

Greeting fellas.

I was performing the algorithm intended to obtain the number of partitions of a integer. When I tested my program, margin errors started to occur when n > 257. I actually had the same problem on another matter while working with factorials, but my thoughts were on the algorithm itself having some flaws. I know that python 3.5.x doesn't really have limits on number size.

I even tried to do the sum the old fashioned way with every sum being from:

from decimal import Decimal

but it didn't change the result (only added a longer computational time).

#! /usr/bin/python3.5

from unittest import TestCase as Test

def number_partition(n):
    """ 
    Building the 'Euler' triangle such as
                n
    p(n,j) =    sum p(n-j,i)
                i=j
    """
    if n <  0: return 0
    if n is 0: return 1
    p = []
    for i in range(n):
        p.append([])
        for j in range(i+1):
            if j is i: p[i].append(1) ; break
            p[i].append(sum(p[i-j-1][j:]))

    return sum(p[n-1])


if __name__ == '__main__':
#    number_partition(257)
Test.assertEqual(Test(), number_partition(257), 394723676655357) # Pass
Test.assertEqual(Test(), number_partition(258), 425933084409356) # returns 425933084409355
Test.assertEqual(Test(), number_partition(259), 459545750448675) # returns 459545750448673

So is the algorithm flawed, or is there a Python functionnality I didn't get ?

Thank you in advance for your time.

  • Python 2.x didn't have limits, either. It had two different integer types, `int` for fixed-precision and `long` for arbitrary precision, but it would "promote" `int` values to `long` as necessary. You could think of this as a user-visible optimization: all values were arbitrary-precision integers, but the small ones were implemented with machine words where possible. – chepner Apr 23 '18 at 16:32
  • 1
    Most importantly, don't use `is` when you really mean `==`. The two are only equivalent under certain implementation-specific conditions. – chepner Apr 23 '18 at 16:33
  • `is` vs `==` does not matter here. Are you sure of the expected number? Do you have 2 implementations to compare? If so, I would suggest trying to track down the exact calculation that differs, figuring out the right answer and then filing a bug report. – btilly Apr 23 '18 at 16:41
  • 1
    Thank you for your replies, I acutally tested it on both http://www.numbertheory.org/php/partition.html and http://www.wolframalpha.com/widgets/view.jsp?id=ca10ab4a89d9f0f6f378b89881f63ba3 and the anwsers match the ones expected –  Apr 23 '18 at 17:29
  • `is` is not `==`. – user2357112 Apr 23 '18 at 17:49
  • @user2357112 The program produces identical output when you replace `is` with `==`. There may be a semantic difference, but that detail **IS NOT** the problem here. – btilly Apr 23 '18 at 17:51
  • @btilly: You probably missed the second `is`, in `if j is i`. [I get correct output with both uses of `is` replaced with `==`.](https://ideone.com/TJCdhw) – user2357112 Apr 23 '18 at 17:52
  • @user2357112 I did. You are right. :-( – btilly Apr 23 '18 at 17:53

0 Answers0