Opened 10 years ago
Last modified 10 years ago
#11725 closed enhancement
Generate random elements of the algebraic field — at Version 11
Reported by: | rbeezer | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.7.2 |
Component: | algebra | Keywords: | random, QQbar, sd32 |
Cc: | spice | Merged in: | |
Authors: | Rob Beezer | Reviewers: | Simon Spicer, Leif Leonhardy |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Random elements of QQbar default to the method implemented for the integers. This patch creates algebraic numbers via roots of random polynomials with integer coefficients.
Implementation notes:
- Degree 2 is the default so that some complex numbers are generated.
- Might create constant polynomials, so a monic term (of random degree) may be added.
- Could be some efficiencies to be gained by not creating all the roots and choosing just one, but this should be a good start.
- Real goal was random vectors over
QQbar
. A doctest demonstrates how control of the integer coefficients can be passed fromrandom_vector()
to theQQbar.random_element()
toZZ.random_element()
.
Apply
to the Sage library.
Change History (15)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Cc spice added
- Description modified (diff)
- Status changed from new to needs_review
Changed 10 years ago by
comment:2 Changed 10 years ago by
- Description modified (diff)
- Keywords random QQbar added
- Reviewers set to Simon Spicer
Seems mostly fine to me. It would be easy to get bogged down as to what the default behaviour of QQbar.random_element()
should be, but as implemented here this seems a reasonable first step. I did a test and found that with default parameters QQbar.random_element()
returns zero about 15% of the time, nonzero real numbers about 60% of the time, and nonzero imaginary numbers about 7% of the time:
sage: L = [] sage: for j in range(5000): ....: L.append(QQbar.random_element()) ....: sage: RDF(L.count(0))/len(L) 0.133 sage: C = [r.imag() == 0 and r != 0 for r in L] sage: RDF(C.count(True))/len(C) 0.6194 sage: D = [r.real() == 0 and r != 0 for r in L] sage: RDF(D.count(True))/len(D) 0.066
The doctests all work and illustrate the new behaviour well. I fixed a few spelling errors, one grammatical error and added extra info in one other place:
- ``poly_degree`` - default: 2 - degree of the random polynomial over the integers that the algebraic number is a root of.
becomes
- ``poly_degree`` - default: 2 - degree of the random polynomial over the integers of which the returned algebraic number is a root.
And
For example if we do not include zero as a possible coefficient, there will never be a zero constant term, and thus never a zero root. ::
becomes
For example, current default behaviour of this method returns zero about 15% of the time; if we do not include zero as a possible coefficient, there will never be a zero constant term, and thus never a zero root. ::
I've uploaded the updated patch. These are trivial changes, but I suppose this should be re-reviewed before it can be given a positive review.
comment:3 Changed 10 years ago by
New patch uploaded in which the following if statement is removed (since it never triggers):
if len(roots) == 0: print "FUBAR", p
comment:4 Changed 10 years ago by
- Description modified (diff)
All the changes look good to me. I'll let you flip this to positive review.
Thanks for your help with this one - it'll be good to have available.
Rob
comment:5 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:6 Changed 10 years ago by
No prob
:-) Simon
comment:7 Changed 10 years ago by
- Keywords sd32 added
comment:8 follow-up: ↓ 10 Changed 10 years ago by
- Status changed from positive_review to needs_work
- Work issues set to Fix doctest error; optionally also the Sphinx warnings introduced by someone else.
This is easily fixed:
sage -t -long -force_lib "devel/sage/sage/rings/polynomial/multi_polynomial_element.py" ********************************************************************** File ".../sage-4.7.2.alpha3-pre2/devel/sage/sage/rings/polynomial/multi_polynomial_element.py", line 101: sage: x + QQbar.random_element() # indirect doctest Expected: x - 2 Got: x + 4 ********************************************************************** 1 items had failures: 1 of 5 in __main__.example_2 ***Test Failed*** 1 failures.
I also get two Sphinx warnings for qqbar.py
; as far as I can see (regarding the line numbers) these originate from another patch:
.../sage-4.7.2.alpha3-pre2/local/lib/python2.6/site-packages/sage/rings/qqbar.py:docstring of sage.rings.qqbar:476: (WARNING/2) Literal block expected; none found. .../sage-4.7.2.alpha3-pre2/local/lib/python2.6/site-packages/sage/rings/qqbar.py:docstring of sage.rings.qqbar.AlgebraicReal:5: (WARNING/2) Literal block expected; none found.
Would be nice if you could fix these here as well though; my "patch queue" for qqbar.py
is:
changeset: 16112:799c68fc8e9b user: Rob Beezer <beezer@ups.edu> date: Tue Aug 23 16:49:09 2011 -0700 summary: 11725: random elements of QQbar changeset: 16084:2d91134795c5 user: Simon King <simon.king@uni-jena.de> date: Tue Apr 19 10:12:21 2011 +0200 summary: #9138: Use the category framework for rings. changeset: 16075:9baeb151c9a7 user: William Stein <wstein@gmail.com> date: Tue Aug 23 21:36:19 2011 -0700 summary: trac 10981 -- buggy arithmetic in AA, and other issues ... [from previous Sage releases]
So apparently one of the two others (#10981, #9138) causes them, but you could (or should) base your patch(es) on these anyway.
comment:9 Changed 10 years ago by
Replying to leif:
I also get two Sphinx warnings for
qqbar.py
; as far as I can see (regarding the line numbers) these originate from another patch:
.../sage-4.7.2.alpha3-pre2/local/lib/python2.6/site-packages/sage/rings/qqbar.py:docstring of sage.rings.qqbar:476: (WARNING/2) Literal block expected; none found. .../sage-4.7.2.alpha3-pre2/local/lib/python2.6/site-packages/sage/rings/qqbar.py:docstring of sage.rings.qqbar.AlgebraicReal:5: (WARNING/2) Literal block expected; none found.
[...] So apparently one of the two others (#10981, #9138) causes them, but you could (or should) base your patch(es) on these anyway.
Ah, yes, the BDFL's patch at #10981 causes these; the double colons after TESTS
have to be changed to single ones twice.
comment:10 in reply to: ↑ 8 Changed 10 years ago by
- Work issues changed from Fix doctest error; optionally also the Sphinx warnings introduced by someone else. to Fix doctest error.
Changed 10 years ago by
Reviewer patch. Fixes doctest error in multi_polynomial_element.py
. Apply on top of the other patch.
comment:11 Changed 10 years ago by
- Description modified (diff)
- Reviewers changed from Simon Spicer to Simon Spicer, Leif Leonhardy
- Status changed from needs_work to positive_review
- Work issues Fix doctest error. deleted
Attached reviewer patch fixes the doctest error.
Replaces previous patch