asc-community / asc-community/AngouriMath

Taking a constant factor out of a denominator made an unanswerable integral four times slower to decline

Open
#1,255 0 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

`1/(b^2*cos(x)^2 + a^2*sin(x)^2)` has no elementary antiderivative this library can find, and it did
not find one before either. What changed is how long it takes to say so: **107 s to over 400 s**,
measured on one machine, both arms.

### Where it comes from

`TakeConstantFactorOutOfDenominator`, added in #1249. It reads a quotient whose denominator mixes a
factor free of the variable with one holding it, takes the constant out, and hands
`numerator / variablePart` back to the integrator:

```csharp
return Integration.ComputeIndefiniteIntegral(numerator / variablePart, x, integrateByParts)
?.Pipe(i => i / constantPart);
```

That is a fresh integral for the whole chain to work through, and on this integrand the search
underneath produces a great many denominators of that shape — every one of them a new problem.

### Attributed by ablation, not by reading

Two hypotheses about which rule was responsible were wrong before this one was right, so the method
is worth recording. Returning `null` at the top of the method under an environment variable, one
rule at a time:

| | |
|---|--:|
| `2dbeedf7`, before #1249 | 136 s |
| master | > 400 s |
| master, `SolveByScalingTheVariable` ablated | > 400 s |
| master, `TakeConstantFactorOutOfDenominator` ablated | **107 s** |

The scaling rule — the other half of #1249, and the one I first suspected because it is the visible
new rule — is not involved.

### Two narrowings that do not help

Both were plausible and both measured no better than unguarded, which is the useful part of the
report:

- **Only fire where the variable part is a rational function of `x`.** The reasoning was that the
rules wanting a polynomial denominator are the rational ones, so a trigonometric denominator gains
nothing from losing its constant factor. Still > 400 s: the expensive firings are on denominators
that *are* rational — after the half-angle rewrite everything under this integrand is rational in
the new variable with `a` and `b` as parameters. The rule is expensive **inside** its intended
domain, not outside it.
- **Only fire where the constant part is symbolic**, since a numeric factor never needed this rule.
Also > 400 s, for the same reason: `a` and `b` are symbolic.

So the cost is not a matter of firing on the wrong shapes. It is that the rule multiplies the number
of distinct sub-problems on integrands that have no answer, and no structural condition separates
"will pay off" from "will not".

### What it is not

Not a wrong answer, and not a hang: the integral is declined either way, and every suite is green.
It is a slower refusal, and the same kind of cost #1245 records for the half-angle rewrite.

It is, however, why a full `intbench` run over Rubi's suites no longer completes on this machine —
the harness sits on this problem long past its budget.

### What would fix it

A cost bound rather than another structural condition. `WorkBudget` from #896 is the instrument:
a rule that hands on a speculative sub-problem should be able to say how much of the remaining
budget it is prepared to spend, and stop. Inventing another predicate here would be a third guess of
the same kind as the two above.

Filed against #718.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

Contributor guide

Open the contributing guide

Research direction

Start by tracing TakeConstantFactorOutOfDenominator and the WorkBudget mechanism from #896, then reproduce the reported integral and intbench timing. The fix is complete when speculative sub-problems respect a bounded remaining budget, the integral still declines without a wrong answer, and the relevant suites remain green.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
performance
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.