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.
What group did you try it on?
I tried on unit groups of some Zmod(m)'s.
You wouldn't be doing this on large groups, so I expect that the multiplication in
h *= gand the exponentiation ing^iget swamped in all the overhead. It's hard nowadays to measure the "actual" complexity of operations, partially because software likeGMPis so optimized that you need really big integers before operations are not negilible compared to the memory shuffling and interpreter overhead that needs to happen anyway.In your example,
G.identity()already costs a method lookup and a function call. I suspect that if you assignid=G.identity()before the while loop and useidinstead, you'll get a more measurable performance increase. Whether replacing it with a more specific test likeh.is_one()makes it faster is a toss-up.I tried with
Then computed (as above) the order of
g. This is pretty large, and still the first (computing powers) takes 215s and the second 207s. So it's better, but I expected a larger difference with that many iterations.