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

edit retag close merge delete

What group did you try it on?

( 2020-02-25 15:47:54 +0200 )edit

I tried on unit groups of some Zmod(m)'s.

( 2020-02-25 16:42:29 +0200 )edit

You wouldn't be doing this on large groups, so I expect that the multiplication in h *= g and the exponentiation in g^i get swamped in all the overhead. It's hard nowadays to measure the "actual" complexity of operations, partially because software like GMP is 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 assign id=G.identity() before the while loop and use id instead, you'll get a more measurable performance increase. Whether replacing it with a more specific test like h.is_one() makes it faster is a toss-up.

( 2020-02-25 19:16:08 +0200 )edit

I tried with

minp = 50000000
p = next_prime(minp)
G = Zmod(p).unit_group()
g = G.gen()


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.

( 2020-02-26 00:10:30 +0200 )edit

Sort by » oldest newest most voted

When you finish running G = Zmod(m).unit_group() all the hard work is already done: a set of generators $g_i$ and their orders $n_i$ is computed, and elements are internally represented by the exponents of the generators. Exponentiation g^k of an element g in G is internally just multiplying each exponent by k and reducing modulo $n_i$. Only when you request the value of an element (for example, when printing) the generators, raised to the respective powers, are actually multiplied.

When $m=p$ the unit group is cyclic of order $p-1$, so there is just a single generator of order $p-1$.

more

Ah, of course! Thanks for pointing that out (and sorry I missed it).

( 2020-02-26 23:02:37 +0200 )edit