Python - Precision Loss With Large Integer

Question

Edit

Working!!! Thanks everyone for your input! //= in the function is required to port from 2.x to 3.x

I am attempting to factor very large numbers in Python in a timely manner. This is working out except there is a large discrepancy in the values of the primes when multiplied together vs. the original value.

Code:

import math

x = 4327198439888438284329493298321832193892183218382918932183128863216694329


def getPrimes(n):
    num = abs(n)
    factor = 2
    primes = []
    while num > 1:
        factor = getNext(num, factor)
        primes.append(factor)
        num /= factor
    if n < -1:
        primes[0] = -primes[0]
    return primes

def getNext(n, f):
    if n % 2 == 0:
        return 2
    for x in range(max(f, 3), int(math.sqrt(n) + 1), 2):
        if n % x == 0:
            return x
    return n

values = getPrimes(x)

orig = int(1);

print(values)
for y in values:
    orig *= int(y)

print("\n") 
print(x)
print("\n")
print(orig)
print("\n")
print(orig-x)

Output:

[17, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 83, 20845357395553.0]


4327198439888438284329493298321832193892183218382918932183128863216694329


4327198439888438374354383059307859040070974971297410068584490149575917568


90024889760986026846178791752914491136401361286359223239

???

When dividing the original number down, it is able to reach one of the prime factors just fine. This makes me confident that the factors that I am getting in the above factorization are correct.

>>> x /= 17
>>> x /= 20845357395553
>>> x /= (2**185)
>>> x /= 3
>>> x
83.0
>>> x /= 83
>>> x
1.0
>>>

TL;DR

I believe that python's code has an error with large-number (int) multiplication, or maybe I'm doing something absolutely crazy, sanity check!

Thanks!

EDIT

I did the second example code in an online python interpreter, notably 2.xx not 3.xx but I did run the code up top in 3.x as some of you noted. Redid the second operation in 3.xx and replaced. Unaware if anyone has an answer to why the code has two separate values for what should be the same.

EDIT - 7/12/2014

After further examination it appears that I have a case in which the factors are incorrect (checking with Wolfram Alpha) and I've switched algo's. I'll be testing later with long's in 2.7.

Answer 1

Python3 has changed what the division operator does.

In Python 2:

>>> 3 / 2
1

In Python 3:

>>> 3 / 2
1.5
>>> 3 // 2
1

Therefore, your getprimes() function should include the following code:

while num > 1:
    factor = getNext(num, factor)
    primes.append(factor)
    num //= factor