I've always made the assumption that integer division was faster than floating point division, but I did some tests that seemed to prove otherwise.
import gmpy2, time, math
digits = 100000
scale = 10**digits # Decimal precision
gmpy2.get_context().precision = int(math.log2(10) * digits) # Binary precision
def start_timer():
global start_time
start_time = time.time()
def print_timer():
print("%s s" % (time.time() - start_time))
start_timer()
for i in range(1000):
x = scale // 3
print_timer()
start_timer()
for i in range(1000):
x = gmpy2.mpfr(1) / 3
print_timer()
start_timer()
for i in range(1000):
x = gmpy2.mpfr(1) / gmpy2.mpfr(3)
print_timer()
The integer division took 0.17 seconds, the mpfr division took 0.06 seconds, and the division between two floating point numbers took 15.56 seconds.
My questions:
- Am I setting up this test correctly?
- Is mpfr division really more optimized than native division?
- Is division involving a floating point and an integer much faster than that involving two floating point numbers?
I'm using IPython to time some short examples and then I'll try to explain the results.
Notice that as the precision increases, the running time for
a/b
increases more rapidly thana/3
. When calculatinga/b
, MPFR uses the full precision of both values and the running time is (roughly) O(n * ln(n)). When calculatinga/3
, MPFR uses a short, but exact, representation of 3 and the running time is (roughly) O(n). This explains whya/b
is slower thana/3
for high precision. (n is the length ofa
in bits.)When Python calculates
scale//3
, it takes advantage of the fact that 3 will fit into a singledigit
and running time is linear in the length ofscale
. This is effectively the same calculation asa/3
but since the underlying GMP library is faster than Python,a/3
is computed faster thanscale//3
.Here is a short example of the difference in performance between Python and GMP.
You were measuring the performance between an
n
byn
division and ann
byk
division when you compareda/b
anda/3
. (n
is the length ofa
in bits, andk
is much, much smaller thann
.) When you comparedscale//3
and `a/3', you were comparing a simple, straight-forward division implementation with a highly-optimized implementation.Implementation note: In the current unstable development branch,
a/3
callsmpfr_div_ui
directly. This eliminates the creation of a temporary object by MPFR. This improves the performance as shown below.