5

Consider the following code (from here, with the number of tests increased):

from timeit import Timer

def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def find_invpowAlt(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    low = 10 ** (len(str(x)) / n)
    high = low * 10
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

x = 237734537465873465
n = 5
tests = 1000000

print "Norm", Timer('find_invpow(x,n)', 'from __main__ import find_invpow, x,n').timeit(number=tests)
print "Alt", Timer('find_invpowAlt(x,n)', 'from __main__ import find_invpowAlt, x,n').timeit(number=tests)

Using Python 2.6 (Python 2.6.5 (r265:79063, Apr 16 2010, 13:57:41) [GCC 4.4.3] on linux2), the times reported are:

Norm 9.73663210869
Alt 9.53973197937

However, on the same machine using Python 3.1 (Python 3.1.2 (r312:79147, Apr 15 2010, 15:35:48) [GCC 4.4.3] on linux2), the times are:

Norm 28.4206559658
Alt 26.8007400036

Does anyone know why this code runs three times slower on Python 3.1?

Community
  • 1
  • 1
user200783
  • 13,722
  • 12
  • 69
  • 135
  • 1
    no repro: python3.1 is faster than 2.6 by about 30% on my machine. – SilentGhost Jul 11 '10 at 09:45
  • Thanks. What OS are you running? I get the above times on Ubuntu 10.04 64-bit. – user200783 Jul 11 '10 at 09:47
  • 32-bit version of the same system – SilentGhost Jul 11 '10 at 09:49
  • @Paul Baker: I have virtually the same numbers as you on Mac OS X 64-bit (but with Python 3.1.1 32-bit instead of 3.1.2). – Philipp Jul 11 '10 at 09:53
  • 1
    @Paul: these are not the same codes, you're forgetting `from __future__ import division`, without one, results are different. While I'm not entirely sure this is the cause of this issue, I suspect it might be. – SilentGhost Jul 11 '10 at 10:08
  • You're right: Using `from __future__ import division` with Python 2.6 causes it to be almost as slow as 3.1 - the results are `Norm 21.6877419949` and `Alt 26.7953689098`. What changes do I need to make to the code for the performance on 3.1 (and on 2.6 with future division) to match the earlier performance of 2.6? – user200783 Jul 11 '10 at 10:20
  • OK, I replaced `low = high/2` with `low = high//2` and `low = 10 ** (len(str(x)) / n)` with `low = 10 ** (len(str(x)) // n)`. This brought the performance of 2.6 with `from __future__ import division` in line with the regular performance of 2.6. However, the performance of 3.1 was unchanged - still 3 times slower than 2.6. Does anyone know why this might be? – user200783 Jul 11 '10 at 10:39
  • On another machine with Ubuntu 64-bit, Python 3.0.1 is exactly 1.8 times slower than Python 2.6.2. – Philipp Jul 11 '10 at 10:59

2 Answers2

3

I got steadily decreasing times from 2.5, 2.6, 2.7 and 3.1 (Windows XP SP2) ... with the "/" version. With the //, the 3.1 times were dramatically smaller than the 2.X times e.g. "Norm" dropped from 6.35 (py2.7) to 3.62 (py3.1).

Note that in 2.x, there are ints (machine word, 32 or 64 bits) and longs (variable length). In 3.x, long has been renamed int, and int went away. My guess is that converting from long to float may cause the extra time with /.

In any case, a much better "Alt" version would start off with this code:

high = 1
highpown = 1
while highpown < x:
    high <<= 1
    highpown <<= n
John Machin
  • 81,303
  • 11
  • 141
  • 189
  • "would start off with this code `...`". Followed by `low = high // 2`? – user200783 Jul 11 '10 at 11:38
  • @Paul Baker: Of course. `low = high / 2` is a BUG in BOTH functions. – John Machin Jul 11 '10 at 11:56
  • 1
    +1. I strongly suspect it's the `int` versus `long` aspect that makes a difference. Note that on a 32-bit machine, the values being tested wouldn't fit in an int, so you'd be doing calculations with longs in both Python 2.x and 3.x. But on a 64-bit machine, you're using `int` arithmetic in 2.x and arbitrary-precision arithmetic in 3.x. – Mark Dickinson Jul 11 '10 at 14:00
2

The // operator performs integer division (or floor division) in both python 2 and 3, whereas the / operator performs floor division in python 2 given integer operands and true division in python 3 given any operands.

Try replacing the / operator with the // operator.

fmark
  • 57,259
  • 27
  • 100
  • 107
  • Thanks. I replaced `low = high/2` with `low = high//2` and `low = 10 ** (len(str(x)) / n)` with `low = 10 ** (len(str(x)) // n)`. This brought the performance of 2.6 with `from __future__ import division` in line with the regular performance of 2.6. Unfortunately the performance of 3.1 was unchanged - still 3 times slower than 2.6. – user200783 Jul 11 '10 at 10:42
  • Of course, the problem is that "integers" in python3 are the old "longs" of python2. The operator doesn't matter here :) – Jorge Barata Feb 19 '15 at 16:01