Ask Your Question
1

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

asked 2022-09-05 19:38:04 +0100

Vibap gravatar image

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 flag offensive close merge delete

Comments

2

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

Max Alekseyev gravatar imageMax Alekseyev ( 2022-09-06 03:03:53 +0100 )edit

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

Vibap gravatar imageVibap ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2022-09-06 17:09:11 +0100 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2022-09-06 22:28:23 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
3

answered 2022-09-05 23:27:48 +0100

tmonteil gravatar image

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.

edit flag offensive delete link more

Comments

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?

Vibap gravatar imageVibap ( 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?

John Palmieri gravatar imageJohn Palmieri ( 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.

Vibap gravatar imageVibap ( 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.

Vibap gravatar imageVibap ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2022-09-06 19:04:00 +0100 )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

1 follower

Stats

Asked: 2022-09-05 19:38:04 +0100

Seen: 330 times

Last updated: Sep 05 '22