14#include <unordered_map>
15#include <unordered_set>
35constexpr double NaN = std::numeric_limits<double>::quiet_NaN();
58const std::unordered_set<gate_t> *g_shared_base_rvs =
nullptr;
60inline bool is_shared_base_rv(
gate_t rv)
62 return g_shared_base_rvs !=
nullptr && g_shared_base_rvs->count(rv) != 0;
70void collect_reachable_base_rvs(
const GenericCircuit &gc,
gate_t start,
71 std::unordered_set<gate_t> &out)
73 std::unordered_set<gate_t> seen;
74 std::stack<gate_t> stk;
76 while (!stk.empty()) {
77 gate_t g = stk.top(); stk.pop();
78 if (!seen.insert(g).second)
continue;
91 if (mw.size() == 3) { stk.push(mw[1]); stk.push(mw[2]); }
111double try_eval_constant(
const GenericCircuit &gc,
gate_t g)
116 catch (
const CircuitException &) {
return NaN; }
122 if (wires.empty())
return NaN;
124 double first = try_eval_constant(gc, wires[0]);
125 if (std::isnan(first))
return NaN;
129 if (wires.size() == 1)
return std::round(first);
131 double d = try_eval_constant(gc, wires[1]);
132 if (std::isnan(d))
return NaN;
133 const double f = std::pow(10.0, d);
134 return std::round(first * f) / f;
137 return wires.size() == 1 ? std::floor(first) : NaN;
139 return wires.size() == 1 ? std::ceil(first) : NaN;
141 return wires.size() == 1 ? std::fabs(first) : NaN;
145 return wires.size() == 1 ? first : NaN;
147 return wires.size() == 1
148 ?
static_cast<double>(
static_cast<float>(first)) : NaN;
151 for (std::size_t i = 1; i < wires.size(); ++i) {
152 double v = try_eval_constant(gc, wires[i]);
153 if (std::isnan(v))
return NaN;
160 for (std::size_t i = 1; i < wires.size(); ++i) {
161 double v = try_eval_constant(gc, wires[i]);
162 if (std::isnan(v))
return NaN;
168 if (wires.size() != 2)
return NaN;
169 double v = try_eval_constant(gc, wires[1]);
170 if (std::isnan(v))
return NaN;
174 if (wires.size() != 2)
return NaN;
175 double v = try_eval_constant(gc, wires[1]);
179 if (std::isnan(v) || v == 0.0)
return NaN;
183 if (wires.size() != 2)
return NaN;
184 double v = try_eval_constant(gc, wires[1]);
185 if (std::isnan(v) || v == 0.0)
return NaN;
186 return std::trunc(first / v);
189 if (wires.size() != 1)
return NaN;
193 for (std::size_t i = 1; i < wires.size(); ++i) {
194 double v = try_eval_constant(gc, wires[i]);
195 if (std::isnan(v))
return NaN;
202 for (std::size_t i = 1; i < wires.size(); ++i) {
203 double v = try_eval_constant(gc, wires[i]);
204 if (std::isnan(v))
return NaN;
210 if (wires.size() != 2)
return NaN;
211 double e = try_eval_constant(gc, wires[1]);
212 if (std::isnan(e))
return NaN;
218 return std::pow(first, e);
221 if (wires.size() != 1)
return NaN;
223 return std::log(first);
225 if (wires.size() != 1)
return NaN;
226 return std::exp(first);
247bool subtree_contains_agg(
const GenericCircuit &gc,
gate_t g)
249 std::unordered_set<gate_t> seen;
250 std::stack<gate_t> stk;
252 while (!stk.empty()) {
253 gate_t cur = stk.top(); stk.pop();
254 if (!seen.insert(cur).second)
continue;
268void replace_with_value(GenericCircuit &gc,
gate_t g,
double c)
277bool is_value_equal_to(
const GenericCircuit &gc,
gate_t g,
double target)
281 catch (
const CircuitException &) {
return false; }
300bool try_identity_drop(GenericCircuit &gc,
gate_t g)
306 std::vector<gate_t> kept;
307 kept.reserve(wires.size());
309 if (!is_value_equal_to(gc, w, 0.0)) kept.push_back(w);
311 if (kept.size() == wires.size())
return false;
313 replace_with_value(gc, g, 0.0);
316 wires = std::move(kept);
322 if (is_value_equal_to(gc, w, 0.0)) {
323 replace_with_value(gc, g, 0.0);
327 std::vector<gate_t> kept;
328 kept.reserve(wires.size());
330 if (!is_value_equal_to(gc, w, 1.0)) kept.push_back(w);
332 if (kept.size() == wires.size())
return false;
334 replace_with_value(gc, g, 1.0);
337 wires = std::move(kept);
363bool is_invalid(
gate_t g) {
return g == INVALID_GATE; }
390std::optional<LinearTerm>
391decompose_linear_term(
const GenericCircuit &gc,
gate_t g)
398 catch (
const CircuitException &) {
return std::nullopt; }
399 return LinearTerm{INVALID_GATE, 0.0, v};
406 return LinearTerm{g, 1.0, 0.0};
421 return LinearTerm{g, 1.0, 0.0};
437 && wires.size() == 1) {
438 return decompose_linear_term(gc, wires[0]);
442 if (wires.size() != 1)
return std::nullopt;
443 auto inner = decompose_linear_term(gc, wires[0]);
444 if (!inner)
return std::nullopt;
445 return LinearTerm{inner->rv_gate, -inner->a, -inner->b};
449 if (wires.size() != 2)
return std::nullopt;
452 gate_t var_side = INVALID_GATE;
455 catch (
const CircuitException &) {
return std::nullopt; }
459 catch (
const CircuitException &) {
return std::nullopt; }
464 auto inner = decompose_linear_term(gc, var_side);
465 if (!inner)
return std::nullopt;
466 return LinearTerm{inner->rv_gate, c * inner->a, c * inner->b};
506bool try_sum_closure(GenericCircuit &gc,
gate_t g)
509 if (wires.size() < 2)
return false;
511 std::vector<LinearTerm> lterms;
512 lterms.reserve(wires.size());
514 auto term = decompose_linear_term(gc, w);
515 if (!term)
return false;
516 lterms.push_back(*term);
520 std::vector<std::unique_ptr<Distribution>> dists(lterms.size());
521 std::vector<ClosureTerm> terms;
522 terms.reserve(lterms.size());
523 std::unordered_set<gate_t> seen_rvs;
524 for (std::size_t i = 0; i < lterms.size(); ++i) {
525 const auto &t = lterms[i];
526 if (is_invalid(t.rv_gate)) {
527 terms.push_back({
nullptr, t.a, t.b});
530 if (!seen_rvs.insert(t.rv_gate).second)
return false;
534 if (is_shared_base_rv(t.rv_gate))
return false;
536 if (!spec)
return false;
538 terms.push_back({dists[i].get(), t.a, t.b});
542 if (!folded)
return false;
560bool try_product_closure(GenericCircuit &gc,
gate_t g)
563 if (wires.size() < 2)
return false;
565 double c_total = 1.0;
566 std::vector<std::unique_ptr<Distribution>> dists;
567 std::vector<const Distribution *> factors;
568 std::unordered_set<gate_t> seen_rvs;
573 catch (
const CircuitException &) {
return false; }
576 if (t !=
gate_rv)
return false;
577 if (!seen_rvs.insert(w).second)
return false;
578 if (is_shared_base_rv(w))
return false;
580 if (!spec)
return false;
582 factors.push_back(dists.back().get());
584 if (factors.size() < 2)
return false;
587 if (!combined)
return false;
588 if (c_total != 1.0) {
589 combined = combined->scale(c_total);
590 if (!combined)
return false;
607bool try_transform_closure(GenericCircuit &gc,
gate_t g)
613 if (!transform)
return false;
615 if (wires.size() != 1)
return false;
617 if (is_shared_base_rv(wires[0]))
return false;
619 if (!spec)
return false;
622 if (!image)
return false;
643bool try_neg_rv(GenericCircuit &gc,
gate_t g)
649 if (wires.size() != 1)
return false;
651 if (is_shared_base_rv(wires[0]))
return false;
654 if (!spec)
return false;
657 if (!negated)
return false;
693unsigned apply_rules(GenericCircuit &gc,
gate_t g,
694 bool include_scalar_fold);
713bool try_categorical_mixture_lift(GenericCircuit &gc,
gate_t g,
716 const std::vector<gate_t> &others)
729 catch (
const CircuitException &) {
return false; }
743 const std::vector<gate_t> mw = gc.
getWires(mix_gate);
745 std::vector<gate_t> new_wires;
746 new_wires.reserve(mw.size());
747 new_wires.push_back(key);
748 for (std::size_t i = 1; i < mw.size(); ++i) {
749 const gate_t old_mul = mw[i];
752 catch (
const CircuitException &) {
return false; }
756 const double p = gc.
getProb(old_mul);
757 const auto vi =
static_cast<unsigned>(gc.
getInfos(old_mul).first);
760 new_wires.push_back(new_mul);
766bool try_mixture_lift(GenericCircuit &gc,
gate_t g,
767 bool include_scalar_fold)
773 if (wires.size() < 2)
return false;
776 std::size_t mix_idx =
static_cast<std::size_t
>(-1);
777 for (std::size_t i = 0; i < wires.size(); ++i) {
779 if (mix_idx !=
static_cast<std::size_t
>(-1))
return false;
783 if (mix_idx ==
static_cast<std::size_t
>(-1))
return false;
785 const auto mix_gate = wires[mix_idx];
790 std::vector<gate_t> others;
791 others.reserve(wires.size() - 1);
792 for (std::size_t i = 0; i < wires.size(); ++i) {
793 if (i != mix_idx) others.push_back(wires[i]);
800 return try_categorical_mixture_lift(gc, g, op, mix_gate, others);
804 const auto &mw = gc.
getWires(mix_gate);
805 if (mw.size() != 3)
return false;
806 const gate_t p_tok = mw[0];
807 const gate_t x_tok = mw[1];
808 const gate_t y_tok = mw[2];
814 std::vector<gate_t> new_x_wires = others; new_x_wires.push_back(x_tok);
815 std::vector<gate_t> new_y_wires = others; new_y_wires.push_back(y_tok);
831 apply_rules(gc, new_x, include_scalar_fold);
832 apply_rules(gc, new_y, include_scalar_fold);
862bool try_times_scalar_rv(GenericCircuit &gc,
gate_t g)
867 if (wires.size() != 2)
return false;
871 gate_t rv_side = INVALID_GATE;
875 catch (
const CircuitException &) {
return false; }
880 catch (
const CircuitException &) {
return false; }
888 if (c == 0.0 || c == 1.0)
return false;
890 if (is_shared_base_rv(rv_side))
return false;
893 if (!spec)
return false;
896 if (!scaled)
return false;
902 if (
auto dirac = scaled->asDirac()) {
903 replace_with_value(gc, g, *dirac);
940bool try_plus_aggregate(GenericCircuit &gc,
gate_t g,
941 bool include_scalar_fold)
945 const auto &wires_in = gc.
getWires(g);
946 if (wires_in.size() < 2)
return false;
948 std::vector<LinearTerm> terms;
949 terms.reserve(wires_in.size());
950 for (
gate_t w : wires_in) {
951 auto t = decompose_linear_term(gc, w);
952 if (!t)
return false;
959 std::vector<std::pair<gate_t, double>> coeffs;
960 double b_total = 0.0;
961 unsigned constants_in = 0;
962 for (
const auto &t : terms) {
964 if (is_invalid(t.rv_gate)) {
969 for (
auto &p : coeffs) {
970 if (p.first == t.rv_gate) {
976 if (!found) coeffs.emplace_back(t.rv_gate, t.a);
983 const bool has_duplicate = (coeffs.size() < terms.size() - constants_in);
984 const bool many_constants = (constants_in >= 2);
985 if (!has_duplicate && !many_constants)
return false;
988 std::vector<std::pair<gate_t, double>> kept;
989 kept.reserve(coeffs.size());
990 for (
const auto &p : coeffs) {
991 if (p.second != 0.0) kept.push_back(p);
996 replace_with_value(gc, g, b_total);
1014 if (kept.size() == 1 && b_total == 0.0) {
1015 const auto &only = kept.front();
1016 if (only.second == 1.0) {
1028 std::vector<gate_t> new_wires;
1029 new_wires.reserve(kept.size() + 1);
1030 for (
const auto &p : kept) {
1031 if (p.second == 1.0) {
1032 new_wires.push_back(p.first);
1037 new_wires.push_back(tm);
1040 if (b_total != 0.0) {
1044 gc.
setWires(g, std::move(new_wires));
1051 apply_rules(gc, w, include_scalar_fold);
1066unsigned apply_rules(GenericCircuit &gc,
gate_t g,
1067 bool include_scalar_fold)
1074 for (
unsigned iter = 0; iter < 32; ++iter) {
1079 double c = try_eval_constant(gc, g);
1080 if (!std::isnan(c)) {
1081 replace_with_value(gc, g, c);
1101 const auto &wires_in = gc.
getWires(g);
1102 if (wires_in.size() == 2) {
1103 const gate_t a = wires_in[0];
1104 const gate_t b = wires_in[1];
1130 const auto &wires_in = gc.
getWires(g);
1131 if (wires_in.size() == 2 && !subtree_contains_agg(gc, wires_in[0])) {
1132 const double c = try_eval_constant(gc, wires_in[1]);
1133 if (!std::isnan(c) && c != 0.0) {
1134 const gate_t x = wires_in[0];
1147 if (try_identity_drop(gc, g)) {
1158 if (try_mixture_lift(gc, g, include_scalar_fold)) {
1171 if (try_plus_aggregate(gc, g, include_scalar_fold)) {
1188 if (try_times_scalar_rv(gc, g)) {
1201 if (try_sum_closure(gc, g)) { ++local;
break; }
1204 if (try_product_closure(gc, g)) { ++local;
break; }
1207 if (try_transform_closure(gc, g)) { ++local;
break; }
1224void simplify(GenericCircuit &gc,
gate_t g,
1225 std::unordered_set<gate_t> &done,
unsigned &counter,
1226 bool include_scalar_fold)
1232 std::stack<std::pair<gate_t, std::size_t>> stk;
1233 if (!done.insert(g).second)
return;
1236 while (!stk.empty()) {
1237 auto &frame = stk.top();
1238 gate_t cur = frame.first;
1239 const auto &wires = gc.
getWires(cur);
1240 if (frame.second < wires.size()) {
1241 gate_t child = wires[frame.second++];
1242 if (done.insert(child).second) stk.emplace(child, 0);
1247 counter += apply_rules(gc, cur, include_scalar_fold);
1256 unsigned counter = 0;
1264 for (std::size_t i = 0; i < nb; ++i) {
1265 auto g =
static_cast<gate_t>(i);
1267 double c = try_eval_constant(gc, g);
1268 if (!std::isnan(c)) {
1269 replace_with_value(gc, g, c);
1295 std::vector<signed char> &memo)
1297 const auto idx = [](
gate_t g) {
return static_cast<std::size_t
>(g); };
1298 if (memo[idx(root)] != -2)
return memo[idx(root)];
1300 std::vector<std::pair<gate_t, bool>> stack{{root,
false}};
1301 while (!stack.empty()) {
1302 auto [g, expanded] = stack.back();
1304 if (memo[idx(g)] != -2)
continue;
1306 const auto &wires = gc.
getWires(g);
1314 const double p = gc.
getProb(g);
1315 r = p == 1.0 ? 1 : p == 0.0 ? 0 : -1;
1327 stack.emplace_back(g,
true);
1329 if (memo[idx(c)] == -2) stack.emplace_back(c,
false);
1335 if (memo[idx(c)] == 1) { r = 1;
break; }
1336 if (memo[idx(c)] == -1) r = -1;
1341 if (memo[idx(c)] == 0) { r = 0;
break; }
1342 if (memo[idx(c)] == -1) r = -1;
1345 if (wires.size() != 2)
break;
1346 const auto a = memo[idx(wires[0])], b = memo[idx(wires[1])];
1347 r = (a == 0 || b == 1) ? 0 : (a == 1 && b == 0) ? 1 : -1;
1351 if (wires.empty())
break;
1352 r = memo[idx(wires[0])];
1361 return memo[idx(root)];
1368 unsigned counter = 0;
1370 std::vector<signed char> memo(nb, -2);
1371 std::unordered_map<gate_t, gate_t> subst;
1372 for (std::size_t i = 0; i < nb; ++i) {
1373 auto g =
static_cast<gate_t>(i);
1379 const auto &wires = gc.
getWires(g);
1380 if (wires.size() != 3)
continue;
1400 if (read_probabilities) {
1401 truth = selector_truth(gc, wires[0], memo);
1412 if (truth == 1 || truth == 0) {
1413 subst[g] = wires[truth == 1 ? 1 : 2];
1430 unsigned counter = 0;
1451 std::unordered_set<gate_t> shared_base_rvs;
1455 std::unordered_map<gate_t, unsigned> cmp_footprint_count;
1456 for (std::size_t i = 0; i < nb; ++i) {
1457 auto g =
static_cast<gate_t>(i);
1460 std::unordered_set<gate_t> fp;
1461 collect_reachable_base_rvs(gc, w, fp);
1462 for (
gate_t rv : fp) ++cmp_footprint_count[rv];
1465 for (
const auto &[rv, n] : cmp_footprint_count)
1466 if (n > 1) shared_base_rvs.insert(rv);
1468 for (std::size_t i = 0; i < nb; ++i) {
1469 auto g =
static_cast<gate_t>(i);
1474 if (arms.size() < 2)
continue;
1475 std::unordered_map<gate_t, unsigned> arm_count;
1476 for (
gate_t arm : arms) {
1477 std::unordered_set<gate_t> fp;
1478 collect_reachable_base_rvs(gc, arm, fp);
1479 for (
gate_t rv : fp) ++arm_count[rv];
1481 for (
const auto &[rv, n] : arm_count)
1482 if (n > 1) shared_base_rvs.insert(rv);
1485 g_shared_base_rvs = &shared_base_rvs;
1486 struct SharedGuard {
1487 ~SharedGuard() { g_shared_base_rvs =
nullptr; }
1500 std::unordered_set<gate_t> done;
1502 for (std::size_t i = 0; i < nb; ++i) {
1503 simplify(gc,
static_cast<gate_t>(i), done, counter,
1522 for (std::size_t i = 0; i < nb; ++i) {
1523 auto g =
static_cast<gate_t>(i);
1525 if (try_times_scalar_rv(gc, g)) ++counter;
1526 else if (try_neg_rv(gc, g)) ++counter;
1547 const auto &wires = gc.
getWires(cmp_gate);
1548 if (wires.size() != 2)
return false;
1550 std::unordered_set<gate_t> seen;
1551 std::stack<gate_t> stk;
1554 while (!stk.empty()) {
1555 gate_t g = stk.top(); stk.pop();
1556 if (!seen.insert(g).second)
continue;
1575 if (mw.size() != 3)
return false;
1593void collect_cmp_rv_footprint(
const GenericCircuit &gc,
gate_t cmp_gate,
1594 std::unordered_set<gate_t> &fp)
1596 std::unordered_set<gate_t> seen;
1597 std::stack<gate_t> stk;
1599 while (!stk.empty()) {
1600 gate_t g = stk.top(); stk.pop();
1601 if (!seen.insert(g).second)
continue;
1631 if (mw.size() == 3) { stk.push(mw[1]); stk.push(mw[2]); }
1660void collect_cmp_mixture_selectors(
const GenericCircuit &gc,
gate_t cmp_gate,
1661 std::unordered_set<gate_t> &sels)
1663 std::unordered_set<gate_t> seen;
1664 std::stack<gate_t> stk;
1666 while (!stk.empty()) {
1667 gate_t g = stk.top(); stk.pop();
1668 if (!seen.insert(g).second)
continue;
1677 if (mw.size() == 3) {
1699constexpr std::size_t JOINT_TABLE_K_MAX = 8;
1713bool is_analytic_singleton_cmp(
const GenericCircuit &gc,
gate_t cmp_gate)
1715 const auto &wires = gc.
getWires(cmp_gate);
1716 if (wires.size() != 2)
return false;
1757struct FastPathInfo {
1759 std::vector<ComparisonOperator> ops;
1760 std::vector<double> thresholds;
1806std::optional<FastPathInfo>
1807detect_shared_scalar(
const GenericCircuit &gc,
1808 const std::vector<gate_t> &cmps)
1811 info.ops.reserve(cmps.size());
1812 info.thresholds.reserve(cmps.size());
1816 const auto &wires = gc.
getWires(c);
1817 if (wires.size() != 2)
return std::nullopt;
1821 if (!ok)
return std::nullopt;
1826 return std::nullopt;
1829 double threshold = std::numeric_limits<double>::quiet_NaN();
1832 scalar_side = wires[0];
1834 catch (
const CircuitException &) {
return std::nullopt; }
1836 scalar_side = wires[1];
1838 catch (
const CircuitException &) {
return std::nullopt; }
1839 effective_op = flip_cmp_op(op);
1841 return std::nullopt;
1845 info.scalar = scalar_side;
1847 }
else if (info.scalar != scalar_side) {
1848 return std::nullopt;
1850 info.ops.push_back(effective_op);
1851 info.thresholds.push_back(threshold);
1882bool inline_fast_path(GenericCircuit &gc,
1883 const std::vector<gate_t> &cmps,
1884 const FastPathInfo &info,
1891 std::vector<double> ts = info.thresholds;
1892 std::sort(ts.begin(), ts.end());
1893 ts.erase(std::unique(ts.begin(), ts.end()), ts.end());
1894 const std::size_t m = ts.size();
1895 const std::size_t nb_intervals = m + 1;
1909 std::vector<double> interval_probs(nb_intervals, 0.0);
1910 bool analytical =
false;
1914 std::vector<double> cdf_at_boundary(m);
1916 for (std::size_t i = 0; i < m; ++i) {
1917 cdf_at_boundary[i] =
cdfAt(*spec, ts[i]);
1918 if (std::isnan(cdf_at_boundary[i])) { all_ok =
false;
break; }
1921 interval_probs[0] = cdf_at_boundary[0];
1922 for (std::size_t i = 1; i < m; ++i)
1923 interval_probs[i] = cdf_at_boundary[i] - cdf_at_boundary[i - 1];
1924 interval_probs[m] = 1.0 - cdf_at_boundary[m - 1];
1935 if (!allow_mc)
return false;
1940 for (
const auto &d : draws)
1941 if (!d || std::isnan(*d))
return false;
1942 for (
const auto &d : draws) {
1943 auto it = std::upper_bound(ts.begin(), ts.end(), *d);
1944 std::size_t idx =
static_cast<std::size_t
>(it - ts.begin());
1945 ++interval_probs[idx];
1947 for (
auto &p : interval_probs) p /= samples;
1956 std::vector<unsigned long> outcome_word(nb_intervals, 0);
1957 for (std::size_t i = 0; i < nb_intervals; ++i) {
1959 if (i == 0) point = ts[0] - 1.0;
1960 else if (i == m) point = ts[m - 1] + 1.0;
1961 else point = 0.5 * (ts[i - 1] + ts[i]);
1962 unsigned long w = 0;
1963 for (std::size_t j = 0; j < info.thresholds.size(); ++j) {
1964 if (apply_cmp(point, info.ops[j], info.thresholds[j]))
1967 outcome_word[i] = w;
1973 std::vector<gate_t> mul_for_interval(nb_intervals,
1974 static_cast<gate_t>(-1));
1975 for (std::size_t i = 0; i < nb_intervals; ++i) {
1976 if (interval_probs[i] <= 0.0)
continue;
1977 mul_for_interval[i] =
1979 static_cast<unsigned>(i));
1984 for (std::size_t j = 0; j < cmps.size(); ++j) {
1985 std::vector<gate_t> plus_wires;
1986 plus_wires.reserve(nb_intervals);
1987 for (std::size_t i = 0; i < nb_intervals; ++i) {
1988 if (!(outcome_word[i] & (1ul << j)))
continue;
1989 gate_t mw = mul_for_interval[i];
1990 if (mw ==
static_cast<gate_t>(-1))
continue;
1991 plus_wires.push_back(mw);
2018void inline_joint_table(GenericCircuit &gc,
2019 const std::vector<gate_t> &cmps,
2022 const unsigned k =
static_cast<unsigned>(cmps.size());
2037 const std::size_t nb_outcomes = std::size_t{1} << k;
2038 std::vector<gate_t> mul_for_outcome(nb_outcomes,
2039 static_cast<gate_t>(-1));
2040 for (std::size_t w = 0; w < nb_outcomes; ++w) {
2041 if (probs[w] <= 0.0)
continue;
2042 mul_for_outcome[w] =
2044 static_cast<unsigned>(w));
2049 for (
unsigned i = 0; i < k; ++i) {
2050 std::vector<gate_t> plus_wires;
2051 plus_wires.reserve(nb_outcomes / 2);
2052 for (std::size_t w = 0; w < nb_outcomes; ++w) {
2053 if ((w & (std::size_t{1} << i)) == 0)
continue;
2054 gate_t m = mul_for_outcome[w];
2055 if (m ==
static_cast<gate_t>(-1))
continue;
2056 plus_wires.push_back(m);
2071struct PivotIslandInfo {
2072 DistributionSpec pivotSpec;
2075 DistributionSpec other;
2079 std::vector<Factor> factors;
2086std::optional<PivotIslandInfo>
2087detect_shared_pivot_rv(
const GenericCircuit &gc,
2088 const std::vector<gate_t> &cmps)
2091 bool havePivot =
false;
2092 std::optional<DistributionSpec> pivotSpec;
2093 PivotIslandInfo info;
2094 std::unordered_set<gate_t> othersSeen;
2099 if (w.size() != 2)
return std::nullopt;
2103 return std::nullopt;
2106 gate_t pv, other;
bool pivotLeft;
2108 (!havePivot || w[0] == pivot)) { pv = w[0]; other = w[1]; pivotLeft =
true; }
2110 (!havePivot || w[1] == pivot)) { pv = w[1]; other = w[0]; pivotLeft =
false; }
2111 else return std::nullopt;
2115 if (!sp)
return std::nullopt;
2116 pivot = pv; pivotSpec = *sp; havePivot =
true;
2123 const bool trueIsGreater = pivotLeft ? greaterOp : lessOp;
2125 PivotIslandInfo::Factor f;
2126 f.trueIsGreater = trueIsGreater;
2130 catch (
const CircuitException &) {
return std::nullopt; }
2132 if (!othersSeen.insert(other).second)
return std::nullopt;
2134 if (!sp)
return std::nullopt;
2137 }
else return std::nullopt;
2138 info.factors.push_back(std::move(f));
2140 if (!havePivot)
return std::nullopt;
2141 info.pivotSpec = *pivotSpec;
2155bool inline_analytic_pivot_joint_table(GenericCircuit &gc,
2156 const std::vector<gate_t> &cmps,
2157 const PivotIslandInfo &info)
2159 const unsigned k =
static_cast<unsigned>(cmps.size());
2160 const std::size_t nb_outcomes = std::size_t{1} << k;
2164 if (!dX->integrationRange(lo0, hi0))
return false;
2167 std::vector<std::unique_ptr<Distribution>> otherDist(k);
2168 for (
unsigned j = 0; j < k; ++j)
2169 if (!info.factors[j].isConst)
2172 std::vector<double> probs(nb_outcomes, 0.0);
2173 for (std::size_t w = 0; w < nb_outcomes; ++w) {
2175 double lo = lo0, hi = hi0;
2176 for (
unsigned j = 0; j < k; ++j) {
2177 if (!info.factors[j].isConst)
continue;
2178 const bool bit = (w >> j) & 1u;
2180 const bool greater = (info.factors[j].trueIsGreater == bit);
2181 if (greater) lo = std::max(lo, info.factors[j].konst);
2182 else hi = std::min(hi, info.factors[j].konst);
2184 if (!(hi > lo)) { probs[w] = 0.0;
continue; }
2188 const double fX = dX->pdf(x);
2189 if (std::isnan(fX))
return std::numeric_limits<double>::quiet_NaN();
2191 for (
unsigned j = 0; j < k; ++j) {
2192 if (info.factors[j].isConst)
continue;
2193 const bool bit = (w >> j) & 1u;
2194 const bool greater = (info.factors[j].trueIsGreater == bit);
2195 const double FY = otherDist[j]->cdf(x);
2196 if (std::isnan(FY))
return std::numeric_limits<double>::quiet_NaN();
2197 weight *= greater ? FY : (1.0 - FY);
2201 if (std::isnan(cell))
return false;
2208 std::vector<gate_t> mul_for_outcome(nb_outcomes,
static_cast<gate_t>(-1));
2209 for (std::size_t w = 0; w < nb_outcomes; ++w) {
2210 if (probs[w] <= 0.0)
continue;
2211 mul_for_outcome[w] =
2214 for (
unsigned i = 0; i < k; ++i) {
2215 std::vector<gate_t> plus_wires;
2216 for (std::size_t w = 0; w < nb_outcomes; ++w) {
2217 if ((w & (std::size_t{1} << i)) == 0)
continue;
2218 gate_t mw = mul_for_outcome[w];
2219 if (mw ==
static_cast<gate_t>(-1))
continue;
2220 plus_wires.push_back(mw);
2242 const bool allow_mc = (samples > 0);
2251 std::vector<gate_t> cmps;
2252 for (std::size_t i = 0; i < nb; ++i) {
2253 auto g =
static_cast<gate_t>(i);
2260 std::unordered_map<gate_t, std::unordered_set<gate_t>> footprints;
2261 footprints.reserve(cmps.size());
2263 collect_cmp_rv_footprint(gc, c, footprints[c]);
2271 std::unordered_map<gate_t, unsigned> indeg;
2273 for (std::size_t i = 0; i < nb; ++i)
2282 std::vector<std::size_t> parent(cmps.size());
2283 for (std::size_t i = 0; i < cmps.size(); ++i) parent[i] = i;
2284 auto find = [&](std::size_t x) {
2285 while (parent[x] != x) {
2286 parent[x] = parent[parent[x]];
2291 auto unite = [&](std::size_t a, std::size_t b) {
2292 a = find(a); b = find(b);
2293 if (a != b) parent[a] = b;
2295 for (std::size_t i = 0; i < cmps.size(); ++i) {
2296 for (std::size_t j = i + 1; j < cmps.size(); ++j) {
2297 if (find(i) == find(j))
continue;
2298 const auto &fp_i = footprints[cmps[i]];
2299 const auto &fp_j = footprints[cmps[j]];
2300 const auto &small = fp_i.size() < fp_j.size() ? fp_i : fp_j;
2301 const auto &big = fp_i.size() < fp_j.size() ? fp_j : fp_i;
2302 for (
gate_t rv : small) {
2303 if (big.count(rv)) { unite(i, j);
break; }
2309 std::unordered_map<std::size_t, std::vector<gate_t>> groups;
2310 for (std::size_t i = 0; i < cmps.size(); ++i)
2311 groups[find(i)].push_back(cmps[i]);
2313 unsigned resolved = 0;
2314 for (
auto &[root, group] : groups) {
2319 bool all_pristine =
true;
2323 if (!all_pristine)
continue;
2342 std::unordered_set<gate_t> island;
2343 std::unordered_map<gate_t, unsigned> island_ref;
2345 std::stack<gate_t> stk;
2346 for (
gate_t c : group) stk.push(c);
2347 while (!stk.empty()) {
2348 gate_t g = stk.top(); stk.pop();
2349 if (!island.insert(g).second)
continue;
2350 for (
gate_t w : gc.
getWires(g)) { ++island_ref[w]; stk.push(w); }
2356 auto sub_dag_escapes_island = [&](
gate_t s) {
2357 std::unordered_set<gate_t> seen;
2358 std::stack<gate_t> st; st.push(s);
2359 while (!st.empty()) {
2360 gate_t g = st.top(); st.pop();
2361 if (!seen.insert(g).second)
continue;
2362 unsigned inside = island_ref.count(g) ? island_ref[g] : 0;
2363 unsigned total = indeg.count(g) ? indeg[g] : 0;
2364 if (total > inside)
return true;
2369 std::unordered_set<gate_t> sels;
2370 for (
gate_t c : group) collect_cmp_mixture_selectors(gc, c, sels);
2371 bool group_couples_selector =
false;
2373 if (sub_dag_escapes_island(s)) { group_couples_selector =
true;
break; }
2374 if (group_couples_selector)
continue;
2377 if (group.size() == 1) {
2384 if (is_analytic_singleton_cmp(gc, group[0]))
continue;
2388 if (!allow_mc)
continue;
2405 if (
auto info = detect_shared_scalar(gc, group)) {
2406 if (inline_fast_path(gc, group, *info, samples, allow_mc)) {
2407 resolved +=
static_cast<unsigned>(group.size());
2413 "the joint probability of correlated comparison events over a "
2414 "composite quantity needs Monte Carlo, but provsql.rv_mc_samples "
2415 "= 0 disables it; set provsql.rv_mc_samples > 0 (comparisons "
2416 "against constants on a single distribution stay analytical)");
2425 if (
auto pinfo = detect_shared_pivot_rv(gc, group)) {
2426 if (inline_analytic_pivot_joint_table(gc, group, *pinfo)) {
2427 resolved +=
static_cast<unsigned>(group.size());
2440 "the joint probability of correlated comparison events needs "
2441 "Monte Carlo, but provsql.rv_mc_samples = 0 disables it; set "
2442 "provsql.rv_mc_samples > 0 (comparisons against constants on a "
2443 "single distribution stay analytical)");
2445 if (group.size() > JOINT_TABLE_K_MAX)
continue;
2447 inline_joint_table(gc, group, samples);
2448 resolved +=
static_cast<unsigned>(group.size());
ComparisonOperator cmpOpFromOid(Oid op_oid, bool &ok)
Map a PostgreSQL comparison-operator OID to a ComparisonOperator.
Typed aggregation value, operator, and aggregator abstractions.
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
@ LE
Less than or equal (<=).
@ GE
Greater than or equal (>=).
Closed-form CDF resolution for trivial gate_cmp shapes.
gate_t
Strongly-typed gate identifier.
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Analytical expectation / variance / moment evaluator over RV circuits.
Peephole simplifier for continuous gate_arith sub-circuits.
Monte Carlo sampling over a GenericCircuit, RV-aware.
Shared 1-D quadrature core for the pivot-conjunction and order-statistic closed forms.
Continuous random-variable helpers (distribution parsing, moments).
Exception type thrown by circuit operations on invalid input.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
void resolveToPlus(gate_t g, std::vector< gate_t > w)
Rewrite an arbitrary gate as a gate_plus over w.
void resolveToCategoricalMixture(gate_t g, std::vector< gate_t > wires_)
Rewrite g in place as a categorical-form gate_mixture over wires ([key, mul_1, ......
void setWires(gate_t g, std::vector< gate_t > w)
Replace the wires of g with w.
gate_t addAnonymousMulinputGateWithValue(gate_t key, double p, unsigned value_index, const std::string &value_text)
Allocate a fresh gate_mulinput labelled with a numeric outcome value carried in extra.
void resolveToRv(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_rv carrying the distribution-spec extra s.
void resolveToMixture(gate_t g, gate_t p_token, gate_t x_token, gate_t y_token)
Rewrite g in place as a gate_mixture over the wires [p_token, x_token, y_token].
gate_t addAnonymousArithGate(provsql_arith_op op, std::vector< gate_t > wires_)
Allocate a fresh gate_arith gate with operator tag op and the given wires.
gate_t addAnonymousValueGate(const std::string &text)
Allocate a fresh gate_value gate carrying the textual scalar text.
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
double getProb(gate_t g) const
Return the probability for gate g.
void resolveCmpToBernoulli(gate_t g, double p)
Replace a gate_cmp by a constant Boolean leaf (gate_one for p == 1, gate_zero for p == 0) or by a Ber...
void redirectGates(std::unordered_map< gate_t, gate_t > subst)
Make every reference to a gate of subst point to its target instead.
gate_t addAnonymousInputGate(double p)
Allocate a fresh gate_input gate carrying probability p, with a unique synthetic UUID so subsequent B...
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
gate_t addAnonymousMulinputGate(gate_t key, double p, unsigned value_index)
Allocate a fresh gate_mulinput gate with key key, probability p, and value index value_index.
void resolveToValue(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_value carrying the textual extra s.
unsigned foldDegenerateMixtures(GenericCircuit &gc, bool read_probabilities)
Collapse degenerate Bernoulli gate_mixture gates whose selector is certainly true (pi = 1) or certain...
std::vector< std::optional< double > > monteCarloScalarSamples(const GenericCircuit &gc, gate_t root, unsigned samples)
Sample a scalar sub-circuit samples times and return the draws.
unsigned runConstantFold(GenericCircuit &gc)
Constant-fold pass over every gate_arith in gc.
std::unique_ptr< Distribution > closeTransform(const char *transform, const Distribution &x)
The image distribution of transform applied to x, when a registered rule covers x's family; nullptr o...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::vector< double > monteCarloJointDistribution(const GenericCircuit &gc, const std::vector< gate_t > &cmps, unsigned samples)
Estimate the joint distribution of cmps via Monte Carlo.
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
std::unique_ptr< Distribution > closePlusTerms(const std::vector< ClosureTerm > &terms)
Fold PLUS(terms) into a single distribution when a registered closure covers every family in the sum.
double simpsonIntegrate(double lo, double hi, int N, F &&f)
Composite-Simpson with N panels.
unsigned runHybridSimplifier(GenericCircuit &gc)
Run the peephole simplifier over gc.
std::unique_ptr< Distribution > closeProductFactors(const std::vector< const Distribution * > &factors)
Fold a product of independent factors into a single distribution when a registered closure covers eve...
std::optional< DistributionSpec > parse_distribution_spec(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution.
double monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples)
Run Monte Carlo on a circuit that may contain gate_rv leaves.
constexpr int kSimpsonPanels
Panel count shared by every composite-Simpson quadrature over a distribution's integration range: exa...
double cdfAt(const DistributionSpec &d, double c)
Closed-form CDF for a basic continuous distribution.
std::string double_to_text(double v)
Format a double back into the canonical text form used by gate_value extras and gate_rv distribution ...
unsigned runHybridDecomposer(GenericCircuit &gc, unsigned samples)
Marginalise unresolved continuous-island gate_cmp gates into Bernoulli gate_input leaves.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_PERCENTILE
continuous percentile (order-statistic aggregate): wires are interleaved [ind_1, x_1,...
@ PROVSQL_ARITH_DIV
binary, child0 / child1
@ PROVSQL_ARITH_ASFLOAT8
unary, child0 as double precision
@ PROVSQL_ARITH_LN
unary, natural logarithm of child0 (a negative draw raises at evaluation)
@ PROVSQL_ARITH_ROUND
child0 rounded half away from zero, to child1 decimal digits where a second child is given (SQL round...
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ PROVSQL_ARITH_POW
binary, child0 ^ child1 (real branch only: a negative base drawn with a non-integer exponent raises a...
@ PROVSQL_ARITH_ABS
unary, |child0|
@ PROVSQL_ARITH_FLOOR
unary, greatest integer <= child0
@ PROVSQL_ARITH_NEG
unary, -child0
@ PROVSQL_ARITH_INTDIV
binary, child0 / child1 truncated toward zero: SQL's division of two integers
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ PROVSQL_ARITH_CEIL
unary, least integer >= child0
@ PROVSQL_ARITH_EXP
unary, e^child0
@ PROVSQL_ARITH_TIMES
n-ary, product of children
@ PROVSQL_ARITH_MIN
n-ary, min of children (order statistic; least / min aggregate)
@ PROVSQL_ARITH_MAX
n-ary, max of children (order statistic; greatest / max aggregate)
@ PROVSQL_ARITH_ASFLOAT4
unary, child0 as real reads it
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...