O(n) High-precision Division Between Two Integers

This article will describe a quick and easy implementation of a algorithm that divides two integers with a high precision.

Normally, an array is required to hold the results if the required-precision is high. However, in this implementation, the string is used and returned. It is also easy to replace the string concatenation with the simple print statement, which will make the space usage complexity to .

The idea is to based on human manual process to divide two integers. The following can be improved by extending to two floating numbers instead of integers by considering the positions of the DOT in the given two numbers.

To repeat the process, you need to first obtain the integer part of the division result, check if the remainder is zero, if not, multiple by ten and the division goes on. It is repeated until the required-precision is met or the remainder becomes zero.

#!/usr/bin/evn python
"""
    High-precision division between two integers
    Algorithm complexity: O(n)
    Space complexity: O(n)
    // http://CodingForSpeed.com
"""

def zDiv(a, b, n):
    if b == 0:
        if a >= 0:
            return "+infinity"
        else:
            return "-infinity"
    elif a == 0:
        return "0"
    else:
        from cStringIO import StringIO
        c = a * b
        file_str = StringIO()            
        if c < 0:
            file_str.write("-")
        a = abs(a)
        b = abs(b)
        c = a / b
        d = a % b
        file_str.write(str(c))        
        if d > 0:
            file_str.write(".")
            for x in xrange(0, n):
                a = d * 10
                c = a / b
                d = a % b
                file_str.write(str(c))
                if d == 0:
                    break
        return file_str.getvalue()

if __name__ == "__main__":
    print "355 / 113 = %s" % zDiv(355, 113, 100)
    print "1 / 0 = %s " % zDiv(1, 0, 100)
    print "-1 / 0 = %s " % zDiv(-1, 0, 100)
    print "0 / (-1) = %s " % zDiv(0, -1, 100)
    print "-22 / 7 = %s " % zDiv(-22, 7, 100)
    print "35 / (-5) = %s " % zDiv(35, -5, 100)
    print "-1 / (-8) = %s " % zDiv(-1, -8, 100)

The above Python code is the quick implementation and can also be found in https://github.com/DoctorLai/PyUtils/blob/master/zDiv.py

The above code prints the following if it runs directly (press F5 in the IDLE):

355 / 113 = 3.1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654
1 / 0 = +infinity 
-1 / 0 = -infinity 
0 / (-1) = 0 
-22 / 7 = -3.1428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428 
35 / (-5) = -7 
-1 / (-8) = 0.125 

The xrange() is used instead of range(), which is far more efficient because xrange() simply returns an element at a time. The range() returns a list i.e. will actually creates the list of elements in memory. If the number of elements is huge, it will be more efficient to use xrange().

In Python 3, range() no longer returns a list, therefore, you will need list(range(1, 100)) to returns the list.
The native string concatenation is using ‘+’, which can be improved if the string concatenation is frequent by the following.

from cStringIO import StringIO
file_str = StringIO()
for num in xrange(1, 100):
    file_str.write(str(num))
print file_str.getvalue()

Or, using the list join may also gives quite efficient solutions.

print ";".join([str(num) for num in xrange(1, 100)])

–EOF (The Ultimate Computing & Technology Blog) —