#11138: Make Jacobi symbol
----------------------------------------------------+-----------------------
Reporter: kcrisman | Owner: was
Type: enhancement | Status: needs_work
Priority: minor | Milestone:
Component: number theory | Keywords: beginner
Author: Taylor Dupuy | Upstream: N/A
Reviewer: François Bissey, Karl-Dieter Crisman | Merged:
Work_issues: |
----------------------------------------------------+-----------------------
Comment(by kcrisman):
{{{
INPUT:
}}}
should be
{{{
INPUT:
}}}
I think. You'll also want to make sure the description looks more like
{{{
The jacobi symbol asf;lkjas owepiuf
opiwu ;laksjdf;lkj sa ;daskfj
wer;kj;lajksdf;lkj
}}}
than
{{{
The jacobi symbol asf;lkjas owepiuf opiwu ;laksjdf;lkj sa ;daskfj
wer;kj;lajksdf;lkj
}}}
which is hard to view in the command line.
There is some weird grammar in the latest version.
{{{
The jacobi symbol of an odd number if...
}}}
The symbols have two inputs, right? Not sure what "of an odd number"
means without more clarification. And Jacobi should be capitalized, most
likely.
You also still don't have the convention of a or b or n worked out
properly. In fact, you might as well raise a !ValueError {{{"%s must be
odd"%b}}} or something like that, since it's an asymmetric situation but
fairly nonstandardized notation (as opposed to p for prime, for instance).
After trying two that were identical, except for replacing the factoring
and return value with
{{{
sage: def jacobi_symbol1(a,b):
if b%2==0:
raise ValueError, "n must be odd"
return kronecker_symbol(a,b)
....:
}}}
I get the following timings:
{{{
sage: timeit('jacobi_symbol(55,10000049000057)')
625 loops, best of 3: 271 µs per loop
sage: timeit('jacobi_symbol1(55,10000049000057)')
625 loops, best of 3: 8.55 µs per loop
}}}
Granted, this is a product of two relatively large primes, but
{{{
sage: n = next_prime(10^30)*next_prime(10^40)
sage: timeit('jacobi_symbol1(97,n)')
625 loops, best of 3: 8.24 µs per loop
sage: timeit('jacobi_symbol(97,n)')
<took over a minute and I got bored waiting>
}}}
really shows the difference. Make sure to use the kronecker symbol :)
Indeed, if you look in number theory texts (well, the ones that have the
Jacobi symbol as opposed to just Legendre symbol), none of them compute
the Jacobi symbol 'by hand' - they all use that definition to prove you
can do a Euclidean algorithm-style quadratic or sub-quadratic complexity.
By the way, this is normal review process for Sage; this is great for your
first contribution, please don't be discouraged! Mine needed much more
work (well, my second one did - the first one was a one-word change to
remove an unused keyword).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11138#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
