[ET Trac] #2925: overflow in rat<int64> in Arith

[Roland Haas]

#2925: overflow in rat<int64> in Arith

 Reporter: Roland Haas
   Status: new
Milestone: 
  Version: 
     Type: bug
 Priority: minor
Component: 

Arith implements rational numbers which are used by CarpetX to track iterations on refinement levels, so that it can handle the fractional times of the coarse step that are used by refined levels. 

In https://github.com/EinsteinToolkit/CarpetX/pull/377#pullrequestreview-3994686849 I had to find the maximum and minimum iteration used during interpolation and a code putting an elephant in a known location:

```
diff --git a/CarpetX/src/interpolate.cxx b/CarpetX/src/interpolate.cxx
index eee39a9a..2c490c68 100644
--- a/CarpetX/src/interpolate.cxx
+++ b/CarpetX/src/interpolate.cxx
@@ -664,6 +664,11 @@ extern "C" void CarpetX_Interpolate(const CCTK_POINTER_TO_CONST cctkGH_,
     givis.at(v) = {gi, vi};
   }

+  rat64 min_level_iteration_used =
+      std::numeric_limits<decltype(min_level_iteration_used.num)>::max();
+  rat64 max_level_iteration_used =
+      std::numeric_limits<decltype(max_level_iteration_used.num)>::min();
+  bool requires_interpolation_in_time = false;
   for (const auto &patchdata : ghext->patchdata) {
     const int patch = patchdata.patch;
     for (const auto &leveldata : patchdata.leveldata) {
@@ -676,6 +681,11 @@ extern "C" void CarpetX_Interpolate(const CCTK_POINTER_TO_CONST cctkGH_,
         const GridDesc grid(leveldata, mfp);
         // const int component = mfp.index();

+        min_level_iteration_used =
+            std::min(min_level_iteration_used, leveldata.iteration);
+        max_level_iteration_used =
+            std::max(max_level_iteration_used, leveldata.iteration);
+
         const int np = pti.numParticles();
         const auto &particles = pti.GetArrayOfStructs();
```

fails as pointed out in the comment by Yosef since `min(rat64,rat64)` computes products of numerator and denominator which are guaranteed to overflow given that one numerator is `INT64_MAX`.

For this special case the workaround is to keep track of whether one has already set the min / max candidate, but the issue is present in general in that overflows can happen.

Generic routines to compare that avoid overflows would require for example repeated divisions with remainders or having access to a double-length variable type (but there's not `int128_t` in C++). 

For use as an iteration counter (since Cactus's `cctk_iteration` is 32 bits only) a rat32 would be sufficient, which would provide access to `int64_t` for the multiplication as an intermediate result.

This ticket exists solely to record the fact that this is a known issue.

--
Ticket URL: https://bitbucket.org/einsteintoolkit/tickets/issues/2925/overflow-in-rat-in-arith
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.einsteintoolkit.org/pipermail/trac/attachments/20260326/934c95c1/attachment.htm>