# The performance speed of "len(str(n))" method and "a^b % p" method in Sage

Hi.

Using the same Jupyter Notebook, I've found that identical codes between SageMath and Python turns out that the running time of SageMath shows up much faster than the same code written in Python.

Those codes are as follows.

import timeit

def modular():
return 3**10000000 % (2**127-1)

def countlength():
return len(str(3**10000000))

print(timeit.timeit(modular, number=1))
print(timeit.timeit(countlength, number=1))


In SageMath, the running time is less than 1 second for both functions. On the other hand, the running time for "modular' is 5 times slower in Python and for the "countlengh" function, there isn't even an answer from Python.

It makes me curious, what's the magic behind the speed of SageMath?

Recently I'm working on algorithm and coding optimization so any advice from a senior would be grateful.

Thanks.

edit retag close merge delete

2

It should be more efficient to compute the first function as Mod(3,2**127-1)**10000000 which relies on modular exponentiation.

( 2022-09-06 03:03:53 +0100 )edit

@MaxAlekseyev: I've tried by myself and indeed. Thank you for so useful tip.

( 2022-09-06 11:15:36 +0100 )edit
1

In Sage, even faster is: R = Integers(2**127 - 1); R(3)**10000000: Sage's modular arithmetic is faster than Python's.

( 2022-09-06 17:09:11 +0100 )edit

John - it's same as in my comment above.

( 2022-09-06 19:42:55 +0100 )edit

No, that's what I mean: %timeit R(3)**10000000 gives a faster time than %timeit Mod(3,2**127-1)**10000000. With R defined as I did and with b=2**127-1, then %timeit Mod(3, b, R)**10000000 is comparable. So if you're going to do many computations, either pass the parent argument to Mod or compute inside the ring R.

( 2022-09-06 22:28:23 +0100 )edit

Sort by ยป oldest newest most voted

The computation of 3**10000000 is itself much faster in Sage than Python 3. This is because, when you type 3 in Sage, you do not get a Python int but a Sage integer, that relies on the GMP library (which is optimized for such computations):

sage: type(3)
<class 'sage.rings.integer.Integer'>
sage: parent(3)
Integer Ring


If you look at, the source code for the exponentitiation of such an object:

sage: a = 3
sage: a.__pow__??


you see that it will call a._pow_ (with a single underscore), and if you look at that source code:

you see that it calls the _pow_longmethod which is not available to introspection, but you can get its source code at https://git.sagemath.org/sage.git/tre... which is written in the Cython language. Everytime you see mpz..., it means that the GMP library is used.

more

Your source code link is really helpful. Could you help me where I can find a similar source code page with len(str(n)) method like you've referred to with _pow_long method?

( 2022-09-06 15:36:57 +0100 )edit
1

I think that the reason countlength is faster is because exponentiation is faster, not because of len or str. Do your experiments show otherwise?

( 2022-09-06 17:12:33 +0100 )edit

Oh, that seems plausible! I will do experiment myself with your R = Integers(2**127 - 1); R(3)**10000000 method above.

( 2022-09-06 18:01:54 +0100 )edit

@JohnPalmieri: modular function in my codes are slow but it gives an output anyway. However countlength function doesn't show even an output for the same argument number. Thus, I think experiment is needed. It would be straightforward if I can check the source code to know whether the embedded codes for the len() function are different between Python and SageMath though.

( 2022-09-06 18:10:27 +0100 )edit
1

Maybe you're right about a speed difference in str. I think that the str function for Sage integers is using the strmethod: source at https://github.com/sagemath/sage/blob.... This again is using the GMP library.

( 2022-09-06 19:04:00 +0100 )edit