Ask Your Question

HowTo Compute Past Largest Cython Supported Wordsize (efficiently)?

asked 2010-08-20 01:29:16 +0200

ccanonc gravatar image

updated 2011-05-12 23:57:35 +0200

Kelvin Li gravatar image

Say I compute over a domain where my largest Cython cdef is ___ unsigned bits. Having enjoyed the wonderful Cython speedup this long, does Cython let me continue at arbitrary precisions past the largest supported word size? Any contrived example will do (for an answer, assuming it works!) Please and thank you very much.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2010-08-20 02:51:00 +0200

Mike Hansen gravatar image

Cython doesn't magically let you do arithmetic at arbitrary precisions at the same speed as arithmetic with native machine types. If you need to support arbitrary precision calculations, you need use a datatype that supports them. In the easiest case, you could use Python's integers, but that has a speed overhead which you are probably trying to avoid. You'll likely need to use GMP/MPIR directly.

There is an example of creating a Cython file that uses GMP/MPIR directly in $SAGE_ROOT/examples/programming/sagex/factorial.spyx . This is mentioned in the Sage tutorial under the section Creating Compiled Code . After declaring the appropriate functions in the heading, it basically boils down to:

def factorial(int n):
    cdef mpz_t f
    cdef int i
    cdef char* s

    mpz_set_si(f, n)

    for i from 2 <= i <= n-1:
        mpz_mul_si(f, f, i)
    s = mpz_get_str(NULL, 32, f)

    r = int(s, 32)
    return r

Check the referenced file for the complete example.

It might be a nice feature or plugin to Cython where you could do "cdef mpz_t x" and have statements like "x+2" be converted into the appropriate GMP/MPIR function call. One could envision a similar thing for MPFR types. However, I do not know how feasible it would be to implement such a thing.

edit flag offensive delete link more


Nice. math.factorial(100000) took 50.66 seconds, and your cython factorial took 2.31 seconds; a speedup of 21.93x! Very nice encouragement for a new cython developer! ;)

ccanonc gravatar imageccanonc ( 2010-08-20 12:40:54 +0200 )edit

for factorial(234567) the speedup increases to 28.79x

ccanonc gravatar imageccanonc ( 2010-08-20 22:49:24 +0200 )edit

It depends on your application whether directly interfacing GMP is worth the effort: {{{ import sage.rings.integer_ring def dumb_cython_factorial(int n): R=sage.rings.integer_ring.ZZ(n) for i from 2 <= i <= n-1: R *= i return R }}} only gives a 15% time penalty on the exmpl

nbruin gravatar imagenbruin ( 2010-08-21 02:21:12 +0200 )edit

nbruin: Why is the factorial answer "dumb"? It's a common hello world program.

ccanonc gravatar imageccanonc ( 2010-08-21 07:50:29 +0200 )edit

"dumb" as in "not a smart way to calculate it". Compare time with the "factorial" command in sage. The point of the example (which came out horribly formatted) is that it just uses the sage Integer type, which is a good GMP wrapper, saving you the memory management.

nbruin gravatar imagenbruin ( 2010-08-21 13:31:01 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2010-08-20 01:29:16 +0200

Seen: 7,282 times

Last updated: Aug 20 '10