How to halve a very large even integer without getting an float overflow error?

Question

I have an expression where I halve very large even integers, and I know the numerators are even so there is no fractional part, but I get an overflow error "OverflowError: integer division result too large for a float" because internally Python converts to floats.

return int(n/2) if (n%2) == 0 else int((3*n+1)/2)

I can fix this with mpmath via int(mpf(n)/2) if (n%2) == 0 else int(mpf(3*n+1)/2) but it runs 3x slower than native division and I am looping millions of times so this is too long.

Is there an efficient way to halve a very large even integer?

---

Some have suggested integer division // and I have tested it. The stats are: -

• Using / 45 tests per sec
• Using // 5 tests per sec
• Using mpf 12 tests per sec
• Using >> 5 tests per sec

The integers I am working with are of the order 2**2000 but I want to consider larger ones so I need a method that works on unbounded integers.

Answer 1

You can use // for integer division or >> to bit-shift it

>>> 10 / 2   # results in float
5.0
>>> 10 // 2  # results in int
5
>>> 10 >> 1  # bit shift
5
>>> f"{10:04b}"  # binary format display
'1010'
>>> f"{5:04b}"   # shows shift
'0101'

Demo on a big number

>>> _ = 10**10000 / 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: integer division result too large for a float
>>> _ = 10**10000 // 2
>>> (10**10000 >> 1) == (10**10000 // 2)
True

Beware, you must coerce non-int inputs in either case

>>> 10.0 / 2
5.0
>>> 10.0 // 2
5.0
>>> 10.0 >> 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for >>: 'float' and 'int'

Take a look at the PEP 238 Abstract which introduced the split of / vs // and the rest for a little about how this is implemented as __div__() (now __truediv__() as of some more recent revision) and __floordiv__() methods on instances of int

Answer 2

Both of these options seem pretty fast:

In [387]: n = int("12" * 10_000)

In [388]: %timeit n//2
20.6 µs ± 593 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [389]: %timeit n>>1
3.81 µs ± 37.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

You can use wombo_combo = lambda x : x>>1 if x%2 == 0 else (3*x + 1)>>1

Edit:

I think if you're looking to speed things up you can also do something like this, which is slightly faster than %

if n & 1 == 0: # even
    return n >> 1
# odd
return (n*3 + 1) >> 1

Here are more timings for you:

In [78]: n = 2**2000

In [79]: %timeit n>>1 if n&1==0 else (n*3+1)>>1
288 ns ± 8.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [80]: %timeit n//2 if n&1==0 else (n*3+1)//2
566 ns ± 5.37 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [81]: %timeit n//2 if n%2==0 else (n*3+1)//2
965 ns ± 3.24 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Also if you know the numerator is always positive you should just avoid doing the conditional check. That's extra wasted time that could be spent shifting them bits!