asc-community / asc-community/AngouriMath

A rational coefficient beside a variable never reaches a fixed point at the safe ceiling

Open
#1,200 3 comments 0 reactions 0 assignees View on GitHub
Minor bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.