ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 26 Feb 2020 23:02:37 +0100Performance Questionhttps://ask.sagemath.org/question/50057/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.Tue, 25 Feb 2020 15:07:17 +0100https://ask.sagemath.org/question/50057/performance-question/Comment by rburing for <p>I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:</p>
<pre><code>def naive_find_order1(g):
G = g.parent()
i = 1
while g^i != G.identity():
i += 1
return i
</code></pre>
<p>I told them that this was wasteful, as it computes powers in every iteration, and suggested:</p>
<pre><code>def naive_find_order2(g):
G = g.parent()
i = 1
h = g
while h != G.identity():
h *= g
i += 1
return i
</code></pre>
<p>On the other hand, when testing both, they run in practically the same amount of time.</p>
<p>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.</p>
https://ask.sagemath.org/question/50057/performance-question/?comment=50058#post-id-50058What group did you try it on?Tue, 25 Feb 2020 15:47:54 +0100https://ask.sagemath.org/question/50057/performance-question/?comment=50058#post-id-50058Comment by lrfinotti for <p>I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:</p>
<pre><code>def naive_find_order1(g):
G = g.parent()
i = 1
while g^i != G.identity():
i += 1
return i
</code></pre>
<p>I told them that this was wasteful, as it computes powers in every iteration, and suggested:</p>
<pre><code>def naive_find_order2(g):
G = g.parent()
i = 1
h = g
while h != G.identity():
h *= g
i += 1
return i
</code></pre>
<p>On the other hand, when testing both, they run in practically the same amount of time.</p>
<p>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.</p>
https://ask.sagemath.org/question/50057/performance-question/?comment=50061#post-id-50061I tried on unit groups of some Zmod(m)'s.Tue, 25 Feb 2020 16:42:29 +0100https://ask.sagemath.org/question/50057/performance-question/?comment=50061#post-id-50061Comment by nbruin for <p>I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:</p>
<pre><code>def naive_find_order1(g):
G = g.parent()
i = 1
while g^i != G.identity():
i += 1
return i
</code></pre>
<p>I told them that this was wasteful, as it computes powers in every iteration, and suggested:</p>
<pre><code>def naive_find_order2(g):
G = g.parent()
i = 1
h = g
while h != G.identity():
h *= g
i += 1
return i
</code></pre>
<p>On the other hand, when testing both, they run in practically the same amount of time.</p>
<p>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.</p>
https://ask.sagemath.org/question/50057/performance-question/?comment=50066#post-id-50066You 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.Tue, 25 Feb 2020 19:16:08 +0100https://ask.sagemath.org/question/50057/performance-question/?comment=50066#post-id-50066Comment by lrfinotti for <p>I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:</p>
<pre><code>def naive_find_order1(g):
G = g.parent()
i = 1
while g^i != G.identity():
i += 1
return i
</code></pre>
<p>I told them that this was wasteful, as it computes powers in every iteration, and suggested:</p>
<pre><code>def naive_find_order2(g):
G = g.parent()
i = 1
h = g
while h != G.identity():
h *= g
i += 1
return i
</code></pre>
<p>On the other hand, when testing both, they run in practically the same amount of time.</p>
<p>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.</p>
https://ask.sagemath.org/question/50057/performance-question/?comment=50068#post-id-50068I 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.Wed, 26 Feb 2020 00:10:30 +0100https://ask.sagemath.org/question/50057/performance-question/?comment=50068#post-id-50068Answer by rburing for <p>I asked my students to write a function to check the order of an element in a multiplicative group. Most wrote something like:</p>
<pre><code>def naive_find_order1(g):
G = g.parent()
i = 1
while g^i != G.identity():
i += 1
return i
</code></pre>
<p>I told them that this was wasteful, as it computes powers in every iteration, and suggested:</p>
<pre><code>def naive_find_order2(g):
G = g.parent()
i = 1
h = g
while h != G.identity():
h *= g
i += 1
return i
</code></pre>
<p>On the other hand, when testing both, they run in practically the same amount of time.</p>
<p>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.</p>
https://ask.sagemath.org/question/50057/performance-question/?answer=50072#post-id-50072When 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$.Wed, 26 Feb 2020 11:11:12 +0100https://ask.sagemath.org/question/50057/performance-question/?answer=50072#post-id-50072Comment by lrfinotti for <p>When you finish running <code>G = Zmod(m).unit_group()</code> 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 <code>g^k</code> of an element <code>g</code> in <code>G</code> is internally just multiplying each exponent by <code>k</code> 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.</p>
<p>When $m=p$ the unit group is cyclic of order $p-1$, so there is just a single generator of order $p-1$.</p>
https://ask.sagemath.org/question/50057/performance-question/?comment=50083#post-id-50083Ah, of course! Thanks for pointing that out (and sorry I missed it).Wed, 26 Feb 2020 23:02:37 +0100https://ask.sagemath.org/question/50057/performance-question/?comment=50083#post-id-50083