In this demo, we will compute some Sage runtimes and graph them.

Here are actual runtimes. You may want to repeat this if you get something weird; it could depend on what the Sage server is doing!

This one is an algorithm which does not depend on $n$:

 

This one is an algorithm that does a fixed task for each bit of $n$. The graph is showing runtime vs. bitlength of n.

 

This is an algorithm that runs a doubly-nested loop through the bits of n:

 

For comparison, here’s an algorithm that does a fixed task $n$ times instead of once per bit of $n$:

 

Let’s try modular exponentiation as Sage implements it. Some fun tips to try here: try making the modulus small. Sage really ought to know it can reduce the exponent modulo phi(n) before doing the successive squaring algorithm, but it doesn’t appear to try. Probably the reason is that factoring n to compute phi(n) is expensive.

 

Let’s try the Euclidean algorithm as Sage implements it. This is interesting, since the gcd has a lot of variation depending on the factorization of $n$, and there’s probably a fixed overhead built into the runtime, etc.