CODEWITHSUNDEEP
python-2.7mathfloating-point
Siesta
Siesta

Reputation: 471

Wrong answer when calculating binomial coefficients using modified formula

I am trying to write a function to calculate the binomial coefficients using this formula: enter image description here

The problem I am having is that I can not mange to get the correct answer. This is an example of two ways I have tried to write the function.

def binomial(n, i):
    total = 0

    for j in range(1, (n-i+1)):
        n = float(n)
        i = float(i)
        j = float(j)        

        product = (i+j) / j

        if total == 0:
            total = product
        else:
            total = total * product

    print '%.f' %total

or like this using numpy

import numpy as np

def binomial_np(n, i):
    array = np.zeros(n-i+1)

    for j in range(1, (n-i+1)):
        s = float(j)
        n = float(n)
        i = float(i)

        array[j] = (i+s)/s

    array = array[1 : ]
    array = np.prod(array)    

    print '%.f' %array

Both of the functions produces almost the correct result. After looking around a bit on the forum I did find some other examples that do produce the correct result, like this one from Python Binomial Coefficient 

import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == x:
    print(1)
elif y == 1:         # see georg's comment
    print(x)
elif y > x:          # will be executed only if y != 1 and y != x
    print(0)
else:                # will be executed only if y != 1 and y != x and x <= y
    a = math.factorial(x)
    b = math.factorial(y)
    c = math.factorial(x-y)  # that appears to be useful to get the correct result
    div = a // (b * c)
    print(div)

The real question I have from this is if there is something wrong with the way I have written the formulas, or if it just isnt possible to get the correct answer this way because of how float's and number of decimals work in Python. Hope someone can point me in the right direction on what I am doing wrong here.

Upvotes: 1

Views: 648

Answers (2)

Rory Daulton
Rory Daulton

Reputation: 22544

The slight discrepancies seem to come from using floating point arithmetic. However, if you are sure that n and i are integers, there is no need at all for floating point values in your routine. You can just do

def binomial(n, i):
    result = 1
    for j in range(1, n-i+1):
        result = result * (i+j) // j
    return result

This works because the product of 2 consecutive numbers is divisible by 1*2, the product of 3 consecutive numbers is divisible by 1*2*3, ... the product of n-i consecutive numbers is divisible by (n-i)!. The calculations in the code above are ordered to that only integers result, so you get an exact answer. This because my code does not calculate (i+j)/j as your code does; it calculates result * (i+j) and only then divides by j. This code also does a fairly good job of keeping the integer values as small as possible, which should increase speed.

If course, if n or i is float rather than integer, this may not work. Also note this code does not check that 0 <= i <= n, which should be done.

Upvotes: 1

MvG
MvG

Reputation: 60868

I would indeed see float precision as the main problem here. You do floating point division, which means your integers may get rounded. I suggest you maintain the numerator and denominator as separate numbers, and do the division in the end. Or, if the numbers get too big using this approach, write some gcd computation and cancel common factors along the way. But only do integer divisions (//) to avoid loss of precision.

Upvotes: 0

Related Questions