Ask Your Question
1

Performance Question

asked 2020-02-25 15:07:17 +0200

lrfinotti gravatar image

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 flag offensive close merge delete

Comments

What group did you try it on?

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

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

lrfinotti gravatar imagelrfinotti ( 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.

nbruin gravatar imagenbruin ( 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.

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

1 Answer

Sort by ยป oldest newest most voted
1

answered 2020-02-26 11:11:12 +0200

rburing gravatar image

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

edit flag offensive delete link more

Comments

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

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-02-25 15:07:17 +0200

Seen: 359 times

Last updated: Feb 26 '20