asc-community / asc-community/AngouriMath
A rational coefficient beside a variable never reaches a fixed point at the safe ceiling
- Dominant language
- C#
- Stars
- 831
- Forks
- 79
- Avg merge
- 3h 23m
- Merged PRs (30d)
- 309
Description
At the safe ceiling (`RulesUpTo(Rearranges)`), seven of the 3,630 shapes in the growth corpus never
report a fixed point, and they are one family: a rational coefficient beside a variable.
## Measured (build `98a9420c`, after #1198)
`WorkBudget { Steps = 200_000, Time = 30 s }`, one input per graph:
| input | fixed point | e-nodes after 30 s | e-nodes after 2 s | extracted |
|---|---|---|---|---|
| `2 * x * 1/2` | no | 158 | — | `x` |
| `x * 1/2 * 2` | no | 135 | — | `x` |
| `(2 - 0) * x * 1/2` | no | 159 | 182 | `x` |
| `x / x * -x` | no | 583 | 464 | `-x` |
| `x / x * x * 1/2` | no | 249 | 282 | `x / 2` |
| `x / x * x ^ (-2)` | no | 317 | 291 | `x ^ (-2)` |
| `1 / (1/2) * x * 1/2` | no | 159 | 181 | `x` |
| `x ^ 2 / x` | no | 145 | 109 | `x` |
| `2 ^ (-1) / sqrt(1/2)` | no, step ceiling | 1,565 | 1,072 | `sqrt(1/2)` |
So this is a **stall, not a runaway**: the graph barely grows with fifteen times the budget, and
every extraction is right. `ConstantFoldTest.ACoefficientBesideAVariableStallsRatherThanRunsAway`
pins it in both directions — an entry that starts saturating is to be deleted, and one that grows
past a thousand e-nodes has stopped being a stall.
## What it is
The spellings of a coefficient beside a variable — `1/2 * x`, `x / 2`, `x * 2 ^ (-1)`,
`2 ^ (-1) * x` — are exchanged by `Rearranges` rules (`a-reciprocal-rational-factor-is-a-division`,
`a-reciprocal-power-is-a-quotient`, the quotient and product regrouping rules of `Common`), and a
fresh spelling keeps appearing at the edge of what has been rewritten, so a pass never comes back
empty. Before #1198 the same rules ran away on constant-only input (`2 - 0 + 0 * 2`, 54 cases),
because with nothing folding a number the spellings were unbounded; folding rationals on
insertion bounded the family without closing it. `RunawayBreadthTest` had called these rules
"confluent on plain arithmetic" from three inputs; it now says what was measured.
## What would close it, not decided
Either a normal form for a rational coefficient inside the graph — `c * x` with `c` a literal,
folded on insertion the way a rational over rationals now is — or an orientation among the
spelling rules so that only one direction fires under saturation. The first is a mechanism; the
second is what the growth ceiling already does for expanding rules and would need a marker for
"rearranges, but one way". Neither is worth doing until something calls the graph on this shape;
`Transformation.CanonicalizationOverGraph` is offered, not applied.
Found while measuring #746 tier 2 item 4 (PR #1198). Related: the budget overshoot on these
same inputs, filed separately.
Contributor guide
Research direction
Start with ConstantFoldTest.ACoefficientBesideAVariableStallsRatherThanRunsAway and RunawayBreadthTest to reproduce the measured saturation behavior. Read the Rearranges and Common rules named in the issue, then determine whether a rational-coefficient normal form or one-way rule orientation is appropriate; done requires a bounded, terminating result with the regression coverage described.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100