Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2011-05-06 18:19:41

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Quadratic Equation Solver

I have updated the Quadratic Equation Solver

Could you guys give it a bit of a workout and let me know how it goes?


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#2 2011-05-06 20:05:09

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi MathsIsFun;

Worked on all test examples. Worked well.

For a quadratic of this type, known to be numerically unstable

The solver gets ( -0.0000017547864, -712345.12) the actual answer is: (-0.00000175476742..., -712345.119998245...)

The answer given by the solver implies an error of ±
5 * 10^-14, the true error is closer to 10^-10 for the smaller root. When I say smaller I mean in magnitude.

By producing other quadratics with the property that:

It is possible to lose more digits, thus drowning out the solution.

This is not due to any error on your part. The high condition number of this polynomial is causing subtractive cancellation in the quadratic formula ( or whatever other method the solver is using ).

It is for this not well known reason that the quadratic formula is not used in numerical analysis! In short it may be taught everywhere but it is not reliable.

If you are passed the debugging stage and want to add more bells and whistles to this solver, then I could show you a simple modification that will increase the accuracy of the smaller root. A way that makes the quadratic formula somewhat stable.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#3 2011-05-06 22:04:19

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Thank you very much for the testing.

bobbym wrote:

If you are passed the debugging stage and want to add more bells and whistles to this solver, than I could show you a simple modification that will increase the accuracy of the smaller root. A way that makes the quadratic formula somewhat stable.

Yes, please!

(PS: Your current Yoda avatar very much I like.)


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#4 2011-05-06 23:31:48

ganesh
Moderator
Registered: 2005-06-28
Posts: 15,206

Re: Quadratic Equation Solver

Hi MathsIsFun,

The Quadratic Equation Solver is well presented. The solver works well.

I feel the page may include mentioning how to form equation given the roots. Also, the sum of the roots and their product.


Character is who you are when no one is looking.

Offline

#5 2011-05-07 01:21:57

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi;

(PS: Your current Yoda avatar very much I like.)

Yoda? Me that be.

Real Roots Only.

It is known that the product of the roots are equal to c / a . If you have divided through by a to create a monic polynomial then the product of the roots is just c.

When

Or more clearly when b is much larger than 4ac then it is much more numerically stable to get the smaller root by dividing c by the larger root. Provided the larger root > c. When I say larger I mean the absolute value of the two roots.

In the previous example the solvers answer of -712345.12 is used to get the smaller root to high precision:

Notice it agrees with the high precision answer of -0.00000175476742795... much better than before.

In order to understand why this works you only need the knowledge that any time you have a floating point number in a computer that number n is actually represented as:

Where epsilon represents the error in the representation. Any time you divide a smaller number by a larger one the error portion of the numerator is divided, made smaller. So division is an error minimizer while multiplication is an error magnifier. Dividing by 712345 picks up 2 or 3 correct digits for us.

There is a general rule that covers all the real roots:

Forman S. Acton wrote:

In order to preserve significant digits one should always get the larger root ( in absolute value ) by using the sign that avoids a subtraction. That is, use - if b is positive and + if it is negative. Then use x1 * x2 = c for the smaller root.

He means in the quadratic formula and a monic polynomial. This also saves some time because you only need to use the formula once, instead of twice.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#6 2011-05-07 16:26:37

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Excellent. Now I just need to translate that to an algorithm. Something like:

(divide through by a)
(make sure root1 is bigger in magnitude than root2, else swap)
if root1 (much bigger than) root2 {
     root2 = root1/c;
}

Yes?


ganesh wrote:

I feel the page may include mentioning how to form equation given the roots. Also, the sum of the roots and their product.

Good ideas ... I can show them at the bottom.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#7 2011-05-07 18:42:49

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi MIF;

Since you need the discriminant anyway, compute it first. When the roots are real use this routine, else use the one you already have.

1) Divide through by a to turn it into a monic polynomial.

2) Is b negative then use:

3) Is b positive then use:

4) Is root1 bigger than c?

5a) Yes: root2 = c / root1 ; goto 6:

5b) No: Get root2 in the ordinary way. By using the other form of the quadratic.

6) Done:

Example:

b is negative so use:

Notice you did not need a compare, this method always produces the largest root first.

xlarger is bigger than c so,

If xlarger was not greater than c then you would use the other form of the quadratic to get root2.

Have I explained it well enough? If not what do you require?


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#8 2011-05-08 11:37:13

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Thanks "Yoda", will get on to it soon.

Rz4Wx.jpg


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#9 2011-05-08 17:40:47

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi MIF;

Sorry, I am sick so I was unable to answer. Look at the claws on that creature!


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#10 2011-05-09 00:21:47

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Oh no ... a virus of some sort?


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#11 2011-05-09 06:45:19

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Yes, and back problems resurfacing. Soon they will just put me to sleep and toss me out into the dumpster.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#12 2011-05-09 09:34:10

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Virus will clear up. Do exercises for back.

Keep the evil dumpster at bay!


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#13 2011-05-09 11:17:34

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Luckily, I do not have to shop for food. It frightens the kiddies when I am seen lurching down the street. My only hope is the the townspeople do not mistake me for Frankenstein's monster and put me to the torch.

Have you been able to implement the idea? Is the pseudocode clear enough?


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#14 2011-05-09 15:52:34

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

So, does someone else shop for you, or do you run on nuclear energy?

Anyhoo ... new version posted (0.72) ... does it pass the tests?


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#15 2011-05-09 19:32:15

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi MIF;

So, does someone else shop for you, or do you run on nuclear energy?

No, I just have a big supply of food in the house. When I was a kid my grandfather used to say that I ran on atomic energy.

Worked on all my examples, accuracy good.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#16 2011-10-18 19:32:47

amit28it
Member
Registered: 2011-10-18
Posts: 1

Re: Quadratic Equation Solver

Quadratic Equation Solver :
You have done good work and it will be better for us if you will work will on homogenous equation.
As for all Discriminant should be
D=sqrt(b^2-4ac)
and
c=b/a;

Offline

#17 2011-10-18 21:50:33

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi;

The discriminant is not the point of this calculation. Anyway, who said it was anything else ( leave out the square root )?

The discriminant is only used to show when the quadratic formula is unstable for numerical calculation.

The idea is to increase the numerical stability of the quadratic formula. To make it more amenable to computer calculation.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

#18 2011-10-19 15:34:18

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,555

Re: Quadratic Equation Solver

Also, amit28it, your formula is not quite right. The discriminant does not include the square root, it is simply b^2-4ac


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#19 2011-10-19 21:34:32

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 90,791

Re: Quadratic Equation Solver

Hi;

Yes, leave out the square root. Sorry, I missed that.


In mathematics, you don't understand things. You just get used to them.

I agree with you regarding the satisfaction and importance of actually computing some numbers. I can't tell you how often I see time and money wasted because someone didn't bother to run the numbers.

Offline

Board footer

Powered by FluxBB