Performance Question

performance

lrfinotti
31 ●1 ●5

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.

Comments

What group did you try it on?

rburing ( 5 years ago )

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

lrfinotti ( 5 years ago )

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.

nbruin ( 5 years ago )

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.

lrfinotti ( 5 years ago )

add a comment

answered 5 years ago

rburing

10964 ●4 ●80 ●219 https://www.rburing.nl/

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

link

Comments

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

lrfinotti ( 5 years ago )

add a comment

Performance Question

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Performance Question savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Performance Question