Python innacuracies with large numbers?

I have to write a function that uses another function, but the other function has to return integers which get fairly innacurate with large numbers.

My code:

import math

def reduce(n, d):
    m = min(n, d)
    for i in range(m, 1, -1):
        if n%i==0 and d%i==0:
            n = n//i
            d = d//i
    return (n, d)

def almost_square(n, d):
    f = n/d
    c = math.ceil(f)
    n*=c
    return reduce(n, d)

def destiny(n, d):
    b = n/d
    fraction = n, d
    while not b.is_integer():
        breuk = almost_square(fraction[0], fraction[1])
        b = fraction[0]/fraction[1]
    
    return int(b)

What the functions are supposed to do:

reduce: just simplifying the fraction, so 2/4 becomes 1/2 for example

almost_square: multiplying the fraction with the rounded up integer of the fraction

destiny: applying almost square on a fraction until it returns an integer.

The thing is, my uni works with a program that tries 50 test cases for each function and you only completed the exercise when every function works for all 50 test cases, and they expect the function 'reduce' to return a tuple of integers, but making integers of the numbers there makes my function 'destiny' innacurate, or at least I think so.

So out of the 50 test cases, all 50 work on the function reduce, all 50 work on the function almost_square, but 5 fail for the function destiny which are:

destiny(10, 6), my output: 1484710602474311424, expected output: 1484710602474311520 destiny(17, 13), my output: 59832260230817688435680083968, expected output: 59832260230817687634146563200

destiny(10, 3), my output: 1484710602474311424, expected output: 1484710602474311520 destiny(15, 9), my output: 1484710602474311424, expected output: 1484710602474311520 destiny(11, 5), my output: 494764640798827343035498496, expected output: 494764640798827359861461484

Anything that could fix this?

Solution 1:

There is some floating point arithmetic in that code, which can slightly throw off the results, and apparently it did. Forget about float, don't use any "floats, but larger" libraries either, integer arithmetic is the way to go.

For example,

f = n/d
c = math.ceil(f)
n*=c

This code looks like it computes n * ⌈n / d⌉, but it only approximately computes that because it uses floating point arithmetic, requiring values to be rounded to the nearest float (for example, int(float(1484710602474311520)) is 1484710602474311424). It should be implemented using integer arithmetic, for example like this:

n *= (n + d - 1) // d

The destiny function should not use floating point division either, and it does not need to. The "is b an integer" test can be stated equivalently as "does d divide n", which can be implemented with integer arithmetic.

Also for that reduce function you can use math.gcd, or implement gcd yourself, the implementation that you have now is very slow.

With those changes, I get the right results for the test cases that you mentioned. I could show the code, but since it is an assignment, you should probably write the code yourself. Asking this question at all is already risky.

Python innacuracies with large numbers?

Solution 1:

Related

Recent Posts