Ask Your Question

Revision history [back]

Performance Question

I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:

def naive_find_order1(g):
    G = g.parent()
    i = 1
    while g^i != G.identity():
        i += 1
    return i

I told them that this was wasteful, as it computes powers in every iteration, and suggested:

def naive_find_order2(g):
    G = g.parent()
    i = 1
    h = g
    while h != G.identity():
        h *= g
        i += 1
    return i

On the other hand, when testing both, they run in practically the same amount of time.

My question is how is that so? The second function only performs one multiplication in the group per loop, while the first I assume computes powers in every iteration. Does Sage/Python cache the powers? Any insight would be greatly appreciated.