#11429: Count integral points without PALP
----------------------------------+-----------------------------------------
Reporter: vbraun | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.1
Component: geometry | Keywords: sd31
Work_issues: | Upstream: N/A
Reviewer: Andrey Novoseltsev | Author: Volker Braun
Merged: | Dependencies: #11312
----------------------------------+-----------------------------------------
Comment(by vbraun):
3. I added a `len(pts)` to the `len(set(pts))` to clarify - the doctests
checks that all points are distinct.
6. The coordinates are permuted such that the largest edge of the
bounding box becomes the inner loop. The inner loop is optimized to run
very fast, so we save wall time by doing the maximal amount of work there.
9. No `inc` will usually be `1`. Usually you'll only have to call
`prepare_inner_loop` between two inner loops. Only if the "odometer ticks
over" you need to call `prepare_next_to_inner_loop`. In terms of the
coordinates `(x1,x2,x3,...)` of the box, the inner loop runs over `x1`. It
suffices to only call `prepare_inner_loop` as long as only `x1`, `x2`
change. You need to call `prepare_next_to_inner_loop` if more coordinates
changed from one inner loop to the next.
10. The dimension limit is only used for the machine integer
representation of inequalities. Its not a real limit, in higher dimensions
the generic Python implementation is used.
There is some overhead to avoid integer overflows and the like, which is a
good thing. Possible improvements are
- don't permute coordinates (overhead) for really really small
polyhedra, and
- allow to just count points without enumeration (since we already find
upper/lower bound in inner loop).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11429#comment:12>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
