TODO tracker

[jk-jeon]

Possibly not all of these will eventually get implemented, but I just need some place to write down all ideas that passed through me.

New algorithms

• Gauss' continued fraction for natural log has better error bound. In the recurrence relation for $q_{n}$, if we define $g_{n}:=qq_{n} - np^{2}q_{n-1}$ then we get a recurrence relation for $(q_{n},g_{n})$ solely consisting of positive entries. I guess this will lead to a better error bound. The current implementation just works, so this is of low priority.
• Add continued fraction of general square-roots, which must have eventually periodic continued fraction expansions. Figuring out the exact expansion may require me to study a bit more about relationship between quadratic forms and linear fractional mappings. It sounds cool, but I don't have any particular application, so this is of low priority.
• In find_xi_zeta_region, I need to split the part where the affine constraints are populated and the part where the actual region is computed. It turns out, the constraints we get out of $\left\lfloor nx + y \right\rfloor = \left\lfloor n\xi + \zeta \right\rfloor$ is just one special case of more general types of inequalities which should be solvable with an almost identical method of finding out the small list of $n$'s whose associated affine constraint can potentially pass through an extreme point. A potential application is an integer formatting algorithm that generalizes James Edward Anhalt III's algorithm: we need to find $(\xi,\zeta)$ satisfying $\left\lceil nx\right\rceil \leq n\xi + \zeta < \left\lceil nx + x\right\rceil$. I'm expecting that this may yield an algorithm that requires less number of bits than the ones I already know (using either floor or floor + 1). I will need to include empty and infinite_cone as new region types if I want to include such a generalization.
• Algorithm for iterating over $\frac{1}{2^{k}}$-lattice points in polygonal regions. This includes: (1) a function for finding the minimum $k$ such that the region is nonempty, and (2) a function for iterating over lattice points for given $k$.
• I may need some functions for computing the intersection of polygonal regions. Or maybe generalize find_xi_zeta_region enough so that I don't need to.
• Opposite algorithm of find_xi_zeta_region. That is, given $x,y,\xi,\zeta$, find the range of $n$ such that $\left\lfloor nx + y\right\rfloor = \left\lfloor n\xi+\zeta\right\rfloor$ holds. A rough idea is that, as $n$ increases, the max/min of $\frac{\left\lfloor nx+y\right\rfloor - \zeta}{n}$ increases/decreases, so we just need to find $n$ where this crosses $\xi$.
• An algorithm for solving $\lfloor nx \rfloor \equiv \lfloor n\xi \rfloor\ \mathrm{mod}\ D$.

API design

• Wrap variable_shape_region into a custom type rather just aliasing std::variant like I did for variable_shape_interval. Needed if I want to (1) have variable_shape_region with only certain types of regions are allowed, and (2) in particular let variable_shape_region be just an alias of one of static region types when there is only one allowed region type, and (3) have better API's, e.g. have region_type() member function.
• Better util::constexpr_assert that prints the actual source location on error. Maybe doable with std::source_location?
• More reliable distinction of signed vs unsigned integer types, and come up with a better way to reliably get a "value-like" type generically.
• Custom interval_estimate_provider facade for unary_gosper and binary_gosper. Just track convergents and apply inverse transform to the interval for the complete fraction.
• More robust type_erased? Not quite sure how it works when tracking_data and facade are specialized.
• Can we simplify the current callback mess with coroutine?
• Be clearer about exception safety guarantees. I don't expect strong guarantee to be achievable, but I have to revisit things to make sure everything provides the weak guarantee. If that's impossible to achieve, I have to document it.
• What would be the best way to allow having the answers as constexpr variables? bigint stuffs may need some allocator, and interval stuffs may need "flattening" into statically shaped intervals.

General project quality

• Learn how to use CI tools properly. Why is it not running lol
• More, more tests! At this moment there are many subroutines that has never been tested in isolation.
  • Learn how to use code coverage tools, if there is any that I can use for free. The one Boost.CharConv is using seemed really cool.
  • I need to think about how to test find_xi_zeta_region because it's really hard to come up with an example where the correct answer can be easily verified by hand. This should be attacked from multiple angles, one might be to match the result with find_xi_zeta_region_simultaneous_floor. One rough idea for another angle is that, we parameterize the boundary curve of the region, choose some small step size and then iterate over the boundary. If the current boundary line segment is contained in the region, then verify that $\left\lfloor nx+y\right\rfloor$ and $\left\lfloor nx+y\right\rfloor$ are equal for all $n$. Also, verify that the equality does not hold for some $n$ if we replace $(\xi,\zeta)$ by $(\xi,\zeta)+\epsilon v$ where $\epsilon>0$ is a small chosen rational number and $v$ is the outward normal vector. If the current boundary line segment is not contained in the region, do the same for $(\xi,\zeta)-\epsilon v$ and $(\xi,\zeta)$. In this case, we need to ensure that $(\xi,\zeta)-\epsilon v$ is in the region.
  • There are probably many more, but right now I need to test stuffs in extended_linear_fractional_mapping
• Documentation. The project has grown too much to a point where even myself constantly forgets many details . Hopefully, making a documentation not only helps understanding the code but also enforces me to clarify some currently unclear semantics, and further figures out unneeded complexities that previously deemed to be needed. In any case, this is a must if I ever want this project to be really usable by other people.
  • Learn how to use some tools for making decent documentation. The most boring part of OSS development I guess but I need to grow up at some point 🙂
• Disable useless warnings that are turned on by ut. Or I may need to migrate into ut2.
• Module support.
• Be more FetchContent friendly.