Mathematician Finds Easier Way to Solve Quadratic Equations

[Namir]

(05-05-2024 06:31 AM)carey Wrote:  

(05-05-2024 02:24 AM)Namir Wrote:  Wat's next? Solving systems of linear equations using Cramer's rule???

Namir

And what’s wrong with using Cramer’s rule for linear systems?

In the late 80s I attended a programmers' conference in Boston. A speaker mentioned that he encountered a math application that was running WAY TOO SLOW! When he checked the source code, he found that the code author was using Cranmer's method to solve linear equations. You should have heard the attendees reaction .. a resounding ouuuuuuuh!!!

Just sharing!

[Namir]

(05-05-2024 11:07 AM)Thomas Klemm Wrote:  

(05-05-2024 02:24 AM)Namir Wrote:  Wat's next? Solving systems of linear equations using Cramer's rule???

How about using the HP-67 to evaluate the determinant of a square matrix by repeated applications of the process of pivotal condensation?

I don't see Cranmer's rule mentioned much in Numerical Analysis books when they discuss the topic of solving linear equations.`I guess these authors maintain a reasonable bar for algorithms used to solve linear equations.

Namir

[vaklaff]

(05-05-2024 02:24 AM)Namir Wrote:  Let's keep in mind the KISS principle (keep it simple stupid), or what Einstein said, "Make it simple, but no simpler". Using fancy functions like cosh, exp, sin, and so on is fancy, but introduces a bit of complicatrion in my very humble opinion.

I strongly believe KISS doesn’t apply when you are just having fun…

[carey]

(05-05-2024 01:18 PM)Namir Wrote:  

(05-05-2024 06:31 AM)carey Wrote:  And what’s wrong with using Cramer’s rule for linear systems?

In the late 80s I attended a programmers' conference in Boston. A speaker mentioned that he encountered a math application that was running WAY TOO SLOW! When he checked the source code, he found that the code author was using Cranmer's method to solve linear equations. You should have heard the attendees reaction .. a resounding ouuuuuuuh!!!

Just sharing!

Yes, Cramer's rule is awful as a numerical method, but, using symbolic determinants, as the IEEE article linked in my previous tongue-in-cheek reply shows, offers unique advantages for obtaining symbolic results, e.g., transfer functions at any point in a linear system. The classic books Network Analysis and Feedback Amplifier Design by Hendrik Bode and Control-System Dynamics by Walter Evans (originator of the root-locus method), make good use of Cramer's rule to derive symbolic results.

[Gerson W. Barbosa]

(05-05-2024 02:24 AM)Namir Wrote:  Let's keep in mind the KISS principle (keep it simple stupid), or what Einstein said, "Make it simple, but no simpler". Using fancy functions like cosh, exp, sin, and so on is fancy, but introduces a bit of complicatrion in my very humble opinion.

I fear you have completely missed the point. We could, for instance, apply the identity \(\arcsin{z}=\arccos{\sqrt{1-z^2}}\) to

\[x_{1}=\left({\cos\left({\arcsin{\frac{\sqrt{q}}{-\frac{p}{2}}}}\right)+1}\right)\times-\frac{p}{2}\]
and easily take the trigonometric functions out of the formula. But then we would get back to the original pq formula, which as we know cannot handle, on a 12-digit calculator, the first example in Palmer’s article, a=1E-13, b=-2 and c=1, whose roots at that precision are 2E13 and 0.5, not 2E13 and zero. Of course that is not a concern on Free42 if we are interested solely in 12-digit answers.

Sure these have some shortcomings, like b or c having to be different from zero, depending on the formula we choose, or real results being shown with null imaginary parts in certain cases, for example when a=1, b=-1 and c=-2.

The use of transcendental functions are just trade-offs for a little more accuracy while keeping compactness. In a failed attempt (complex number is an invalid type for the LN1+X function), in order to keep the stack register T intact I would use – horror of horrors! – four transcendental functions in a row.

Regards,

Gerson.


———————-

Code:


00 { 26-Byte Prgm }
01▸LBL "Z"
02 X<> ST Z
03 STO÷ ST Z
04 STO+ ST X
05 +/-
06 ÷
07 RCL ST Y
08 SQRT
09 RCL÷ ST Y
10 ASIN
11 COS
12 LN1+X
13 E↑X
14 ×
15 STO÷ ST Y
16 END

[carey]

(05-05-2024 12:48 PM)Maximilian Hohmann Wrote:  But apart from that I keep wondering why the quadratic equation and it's memorized solution is attributed such a high significance by schools. I have never since finishing school come across a quadratic equation in real life. Things are mostly simple and can be handled with linear calculations ("if my plane needs 1400 pounds of fuel in one hour, how much must I take along for a 2:25h flight?") or they are really complicated and require higher order polynomials, transcendental funcions or numeric solutions. But a quadratic equation? Never ever.

Regards
Max

Hmm...there are a lot of equations in nature that involve squares (e.g., inverse square laws for electrostatics, gravity, light and sound intensity, quadratic dependence of power on current, quadratic dependence of air drag on velocity, etc.) that, in all but the simplest examples that only require taking a square root, lead to quadratic equations.

Paraphrasing Abraham Maslow, "if all you have is y=mx+b, the whole world looks like a line."

[Albert Chan]

(05-05-2024 12:48 PM)Maximilian Hohmann Wrote:  Things are mostly simple and can be handled with linear calculations
("if my plane needs 1400 pounds of fuel in one hour, how much must I take along for a 2:25h flight?")

Extra weight of fuel will require some fuel to transport.
Effect may be small, but this is not a linear calculation!

[Albert Chan]

(05-05-2024 06:13 PM)Gerson W. Barbosa Wrote:  complex number is an invalid type for the LN1+X function

Free42/Plus42 now has C.LN1+X to handle complex input.
https://github.com/thomasokken/free42/issues/55

To make this work, LN accuracy has improved as well.
https://github.com/thomasokken/free42/issues/62

[Maximilian Hohmann]

Hello,

(05-05-2024 07:37 PM)Albert Chan Wrote:  Effect may be small, but this is not a linear calculation!

Yes, but for daily work this is done using tables (until 20 years ago) or rather software on a computer (since 20 years) or an iPad App (since 10 years).

My question really remains: Who has ever, in professional or private life, used his memorised "midnight formula" (no idea if it is called that in English, in German we call it "Mitternachtsformel" because you can wake up any schoolchild at midnight and she or he will be able to recite that equation) for a real calculation? And if not, why on earth did they waste our time with this nonsense at school instead of teaching us something useful?

Regards
Max

[Gerson W. Barbosa]

Perhaps I should invoke the KISS rule to myself. The accuracy of the second root can be improved simply by calculating it as x₂ = q/x₁, x₁≠ 0, assuming of course that the first root is accurate enough. If the first root is zero the program stops and a “Divide by 0” message is shown, but then again in this case a quadratic solver is not needed.

The program has been relabeled as “Y” (why hadn’t I done it this way yet?). Only 22 bytes and 13 steps, including LBL and END.

Code:


00 { 22-Byte Prgm }
01▸LBL "Y"
02 X<> ST Z
03 STO÷ ST Z
04 STO+ ST X
05 ÷
06 ENTER
07 X↑2
08 RCL- ST Z
09 SQRT
10 X<>Y
11 -
12 STO÷ ST Y
13 END

Example:

\(10^{-13}x^2-2x+1=0\)

E +/- 13 ENTER 2 +/- ENTER 1 XEQ Q ->

HP-42S:

T: previous X
Z: previous X
Y: 0.5
X: 2.E13

Free42:

T: previous X
Z: previous X
Y: 0.500000000000012500000000000625
X: 19,999,999,999,999.4999999999999875

[Albert Chan]

(05-06-2024 12:23 AM)Gerson W. Barbosa Wrote:  The accuracy of the second root can be improved simply by calculating it as x₂ = q/x₁

x1 = -p/2 + √Δ
x2 = q/x1

Not an improvement.
Depends on sign(Re(p)), we have 50:50 chance is getting both good roots, or both bad!

[Gerson W. Barbosa]

(05-06-2024 02:32 AM)Albert Chan Wrote:  

(05-06-2024 12:23 AM)Gerson W. Barbosa Wrote:  The accuracy of the second root can be improved simply by calculating it as x₂ = q/x₁

x1 = -p/2 + √Δ
x2 = q/x1

Not an improvement.
Depends on sign(Re(p)), we have 50:50 chance is getting both good roots, or both bad!

I was aware of that. That’s why I added “assuming of course that the first root is accurate enough”. No problem with the few examples I tried, though. Perhaps I need a more comprehensive list of examples to check. Considering the possibilities you mention, I think it’s better to compute the second root as x₂ = -(b + x₁). At least divisions by zero are completely avoided.

[carey]

Max, respectfully, your earlier point seemed to be that the quadratic equation is relatively unimportant because, in your opinion, linearity reigns supreme.

(05-05-2024 12:48 PM)Maximilian Hohmann Wrote:  I have never since finishing school come across a quadratic equation in real life. Things are mostly simple and can be handled with linear calculations ("if my plane needs 1400 pounds of fuel in one hour, how much must I take along for a 2:25h flight?") or they are really complicated and require higher order polynomials, transcendental funcions or numeric solutions. But a quadratic equation? Never ever.

Now your point seems to have shifted to the quadratic formula for solving quadratic equations is implemented in software, so why learn it.

(05-05-2024 09:18 PM)Maximilian Hohmann Wrote:  Yes, but for daily work this is done using tables (until 20 years ago) or rather software on a computer (since 20 years) or an iPad App (since 10 years).

My question really remains: Who has ever, in professional or private life, used his memorised "midnight formula"...?

The former is the view that quadratic equations are unimportant, while the latter is the view that the quadratic formula for solving quadratic equations is unimportant.

Respectfully, I find both views mistaken.

1) The number of uses for quadratic equations is so numerous, and in so many fields, that listing them is like listing uses of the Pythagorean theorem. (see EdS2's current thread for a few examples).

2) Besides the obvious that it's good to understand equations even if we use software to implement them, the quadratic formula in symbolic form is essential for determining equilibria and bifurcations in nonlinear ODE's (for which software is limited to numerical solutions since most nonlinear ODEs have no closed-form solutions).

For example, to find equilibria solutions and bifurcations in the nonlinear ODE \[ \frac{dy}{dt} = y^2 +2y + a \] set it equal to 0, resulting in a non-factorable quadratic equation \[y^2 + 2y + a = 0\].
Solving for y in terms of parameter a using the quadratic formula
\[-b \pm \frac{\sqrt {(b^2 - 4ac)}}{2a} \]
\[-2 \pm \frac{\sqrt {(4 - 4a)}}{2} \]
\[-1 \pm \sqrt {(1 - a)} \]
we obtain an expression (1 - a under the radical) that gives the number of equilibrium solutions and shows the importance of the quadratic formula used as a symbolic equation.

Case 1: If 1-a =0, then a = 1 and there is a single equilibrium solution: y=−1.

Case 2: If 1-a>0, then a <1 and there are two equilibrium solutions: $$-1 \pm \sqrt {(1 - a)} $$

Case 3: If 1-a <0, then a>1 and there are no equilibrium solutions since y is complex.

At a = 1, the number of equilibrium solutions changes from 2 to 1 to 0, as the value of parameter a goes from a<1 to 1 to a>1. Therefore a = 1 is a bifurcation point (and is the only bifurcation point since the number of equilibrium solutions doesn't change at any other value of a). For more details about this example, see Section 2.4 Bifurcation in LibreText MTH 225 Differential Equations.

Summarizing, using the quadratic formula in symbolic form gave the equilibria and bifurcation points to a nonlinear ODE -- not bad for a useless formula! :)

Nonlinear ODEs are everyday staples for engineers working with MEMS and NEMS sensors and nonlinear control, for brain neuroscientists, applied mathematicians, and on and on. While all of us can make it through dinner without using the quadratic formula, many would be unable to get through a day without it! :)

[Albert Chan]

(05-04-2024 02:24 PM)Albert Chan Wrote:  For acosh √(z²-1) form, we need to match sign, to ensure non-negative real part.
Again, assume sign(x) = ±1, never 0

\(e^{\cosh^{-1}{(z)}}=z + sign(\Re(z)) \;\sqrt{z^2-1}\)

Trivia, RHS ensured *both* complex parts without cancellation issue.

Kahan's csqrt(z = x+y*i) formula: √(z) = √((|z|+x)/2) + sign(y) * √((|z|-x)/2) * i

Let sign(z) = [sign(x), sign(y)]

(z²-1) = (x²-y²-1) + (2*x*y) * i
sign(x) * sign(√(z²-1)) = sign(x) * [1, sign(x*y)] = sign(z)

(05-06-2024 02:32 AM)Albert Chan Wrote:  x1 = -p/2 + √Δ
x2 = q/x1

Not an improvement.
Depends on sign(Re(p)), we have 50:50 chance is getting both good roots, or both bad!

Sorry, test with sign(Re(p)) may not get the big root.

Example, x² - 2m + m = 0, where m = 0.1 + 100*I, s = sign(Re(m)) = 1

m + s * √(m²-m) ≈ (0.1+100*I) + (0.399995-100.001*I) = (0.499995-0.001*I)

This get the wrong smaller root, massive cancellation of imag part. KISS is not simple.

Hyp/Trig versions are better.

z = GM/AM = √(q)/(-p/2) = √(m)/m

x1 = √(q) * e^acosh(1/z) ≈ √(0.1+100*I) * (14.1139+14.1705*I) ≈ (-0.299995+200.001*I)
x1 = m + m*cos(asin(z)) ≈ (0.1+100*I) + (-0.399995+100.001*I) ≈ (-0.299995+200.001*I)

x2 = q/x1 ≈ (0.499995-0.00124997*I)

Or, go straight for small root, without massive cancellation:

x2 = √(q) / e^acosh(1/z)  ≈ (0.499995-0.00124997*I)
x2 = -p * sin(asin(z)/2)^2 ≈ (0.499995-0.00124997*I)

[Gerson W. Barbosa]

(05-06-2024 02:27 PM)Albert Chan Wrote:  Example, x² - 2m + m = 0, where m = 0.1 + 100*I, s = sign(Re(m)) = 1

m + s * √(m²-m) ≈ (0.1+100*I) + (0.399995-100.001*I) = (0.499995-0.001*I)

This get the wrong smaller root, massive cancellation of imag part. KISS is not simple.

Not that bad for this particular example. I still get -0.001249972i on the 42S, all the rest being exactly the same. If I insert a +/- instruction after SQRT, then I get the full -0.00124997218867. This choice of the most favorable first root might be done programmatically, but that would cost some extra bytes and steps.

(05-06-2024 02:27 PM)Albert Chan Wrote:  Hyp/Trig versions are better.

Yes, depending on what is our goal. Perhaps that lightbulb is worth changing, no matter how many of us it takes. The other option is living forever in the dark.

[Albert Chan]

KISS quad solver

Code:

function quad(a,b,c)
    b = -.5*b
    local y = I.sqrt(b*b-a*c)
    y = I.abs(b+y) < I.abs(b-y) and b-y or b+y
    return y/a, c/y
end

lua> quad(1e-13,-2,1)
(19999999999999.496+0*I)      (0.5000000000000125+0*I)

[Gerson W. Barbosa]

(05-07-2024 03:05 PM)Albert Chan Wrote:  KISS quad solver

Code:

function quad(a,b,c)
    b = -.5*b
    local y = I.sqrt(b*b-a*c)
    y = I.abs(b+y) < I.abs(b-y) and b-y or b+y
    return y/a, c/y
end

lua> quad(1e-13,-2,1)
(19999999999999.496+0*I)      (0.5000000000000125+0*I)

I assume by KISS you mean “Keep It Simple & Short”. Anyway, for me the acronym would sound offensive only if there were a comma before the second S (“Keep it simple stupid” is quite a different thing than “keep it simple, stupid!”– at least for those of us who use to place a comma before nouns in vocative case).

BTW, do you have an RPL version of that code? Regarding “Lua”, I know the meaning of the name only. Also, the relational < operator doesn’t work for complex numbers on the HP-42S.

Meanwhile I have received two modified versions of my latest “Y” program from an anonymous contributor. The shorter one is suitable for the real HP-42S while the other is meant for Free42.

HP-42S:

Code:


00 { 24-Byte Prgm }
01▸LBL "Q"
02 X<> ST Z
03 STO÷ ST Z
04 STO+ ST X
05 ÷
06 +/-
07 ENTER
08 X↑2
09 RCL- ST Z
10 SQRT
11 X=Y?
12 +/-
13 -
14 STO÷ ST Y
15 END

Free42:

Code:


00 { 28-Byte Prgm }
01▸LBL "Q"
02 X<> ST Z
03 STO÷ ST Z
04 STO+ ST X
05 ÷
06 +/-
07 ENTER
08 X↑2
09 RCL- ST Z
10 SQRT
11 SF 25
12 X≤Y?
13 +/-
14 CF 25
15 -
16 STO÷ ST Y
17 END

Best regards,

Gerson.

[Albert Chan]

(05-08-2024 02:23 AM)Gerson W. Barbosa Wrote:  I assume by KISS you mean “Keep It Simple & Short”. Anyway, for me the acronym would sound offensive only if there were a comma before the second S (“Keep it simple stupid” is quite a different thing than “keep it simple, stupid!”– at least for those of us who use to place a comma before nouns in vocative case).

KISS principle have many variations, not necessarily end in Stupid.
Comma or not, Stupid is meant as a tease, not in a negative way!

Quote:relational < operator doesn’t work for complex numbers on the HP-42S.

I was comparing absolute value, going for the big root.
This is *exactly* the same as your cos/asin trig formula.

(05-04-2024 07:37 PM)Gerson W. Barbosa Wrote:  \(x_{1}=\left({\cos\left({\arcsin{\frac{\sqrt{q}}{-\frac{p}{2}}}}\right)+1}\right)\times-\frac{p}{2}\)

Replace cos(asin(z)) = √(1-z²), we have KISS version, only 1 square root!

Code:

00 { 28-Byte Prgm }
01▸LBL "Q"
02 X<> ST Z         ;   a   b   c
03 STO÷ ST Z        
04 STO+ ST X
05 +/-              
06 ÷                ;   m   q
07 ENTER            
08 X↑2              ; m^2   m   q
09 RCL- ST Z        ; m^2-q m   q
10 RCL÷ ST L
11 SQRT
12 RCL× ST Y        
13 +                ; x1    q
14 STO÷ ST Y        ; x1    x2
15 END

[ttw]

Re Cramer's Rule. Some years ago, I taught a course on using Cray computers to programmers and engineers at an aircraft company. (As an aside, on the second day, one of the managers complained to my boss that he [the manager, not my boss] could not understand his workers' questions or my answers. My boss pointed out that they had requested "technical" not "managerial" help and told him to check back in two or three days.) The main work taking 99% or more of the time was around the wing front, top, back, bottom, front. It was a weird structure from my point of view; the loop went from 1 to 2N+2, with N steps on the top and bottom 1 step at the beginning, 1 step at the back, and a final step at the front; the (legacy from years before) code had 5 IF-blocks (or equivalent) to separate these. I had them write 5 sections, J=1, J=2 to N, J=N+1, J=N+2 to 2N+1, J=2n+2. The new code wasn't much larger as there were no tests. (Management was skeptical.) Then they told me that square roots took up a lot of time; as they were checking for longer or shorter, not a value, I suggested removing the roots. Now the code was about 50 times faster; the long parts of the loops could be vectorized.

I found code implementing Cramer's Rule on 5x5 matrices so we had a discussion. They liked the idea that Cramer's rule had no tests. I pointed out that Cramer's Rule is very unstable and slow. They pointed out that these were always positive-definite matrices with fairly large diagonals (none of the programmers or engineers was dumb, they were just not numerical analysis.) So I noted that Gaussian Elimination without pivoting works on positive definite matrices. This replaces 6 5x5 determinants taking 720 multiplies with a single Gaussian Elimination taking about 40 multiplies. A factor of about 20; now a speedup of 1000.

More discussion about mathematics showed that the whole system was positive definite.
Now I could suggest the red-black ordering. The two-dimensional surface of the wing was covered with squares; if using a Jacobi-like iteration, each red square depends only on itself and the surrounding black squares, and vice versa. This ordering increases the speed of the overall convergence. It was bout a factor of 50 over their input values.

So after a couple of more days, their management noticed a 50,000 speedup in their main code. They bought another Cray.

[nickapos]

(05-05-2024 12:48 PM)Maximilian Hohmann Wrote:  Hello!

(05-05-2024 02:24 AM)Namir Wrote:  Let's keep in mind the KISS principle (keep it simple stupid), or what Einstein said, "Make it simple, but no simpler".

Yes, it's amazing. A simple statement "Mathematician Finds Easier Way to Solve Quadratic Equations" has turned into "how many HP calculator nerds does it take to change a lightbulb?" ;-)

But apart from that I keep wondering why the quadratic equation and it's memorized solution is attributed such a high significance by schools. I have never since finishing school come across a quadratic equation in real life. Things are mostly simple and can be handled with linear calculations ("if my plane needs 1400 pounds of fuel in one hour, how much must I take along for a 2:25h flight?") or they are really complicated and require higher order polynomials, transcendental funcions or numeric solutions. But a quadratic equation? Never ever.

Regards
Max

It seems to me quadratic is simple enough to explain polynomials at a school level. Also useful to be used for introduction to integrals and differentiation