Opened 9 years ago
Closed 9 years ago
#11138 closed enhancement (fixed)
Make Jacobi symbol
Reported by: | kcrisman | Owned by: | was |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.7.1 |
Component: | number theory | Keywords: | beginner |
Cc: | Merged in: | sage-4.7.1.alpha4 | |
Authors: | Taylor Dupuy | Reviewers: | François Bissey, Karl-Dieter Crisman |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
We have Kronecker symbol and Legendre symbol, but not Jacobi symbol. It is a method for integers, I think, but not a global one. It would be nice to have, at the very least for pedagogical purposes so that one doesn't have to explain why it's called Kronecker but we haven't introduced that... anyway, this would require a little checking for appropriate input, but otherwise should be easy to make jacobi_symbol
.
Apply only 11138_rebased.patch
Attachments (6)
Change History (18)
Changed 9 years ago by
comment:1 follow-up: ↓ 2 Changed 9 years ago by
There is a test class that is not passing (10|777)==-1 (if I'm reading the errors right). I'm not sure what is wrong because when I make the same program in a notebook it seems to work. This is my first patch.
comment:2 in reply to: ↑ 1 Changed 9 years ago by
Replying to tdupu:
There is a test class that is not passing (10|777)==-1 (if I'm reading the errors right). I'm not sure what is wrong because when I make the same program in a notebook it seems to work. This is my first patch.
Could you paste the exact output? Another thing: it would be good if your input matched your documentation. Your function takes a and b and the documentation talks about x and n.
comment:3 Changed 9 years ago by
- Reviewers set to François Bissey, Karl-Dieter Crisman
- Status changed from new to needs_work
Thanks for your efforts, Taylor!
There are some things that should be done for this patch to pass muster.
- You definitely need more doctests. There are lots of models in this same file as models. I would use the model of
legendre_symbol
, since it tests for catching illegal input. - Your formatting is off. Check the docs for
kronecker_symbol
to see 'exactly' how things like examples and input should be formatted. - I'm not sure why you don't just pass to
kronecker_symbol
, which is optimized, after catching the invalid input. - Math should be in single ticks.
n = p1^e1 * ... * pr^er then (a|n) = (a|p1)^e1 ... (a|pr)^er where (a|pj)
versus`n = p1^e1 * ... * pr^er` then `(a|n) = (a|p1)^e1 ... (a|pr)^er` where `(a|pj)`
for the formatting in documentation. You may also need to dop_1^{e_1
} in order for it to look right - try./sage -docbuild reference html
to see what happens.
Again, thanks for helping make Sage even better!
Changed 9 years ago by
comment:4 Changed 9 years ago by
Here is the copy and paste requested
sage: l=factor(777) sage: prod([legendre_symbol(10,l[i][0])^(l[i][1]) for i in range(len(l))]) -1
when I run jacobi_symbol(10,777) it returns zero:
sage: jacobi_symbol(10,777) 0
Let me know if my formatting isn't correct. I didn't change to the Kronecker Symbol.
comment:5 Changed 9 years ago by
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).
Changed 9 years ago by
comment:6 Changed 9 years ago by
Ok. So this time it passed all the tests. The only issue could be the documentation. Dang it... I just checked. I copied and pasted the note from the Legendre Symbol and I need to fix this... don't review this until I fix that.
Changed 9 years ago by
comment:7 Changed 9 years ago by
Ok, I think I took care of all the issues. The function works quickly, the documentation appears to be correct and it passed all of the doc tests.
comment:8 Changed 9 years ago by
- Status changed from needs_work to needs_review
Great work, and doc looks great as well.
The only things that remain to be fixed is that you didn't include a commit message (see here, item 6, and a couple very minor typos.
Since this is your first patch, I've fixed those for you as a reviewer prerogative (this is fairly typical). Thank you for doing this!
Incidentally, I'm not getting the failure that the buildbot reports, which seems TOTALLY unrelated.
Changed 9 years ago by
comment:9 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Apply only trac11138.4-with-commit-message.patch.
comment:10 Changed 9 years ago by
- Milestone set to sage-4.7.1
comment:11 Changed 9 years ago by
- Description modified (diff)
comment:12 Changed 9 years ago by
- Merged in set to sage-4.7.1.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
a jacobi symbol function for sage/rings/arith.py