src/math/rational_approx/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../opt/bsearch/lib.hpp" | ||
| 4 | #include "../../util/alias/others/lib.hpp" | ||
| 5 | #include "../../util/traits/math/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | // @return {xl/yl, xr/yr} such that: | ||
| 10 | // 1. xl/yl < f < xr/yr | ||
| 11 | // 2. xl/yl be maximal | ||
| 12 | // 3. xr/yr be minimal | ||
| 13 | // 4. 0 <= xl,xr,yl,yr <= n | ||
| 14 | template <uint_c T> | ||
| 15 | 2440886 | CEXP ptt<ptt<T>> rational_approx(T n, ptt<T> CR f) NE { | |
| 16 | 188361102 | auto ff = [](ptt<T> CR a, u32 b, ptt<T> CR c) NE { return ptt<T>{a.first * b + c.first, a.second * b + c.second}; }; | |
| 17 | 2440886 | ptt<T> lo{0, 1}, hi{1, 0}; | |
| 18 | 16150389 | while (true) { | |
| 19 | 18591275 | cu32 n1 = bsearch([&](u32 x) NE { | |
| 20 | 76046773 | const auto _ = ff(hi, x, lo); | |
| 21 |
6/6✓ Branch 0 taken 74076736 times.
✓ Branch 1 taken 1970037 times.
✓ Branch 2 taken 72653628 times.
✓ Branch 3 taken 1423108 times.
✓ Branch 4 taken 49299405 times.
✓ Branch 5 taken 23354223 times.
|
76046773 | return _.first <= n && _.second <= n && _.first * f.second <= _.second * f.first; |
| 22 | }); | ||
| 23 |
2/2✓ Branch 2 taken 449914 times.
✓ Branch 3 taken 18141361 times.
|
18591275 | if (lo = ff(hi, n1, lo); lo.first * f.second == lo.second * f.first) { |
| 24 | 449914 | hi = lo; | |
| 25 | 449914 | break; | |
| 26 | } | ||
| 27 | 18141361 | cu32 n2 = bsearch([&](u32 x) NE { | |
| 28 | 75581693 | const auto _ = ff(lo, x, hi); | |
| 29 |
6/6✓ Branch 0 taken 73411475 times.
✓ Branch 1 taken 2170218 times.
✓ Branch 2 taken 71411523 times.
✓ Branch 3 taken 1999952 times.
✓ Branch 4 taken 49279283 times.
✓ Branch 5 taken 22132240 times.
|
75581693 | return _.first <= n && _.second <= n && f.first * _.second <= f.second * _.first; |
| 30 | }); | ||
| 31 |
2/2✓ Branch 2 taken 438360 times.
✓ Branch 3 taken 17703001 times.
|
18141361 | if (hi = ff(lo, n2, hi); hi.first * f.second == hi.second * f.first) { |
| 32 | 438360 | lo = hi; | |
| 33 | 438360 | break; | |
| 34 | } | ||
| 35 |
4/4✓ Branch 0 taken 2737831 times.
✓ Branch 1 taken 14965170 times.
✓ Branch 2 taken 1552612 times.
✓ Branch 3 taken 1185219 times.
|
17703001 | if (!n1 && !n2) break; |
| 36 | } | ||
| 37 | 2440886 | return {lo, hi}; | |
| 38 | } | ||
| 39 | |||
| 40 | } // namespace tifa_libs | ||
| 41 |