Opened 10 years ago

Last modified 10 years ago

#11725 closed enhancement

Generate random elements of the algebraic field — at Version 4

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
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

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

Change History (7)

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

Note: See TracTickets for help on using tickets.