5.2.3 An Optimization Example

Imagine you are writing a program that frequently computes a*b + c for $ a,b,c$ Sage integers. For example, you want to do the following computation (timings on a Macbook Pro 2Ghz under OS X):
sage: a = 939393; b = 19393; c = 39390283
sage: time for _ in range(10000): a = a*b + c           
CPU times: user 0.33 s, sys: 0.21 s, total: 0.53 s

There is no ``multiply then add'' operation built into Sage, and you're very frustrated because you really want this to be as fast as possible. There is possibly significant overhead in the computation of a*b + c in Python.

First create a new compiled ``multiply and add'' command in Sage.

cimport sage.rings.integer
def muladd(sage.rings.integer.Integer a,
           sage.rings.integer.Integer b,
           sage.rings.integer.Integer c):
    """
    Compute a*b + c
    """
    cdef sage.rings.integer.Integer d
    d = sage.rings.integer.Integer()
    mpz_mul(d.value, a.value, b.value)
    mpz_add(d.value, d.value, c.value)
    return d

Do this either by putting the above code in a spyx file or pasting it into the notebook in a cell that starts with %cython.

Now we can do the above computation more quickly:

sage: a = 939393; b = 19393; c = 39390283
sage: time for _ in range(10000): a = muladd(a,b,c)
CPU times: user 0.11 s, sys: 0.05 s, total: 0.15 s

To squeeze out even more performance we can put the entire loop in a single function.

cimport sage.rings.integer
def muladdloop(sage.rings.integer.Integer a,
	       sage.rings.integer.Integer b,
	       sage.rings.integer.Integer c, 
	       int n):
    cdef int i
    cdef mpz_t t
    cdef sage.rings.integer.Integer aa
    aa = sage.rings.integer.Integer(a)
    mpz_init(t)

    for i from 0 <= i < n:
        mpz_mul(t, aa.value, b.value)
        mpz_add(aa.value, t, c.value)

    mpz_clear(t)
    return aa

We then have

sage: a = 939393; b = 19393; c = 39390283
sage: time z=muladdloop(a,b,c,10000)
CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s
This is a little faster.

See About this document... for information on suggesting changes.