A square root of a quadratic: Euler's substitutions work, cost one wrong answer and 3x the time

[Rafael-SOWNet]

A square root of a quadratic is the largest remaining gap in the integrator, and Euler's substitutions rationalise it. I implemented them, measured them, and did not ship them, because the measurement says they are not ready. Writing down what they cost so the next attempt starts from evidence rather than from scratch.

The size of the prize

Classifying all 937 integrands the Rubi run leaves unanswered, by shape:

class	count	share
radical / fractional power	361	38.5%
trigonometric	185	19.7%
rational / algebraic	112	12.0%
inverse trig / hyperbolic	96	10.2%
exponential	70	7.5%

Radicals are the largest class by a wide margin. Within them, sqrt(linear) is 67 and is now answered by #1243. 216 involve a quadratic under a root — 108 with a positive leading coefficient, 50 negative, 58 where the sign is not obvious from the text.

What I implemented

Euler's substitutions, chosen over the textbook trigonometric one because they land on a rational integrand in one step rather than on a rational function of sine and cosine that then needs the half-angle substitution as well:

• a > 0 — t = sqrt(Q) - x sqrt(a), giving x = (t^2 - c)/(b - 2 t sqrt(a)) and sqrt(Q) = t + x sqrt(a).
• a < 0 — the radicand is non-negative only between two real roots, so Q = a(x - α)(x - β) and sqrt(Q) = t(x - α) gives x = (aβ - t^2 α)/(a - t^2), with the roots from the quadratic formula rather than a solver.

It works. 1/(1+x^2)^(3/2), 1/(1-x^2)^(3/2) and sqrt(x+x^2)/x all came out and all differentiate back.

What it cost, which is why it is not merged

	before	with Euler
solved	863	899
wrong	0	1
timeouts	12	43
wall clock, whole corpus	~650 s	~1,900 s

Thirty-six more answers, and:

One wrong answer, and it is the bad kind. x^4/(-x^2+sqrt(10))^(9/2) comes back as NaN + C. NaN is a claim that the antiderivative does not exist; it does exist, and Rubi prints it. Declining would be true, so this is a wrong answer where a refusal was available. I added a guard rejecting an answer containing NaN and it did not catch this one — the NaN appears after the rule returns, in the inner simplification Integrate applies to the antiderivative, so a guard inside the rule is in the wrong place.

Thirty-one problems that used to be answered now time out, and the whole corpus takes about three times as long. A size bound on the rewritten integrand (400 nodes) did not move either number, so the cost is not a few huge cases — it is spread across everything the rule fires on.

What the next attempt should do differently

1. Guard where the NaN appears, not where it is produced. Either check the fully simplified antiderivative, or — better — have the rule verify its own answer by differentiating back before returning it. The rule rewrites into a form whose correctness is easy to check and hard to reason about, which is exactly when a self-check earns its cost.
2. Find where the time goes before widening the rule. Three times the corpus is not a price worth paying for 36 problems, and the size bound says it is not the obvious cause. My guess, untested, is the Simplify on the rewritten integrand.
3. Consider the trigonometric substitution for the shapes that have a tidy form, and keep Euler for the rest. The answers Euler gives are correct and algebraic — 4/(2(sqrt(1+x^2) - x)^2 + 2) where a textbook writes x/sqrt(1+x^2) — which is a fair trade for coverage but not for the shapes IntegralPatterns already answers.

The branch is not pushed; the code is reproducible from the description above, and I would rather rewrite it against a measurement than resurrect it.

[Rafael-SOWNet]

Accepted — Rafael gave the go-ahead to accept it if it is a good proposal, so the label records his decision rather than mine.

Taking it up now, and one of the two blockers has probably gone stale in the meantime, which is the reason to re-measure rather than trust what is written above.

The cost. The objection was three times the corpus wall clock. Euler's substitution rewrites into a rational integrand, which is a long sum — and #1250 has since fixed an exponential-time defect on exactly that path: splitting a sum ran behind four searches that each worked the whole sum first, so 1 + 2x + ... + 25x^24 took 20 s where its terms take under a millisecond between them. A rule whose output is big sums is the shape most likely to have been paying that. Whether it accounts for all, some or none of the 3x is a measurement, and it is the first thing I will do.

The wrong answer. Item 1 above is right and is not conditional on anything: the rule verifies its own answer by differentiating back before returning it. The NaN appeared after the rule returned, in Integrate's own simplification, so a guard inside the rule was in the wrong place — a self-check on the value is in the right one, and it also catches whatever else a rewrite of this kind gets wrong.

I will report the measurement either way, including if it says the cost is still there and the rule should stay unmerged.

[Rafael-SOWNet]

Implemented, measured, still not shipped — but the open question above is now answered, and the branch is pushed this time: euler-substitution.

The three times wall clock is not the simplifier

That was my guess above, and it is wrong. Euler's substitution rewrites into a rational function whose coefficients carry the radical. x^4*sqrt(5 - x^2) becomes a 69-node integrand in sqrt(5):

2*sqrt(5)*(2*sqrt(5) - sqrt(5)*(t^2 + 1))^4*t*(...)/(...)

The rational rules read a polynomial over the rationals — TryGetRationalCoefficients is the gate — so they cannot factor that, and they spend the entire budget finding out. Master declines that integrand in 3.1 s; the unguarded substitution had not returned after 200 s.

That is the same wall I hit today probing a general quartic split: a single quadratic with cos(pi/5) coefficients integrates, a product of two does not, because the coprime split works over Q.

A rational-coefficient guard removes the hangs

Requiring sqrt(a) rational for the first substitution and a rational discriminant for the second. The same integrand is then declined in 1.0 s — faster than master's 3.1 s, since the rule now refuses before the expensive part rather than after it.

Self-verification works, and settles item 1

The rule differentiates its answer back and compares with the integrand at sample points before returning it. x^4/(-x^2 + sqrt(10))^(9/2) — the integrand that produced NaN + C last time — is now declined in 9 ms. No wrong answers anywhere in the measurement, including the shapes that produced one before.

Worth keeping whatever happens to the rest: it is cheap, it is a check on the value rather than the shape, so it catches a NaN that appears after the rule returns, and this is a rewrite whose correctness is easy to test and hard to reason about.

What it does not fix, and why there is no PR

	solved	wrong	timeouts
master 7c0963a9	227	0	3
with Euler	229	0	10

463-problem sample, both arms in the foreground on one machine.

Two genuinely new answers — 1/(1 + x^2)^(3/2) and (1 + x + x^2)^(3/2). And seven problems that used to be declined quickly now spend the whole budget before being declined: atan(x)/(x^2*sqrt(1 - x^2)), x*ln(x)/sqrt(-1 + x^2), 1/((4 + x^2)*sqrt(1 + 4*x^2)), (1 + x^4)/((1 + x + x^2)*sqrt(2 + x + x^2)) among them.

No answer is lost. But two answers for seven slow refusals is a worse trade than the one dropped from #1245, and it fails for the same reason: a rule that hands a speculative sub-problem to the whole chain has no way to bound what it spends. That is WorkBudget from #896, and it is now the third place this session has arrived at the same conclusion — the other two are #1255 and #1245.

So the state of this issue

The wrong answer is solved and the cost is diagnosed rather than guessed at. What remains is not a problem with Euler's substitution: it is that the integrator cannot bound speculative work, and that a rational function over an algebraic extension is not something the rational rules read. Either would make this shippable; neither belongs in this rule.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

The scoping mechanism this was waiting on is merged (#1266), so I put Euler's substitution back on top of it and measured. It does not rescue this one, and the number that says so is worth recording before anyone tries it again.

Integration.AnsweringTheQuestionAsked fires a rule only when the integrand in front of it is the one the caller asked about. Three arms, same build, the rule switched by an environment variable so nothing else differs:

Rubi corpus, 463-problem sample, five-second budget:

	solved	wrong	timeouts
without Euler	231/463	0	3
Euler, ungated	233/463	0	10
Euler, scoped to the top	233/463	0	8

The gate buys back two of the seven timeouts and costs no answers. That is real and it is not enough. Uncapped, with the gate on:

51,211 ms   declined   1/((4 + x^2)*sqrt(1 + 4x^2))
  > 500 s   —          x*ln(x)/sqrt(-1 + x^2)

and with the rule switched off entirely, in the same build:

200 ms      declined   1/((4 + x^2)*sqrt(1 + 4x^2))
 25 ms      declined   x*ln(x)/sqrt(-1 + x^2)

Both are ordinary integrands that a user would expect an answer or a quick "no" on, and both hold a square root of a quadratic, so they are inside the rule's intended domain rather than at its edge.

Why the gate works for the secant reduction and not for this. The reduction is closed: it runs its recurrence to completion in a loop and hands back a finished answer, so scoping it to the top costs only the sub-integrals it would have volunteered into other searches. Euler rewrites — it produces a rational integrand and hands it back to the chain, which then does arbitrary work at depths the gate does not reach. The expensive firing really is at the top. Scope is the wrong instrument for a rewriting rule, and the four rows in #1265's table split cleanly along that line.

So #1265's first proposal — a work budget, #896's WorkBudget being the instrument that exists — is the one this rule needs, and there is now evidence that it is not interchangeable with the second.

One more thing the run showed, which the original branch did not: scoped to the top, Euler answers only one of the four integrands this issue named — (1 + x + x^2)^(3/2). 1/(x*sqrt(3 + x^2)), x/sqrt(5 + 2x + x^2) and sqrt(3 - x^2)/x are declined, because by the time the chain reaches Euler on those the integrand has already been rewritten once and the descent is past depth one. The corpus total is the same either way, so the two answers it gains there are elsewhere.

Branch euler-substitution still has the rule as originally written.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

Third instrument tried, and Euler's substitution should be abandoned rather than parked. Recording the measurements so this is the last time anyone builds it.

The cheap structural pre-check I proposed on #1265 works, and it is worth having on its own terms: Euler rationalises a radical, so it can only help an integrand that was algebraic to begin with. Refusing anything with a logarithm, an exponential or a trigonometric function in it — before the rewrite and the Simplify the rule used to do before finding out — turns

x*ln(x)/sqrt(x^2 - 1)     over 399 s   ->   169 ms, and answered

That is the whole of the cost the budget could not reach, gone, for a check that costs a tree walk.

It is still not enough, because what is left is not worth what it costs:

	master	Euler, pre-checked, no budget
1/((4 + x^2)*sqrt(1 + 4x^2))	200 ms, declined	59.5 s, declined
(1 + x^4)/((1 + x + x^2)*sqrt(2 + x + x^2))	223 ms, declined	did not return in 400 s

and of the four integrands this issue was opened about, the pre-checked rule answers one — (1 + x + x^2)^(3/2). 1/(x*sqrt(3 + x^2)), x/sqrt(5 + 2x + x^2) and sqrt(3 - x^2)/x are rewritten by rules in front of it and never reach it at depth one, where its scope confines it.

And the budget makes it worse, not better, for a reason worth writing down. SpendAtMost caps everything inside the scope, and it cannot tell work Euler's speculation caused from work that would have happened anyway. With a ceiling of 4, x*ln(x)/sqrt(x^2 - 1) went from 169 ms back up to 8.6 s — Euler firing on some sub-integrand capped the search that was about to answer the outer one. A ceiling on a sub-problem is not a ceiling on a rule.

So all three instruments are measured now:

scope	51 s and >500 s remained
a cheap structural decline	fixes the transcendental cases entirely; the algebraic ones still cost 59 s
a step budget on the hand-off	caps the wrong thing, and costs answers

Its worth has also been eroded from under it while this was being measured: #1268, #1270 and #1272 landed tonight, and between them they answer things Euler used to be the only route to. The same happened to the half-angle reach, which is now outright negative.

My recommendation is to close this as not worth doing in this form. A square root of a quadratic is worth answering — it is still the largest single class in the Rubi suites — but by a substitution that lands somewhere a rule can read rather than on a rational function nobody can integrate cheaply. The trigonometric substitution lands on sin^p cos^q, which #1268 answers in closed form without asking the integrator anything, and that is the route I am trying next.

The branch euler-substitution and the pre-check are of historical interest only.

🤖 Generated with Claude Code

https://claude.ai/code/session_012sonx8iAspMiwRwokT1Ura

[Rafael-SOWNet]

Re-measured, and this no longer holds. Euler's substitution came in by another route: #1289 closed it to a rational function of x and one square root of a quadratic, finished by the rational integrator, and #1315 extended it. On master 1293b56 every integrand this thread measured is answered, and each answer differentiates back at six points:

	then	now
(1 + x + x^2)^(3/2)		324 ms
1/(x*sqrt(3 + x^2))		58 ms
x/sqrt(5 + 2x + x^2)		26 ms
sqrt(3 - x^2)/x		29 ms
1/((4 + x^2)*sqrt(1 + 4x^2))	51 s to decline	40 ms
(1 + x^4)/((1 + x + x^2)*sqrt(2 + x + x^2))	past 400 s	473 ms
x*ln(x)/sqrt(-1 + x^2)	past 500 s	83 ms

The same seven are answered on today's master with #1602 on top.