Opened 10 years ago

Closed 10 years ago

#11725 closed enhancement (fixed)

Generate random elements of the algebraic field

Reported by: rbeezer Owned by: AlexGhitza
Priority: minor Milestone: sage-4.7.2
Component: algebra Keywords: random, QQbar, sd32
Cc: spice Merged in: sage-4.7.2.alpha3
Authors: Rob Beezer Reviewers: Simon Spicer, Leif Leonhardy
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by leif)

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:

  1. Degree 2 is the default so that some complex numbers are generated.
  2. Might create constant polynomials, so a monic term (of random degree) may be added.
  3. Could be some efficiencies to be gained by not creating all the roots and choosing just one, but this should be a good start.
  4. Real goal was random vectors over QQbar. A doctest demonstrates how control of the integer coefficients can be passed from random_vector() to the QQbar.random_element() to ZZ.random_element().

Apply

  1. trac_11725-random-algebraic-numbers3.patch
  2. trac_11725-fix_doctest_error.reviewer.patch

to the Sage library.

Attachments (4)

trac_11725-random-algebraic-numbers.patch (5.3 KB) - added by rbeezer 10 years ago.
trac_11725-random-algebraic-numbers2.patch (5.3 KB) - added by spice 10 years ago.
Replaces previous patch
trac_11725-random-algebraic-numbers3.patch (5.3 KB) - added by spice 10 years ago.
Replaces previous patch
trac_11725-fix_doctest_error.reviewer.patch (779 bytes) - added by leif 10 years ago.
Reviewer patch. Fixes doctest error in multi_polynomial_element.py. Apply on top of the other patch.

Download all attachments as: .zip

Change History (16)

Changed 10 years ago by rbeezer

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Cc spice added
  • Description modified (diff)
  • Status changed from new to needs_review

Changed 10 years ago by spice

Replaces previous patch

comment:2 Changed 10 years ago by spice

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

Changed 10 years ago by spice

Replaces previous patch

comment:3 Changed 10 years ago by spice

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 rbeezer

  • 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 spice

  • Status changed from needs_review to positive_review

comment:6 Changed 10 years ago by spice

No prob

:-) Simon

comment:7 Changed 10 years ago by rbeezer

  • Keywords sd32 added

comment:8 follow-up: Changed 10 years ago by leif

  • 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 leif

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 leif

  • Work issues changed from Fix doctest error; optionally also the Sphinx warnings introduced by someone else. to Fix doctest error.

Replying to leif:

Would be nice if you could fix these here as well though [...]

Forget that; I've now fixed them at #10981.

Changed 10 years ago by leif

Reviewer patch. Fixes doctest error in multi_polynomial_element.py. Apply on top of the other patch.

comment:11 Changed 10 years ago by leif

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

comment:12 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.