CODEWITHSUNDEEP
pythonfloating-point
Anubhav Agarwal
Anubhav Agarwal

Reputation: 2062

Float Limit in Python

I was writing a program in python

import sys

def func(N, M):
    if N == M:
        return 0.00
    else:
        if M == 0:
            return pow(2, N+1) - 2.00
        else :
            return 1.00 + (0.5)*func(N, M+1) + 0.5*func(N, 0)

def main(*args):
    test_cases = int(raw_input())
    while test_cases:
        string = raw_input()
        a = string.split(" ")
        N = int(a[0])
        M = int(a[1])
        test_cases = test_cases -1
        result = func(N, M)
        print("%.2f" % round(result, 2))

if __name__ == '__main__':
        sys.setrecursionlimit(1500)
        sys.exit(main(*sys.argv))

It gives the same answer for N = 1000 ,M = 1 and N = 1000 , M = 2
On searching I found that limit of float expires over 10^400. My question is how to overcome it

Upvotes: 3

Views: 1359

Answers (3)

casevh
casevh

Reputation: 11394

I maintain one of the Python to GMP/MPFR libraries and I tested your function. After checking the results and looking at your function, I think your function remains entirely in the integers. The following function returns the same values:

def func(N, M):
    if M == 0:
        return 2**(N+1) - 2
    elif N == M:
        return 0
    else:
        return func(N, M+1)//2 + 2**N

The limiting factor with Python's builtin float is not the exponent range (roughly 10**308) but the precision (53 bits). You need around N bits of precision to distinguish between func(N,1) and func(N,2)

Upvotes: 2

Óscar López
Óscar López

Reputation: 236004

Consider using an arbitrary precision floating-point library, for example the bigfloat package, or mpmath.

Upvotes: 0

Ned Batchelder
Ned Batchelder

Reputation: 375564

Floats in Python are IEEE doubles: they are not unlimited precision. But if your computation only needs integers, then just use integers: they are unlimited precision. Unfortunately, I think your computation does not stay within the integers.

There are third-party packages built on GMP that provide arbitrary-precision floats: https://www.google.com/search?q=python%20gmp

Upvotes: 2

Related Questions