Runtimes

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 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.