#15389: An algorithm for enumerating elements of bounded height in number fields
-------------------------------------+-------------------------------------
Reporter: dkrumm | Owner: dkrumm
Type: enhancement | Status: new
Priority: minor | Milestone: sage-5.13
Component: number theory | Resolution:
Keywords: sage-days55 | Merged in:
Authors: David Krumm, John | Reviewers:
Doyle | Work issues:
Report Upstream: N/A | Commit:
Branch: | b81322cb555becf5b44cf6a8419dbaf737f8f4fd
u/jdoyle/bdd_height | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Hi,
Good work! There are some things that need to be changed and others that
can be improved (not necessarily in this ticket but it might be a good
idea to think about it). First of all about syntax and tests:
1) your tests do not work: if you do bdd_height(K,100) in a console the
function bdd_height simply does not exists. You should put the line
{{{
from sage.rings.number_field.bdd_height import bdd_height
}}}
at the begining of the tests.
2) There are many syntax errors in the documentation:
- the lines must not be longer than 80 characters.
- the documentation of each function should start with a short sentence
of one line. Then you can add some more documentation after a break line.
- the syntax for the block of examples is not good
- ...
For all that, you may have look at the Sage developer guide or even better
at other files in the source code (like number_field.py)
3) for your functions there is no need of having an underscore. It is
required to have "private" method into classes but it is not needed for
functions.
4) the name of functions that are actually used by users should not be
abreviated (unless it is as common as det for the determinant). I would
prefer having bounded instead of bdd.
About algorithmic
5) Why did you choose 100 as default precision for your floating point
numbers? It makes no sense. Either you use the default Sage value or you
actually guarantee the result. Moreover you do computations using floating
point numbers and then suddenly, at line 500, you switch to rational
numbers! It seems to me that you use rational numbers for finding your
integer points in the polytope. If you intend to use floating point
approximation it makes more sense to use RDF (as there is an highly
optimized search for integer points in polyhdera). Much more important,
using floating point approximation is always dangerous as you get errors
each time you do an operation. It is not a trouble if you have control on
your quantities (for example you can safely invert a matrix in RDF as soon
as A and A^-1^ are reasonably small). So, if you want your result to be
the good result (meaning that you have all the points and no more) then
you should either take more care with floating point numbers or use proven
arithmetic (like arithmetic interval, which is implemented in Sage or ball
arithmetic etc). Using interval arithmetic is slow so it is not a good
advice to use it here.
6) There are a lot of simplification that you can do. For example the
lines 291-298
{{{
# Create polyhedron from transformed vertices and find integer points
inside
int_points = Polyhedron(transformed_vertices,
base_ring=QQ).integral_points()
# Return these integer vectors as tuples
int_point_tuples = []
for vec in int_points:
int_point_tuples.append(tuple(vec))
return int_point_tuples
}}}
can be replaced by two (much faster) line
{{{
# Return integer points in the polyhedron
return map(tuple, Polyhedron(transformed_vertices,
base_ring=QQ).integral_points())
}}}
And by the way, why do you need to convert the result into tuples?
7) It would make sense to have an iterator rather than an actual list
(i.e. a method K.element_of_bounded_height_iterator(500) that returns an
iterator and not a list). Most of the time, I guess that people want to
use this method to test conjecture or such. So what they want is for each
element in that list check some conjecture with that input. Have a look at
[[http://sagemath.org/doc/thematic_tutorials/tutorial-programming-
python.html|Tutorial: Programming in Python and Sage]].
--
Ticket URL: <http://trac.sagemath.org/ticket/15389#comment:3>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
