support/2016-12-04-ints.sagews

Author William A. Stein
Date 2016-12-04T18:15:53
File 4a5f0542-5873-4eed-a85c-a18c706e8bcd:support/2016-12-04-ints.sagews

On Sat, Dec 3, 2016 at 10:53 PM, Ralf Stephan <> wrote:

“Both ZZ and numpy use libgmp internally “

No, ZZ uses libgmp (actually really MPIR, which is a fork of GMP), and numpy uses Python’s ints/longs. Python’s int/long type is arbitrary precision, despite the confusing naming. It only implements relatively naive algorithms – karatsuba, etc., – and not the asymptotically fast Fourier transform methods that GMP (and MPIR) implement and highly optimize. So Sage’s ZZ will start beating the pants off of Python (and numpy) when the numbers get large.

Example – try this with various values of “digits” and you’ll see ZZ being arbitrarily faster than Python’s longs:

def bench(digits):    print "digits =", digits    global n, m, n1, m1, n2, m2  # timeit uses global namespace    n = ZZ.random_element(10^digits)    m = ZZ.random_element(10^digits)    %timeit n*m    n1 = int(n)    m1 = int(m)    %timeit n1*m1    import numpy    n2 = numpy.int(n)    m2 = numpy.int(m)    %timeit n2*m2
bench(10)bench(100)bench(1000)bench(10000)bench(100000)bench(1000000)
digits = 10 625 loops, best of 3: 51.1 ns per loop 625 loops, best of 3: 126 ns per loop 625 loops, best of 3: 107 ns per loop digits = 100 625 loops, best of 3: 445 ns per loop 625 loops, best of 3: 315 ns per loop 625 loops, best of 3: 254 ns per loop digits = 1000 625 loops, best of 3: 2.16 µs per loop 625 loops, best of 3: 13.8 µs per loop 625 loops, best of 3: 13.5 µs per loop digits = 10000 625 loops, best of 3: 64.9 µs per loop 625 loops, best of 3: 588 µs per loop 625 loops, best of 3: 618 µs per loop digits = 100000 625 loops, best of 3: 1.47 ms per loop 25 loops, best of 3: 20.9 ms per loop 25 loops, best of 3: 21.9 ms per loop digits = 1000000 25 loops, best of 3: 18.7 ms per loop 5 loops, best of 3: 870 ms per loop 5 loops, best of 3: 883 ms per loop
# At 1 million digits (on this test machine): ZZ is 46.5 times faster than Python ints:870 / 18.7
46.5240641711230