How does Integer Division work in python?

Question

So, I have recently heard of Integer Division and that it is very fast. I have always been using Bit Shifting when I do floor(x / 2^n).

So, I have tested if which is faster Integer Division or Bit Shifting so, I made this code where it tests and compare it 100 times and find the mean:

    import timeit
    import statistics as stat
    
    def compare_times(a, b):
        res_a = timeit.timeit(a)
        res_b = timeit.timeit(b)
        c = res_a - res_b # if negative, a is faster 
        return c
    
    output = []
    
    for _ in range(100):
        output.append(compare_times("5 >> 1", "5 // 2"))
    
    print (stat.mean(output))

And the result is positive, meaning b is faster. Isn't bit shifting working directly at the bit of the number? Why is it slower than Integer Division?

I tested another thing to see if it is because I chose 5, so:

    import timeit
    import statistics as stat
    import random
    
    def compare_times(a, b):
        res_a = timeit.timeit(a)
        res_b = timeit.timeit(b)
        c = res_a - res_b # if negative, a is faster 
        return c
    
    output = []
    
    for _ in range(100):
        number = random.randrange(5000, 50001)
        output.append(compare_times(f"{number} >> 1", f"{number} // 2"))
    
    print (stat.mean(output))

which also outputted positve.

The only time I see a (bit shift) is faster than Integer Division is when in floor(x / 2^n), n >= 2.

So, ultimately, how does Integer Division work? And why is it faster than Bit Shift in terms of smaller numbers?

You'd want to look at the bytecode output for those expressions to know for sure. Since you're using constants there could be optimizations applied. — Mark Ransom
– Mark Ransom, Commented Mar 1, 2021 at 5:20

kaya3 · Accepted Answer · 2021-03-01 05:28:30Z

Any time difference you're seeing is spurious; in fact, 5 // 2 and 5 >> 1 both compile to the same CPython bytecode:

>>> from dis import dis
>>> dis('5 // 2')
  1           0 LOAD_CONST               2 (2)
              2 RETURN_VALUE
>>> dis('5 >> 1')
  1           0 LOAD_CONST               2 (2)
              2 RETURN_VALUE

That is, the computation is done at compile-time, not at runtime, so you are actually just measuring how long it takes to load a pre-computed constant in both cases. To get an accurate benchmark, you need to actually perform the computation at runtime, such as by passing a variable; I also suggest using larger numbers (or raising the number of repetitions beyond the default of 1,000,000) to get a more reliable comparison.

>>> n = 1234 ** 56 # a 174-digit number
>>> from timeit import timeit
>>> timeit(lambda: n // 2)
0.32904140199389076
>>> timeit(lambda: n >> 1)
0.12879745499958517

So we can see that at least for very large numbers, bit-shifting is faster, as you would expect. For smaller numbers there may be no significant difference.

As for how CPython actually computes integer division, the source code on GitHub is freely available to read, and according to a comment there, the algorithm used is found in a well-known textbook:

    /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
       edn.), section 4.3.1, Algorithm D], except that we don't explicitly
       handle the special case when the initial estimate q for a quotient
       digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
       that won't overflow a digit. */

Collectives™ on Stack Overflow

How does Integer Division work in python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related