ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 21 Aug 2010 13:35:55 +0200HowTo Compute Past Largest Cython Supported Wordsize (efficiently)?https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/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.Fri, 20 Aug 2010 01:29:16 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/Answer by Mike Hansen for <p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?answer=11477#post-id-11477Cython 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][1] . 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_init(f)
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)
free(s)
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.
[1]: http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-codeFri, 20 Aug 2010 02:51:00 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?answer=11477#post-id-11477Comment by ccanonc for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22965#post-id-22965for factorial(234567) the speedup increases to 28.79xFri, 20 Aug 2010 22:49:24 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22965#post-id-22965Comment by ccanonc for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22955#post-id-22955nbruin: Why is the factorial answer "dumb"? It's a common hello world program.Sat, 21 Aug 2010 07:50:29 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22955#post-id-22955Comment by ccanonc for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22949#post-id-22949Ah, well as I'm just learning Cython, I found it helpful. I did not mind that it reproduced an existing command. Thanks.Sat, 21 Aug 2010 13:35:55 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22949#post-id-22949Comment by nbruin for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22950#post-id-22950"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. Sat, 21 Aug 2010 13:31:01 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22950#post-id-22950Comment by ccanonc for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22992#post-id-22992Nice. 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! ;)Fri, 20 Aug 2010 12:40:54 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22992#post-id-22992Comment by nbruin for <p>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.</p>
<p>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 <a href="http://www.sagemath.org/doc/tutorial/programming.html#creating-compiled-code">Creating Compiled Code</a> . After declaring the appropriate functions in the heading, it basically boils down to:</p>
<pre><code>def factorial(int n):
cdef mpz_t f
cdef int i
cdef char* s
mpz_init(f)
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)
free(s)
return r
</code></pre>
<p>Check the referenced file for the complete example.</p>
<p>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.</p>
https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22957#post-id-22957It 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 exmplSat, 21 Aug 2010 02:21:12 +0200https://ask.sagemath.org/question/7600/howto-compute-past-largest-cython-supported-wordsize-efficiently/?comment=22957#post-id-22957