-1
$\begingroup$

Like the title says, I am trying to solve the quadratic equation while avoiding floating point arithmetic. More specifically, I will be coding this algorithm in C.

I have integer values for a, b, and c. The result can be formatted in any way, though integers would be best. I would also like to avoid losing precision when compared to a traditional floating point solution.

Note this does not have to do with speed or optimization, I don't mind if it takes a little longer, though I would prefer reasonably fast algorithms. Most solutions I have come across are based on multiplying variables by powers of 10.

Answers would be best in pseudocode or C. Thanks

$\endgroup$
  • 3
    $\begingroup$ What should the output of the algorithm be? $\endgroup$ – Yuval Filmus Jun 13 '14 at 1:14
  • 1
    $\begingroup$ If you're going to use the standard solution, you'll have to implement a way to evaluate $\sqrt{b^2-4ac}$ without floating point arithmetic. Luckily for you there are lots of ways to do this, like Newton's method. $\endgroup$ – Rick Decker Jun 13 '14 at 2:56
  • $\begingroup$ @YuvalFilmus I've already stated what the output should be. It should be the same as when performing the same operation with floating point numbers. It can be represented in any reasonable way to do so. My recommendation/preferred representation was to use integers, representing the digits that proceeded/preceded the decimal point $\endgroup$ – Michael Yousef Jun 13 '14 at 4:27
  • 1
    $\begingroup$ What's wrong with the solutions you have come across, which use fixed-point arithmetic? $\endgroup$ – Yuval Filmus Jun 13 '14 at 6:10
  • 3
    $\begingroup$ @MichaelYousef I disagree. Fixed-point arithmetic is the standard approach for making calculations on real numbers in the absence of floating-point arithmetic. Also, it is customary to multiply by powers of 2 (i.e., shift) rather than 10. $\endgroup$ – Yuval Filmus Jun 13 '14 at 17:21
3
$\begingroup$

You could just apply the rational roots theorem and this involves checking a finite number of possibilities. This will only find rational roots.

How do you propose to represent something like the square root of 2? You need a struct or class to do this.

$\endgroup$
  • $\begingroup$ I need to find both roots, regardless of rational or not. For all intents purposes, following the IEEE standard for floating point precision is probably a good place to start. I am also accepting of whatever the IEEE standard would produce for the square root of 2, or any irrational number for that matter. I doubt I will end up storing as many digits in my solution, though. $\endgroup$ – Michael Yousef Jun 13 '14 at 4:37
  • 1
    $\begingroup$ @MichaelYousef I don't think you understand what an irrational number means, such as $\sqrt{2}$. There is no IEEE floating point representation that represents $\sqrt{2}$--only an approximation. $\endgroup$ – Jared Jun 13 '14 at 7:59
  • $\begingroup$ "whatever the IEEE standard would produce". I recognize there's no exact representation, but they still produce a value for it. I am fully aware that there are numbers the IEEE standard cannot properly represent, that doesn't mean I don't want to take a representation of them. Again, whatever the IEEE approximation is would suffice for me. $\endgroup$ – Michael Yousef Jun 13 '14 at 12:51
  • 1
    $\begingroup$ IEEE doesn't "produce" a value for $\sqrt{2}$...an algorithm does. There are two IEEE values that will be on either side of the actual value of $\sqrt{2}$. You can write an algorithm (like Newton's method) to get a particular precision...getting the best possible precision would be fairly involved though (you cannot simply use machine precision). $\endgroup$ – Jared Jun 15 '14 at 4:11
  • 2
    $\begingroup$ Correct Jared, but you can create an object that manipulates $\sqrt{2}$ by using a class or struct. You don't need FP arithmetic $\endgroup$ – ncmathsadist Jun 16 '14 at 0:52
3
$\begingroup$

If you want an infinite precision solution to the equation:

$$ f(x) = ax^2 + bx + c = 0 $$

Then you use Newton's method (or something better) to find:

$$ x_{next} = x - \frac{ax^2 + bx + c}{2ax + b} = \frac{2ax^2 - ax^2 + bx - bx - c}{2ax + b} = \frac{ax^2 - c}{2ax + b} $$

Based on your comments, it would be very difficult (I would think) to find the best possible (i.e. highest precision) value using approximation methods (and you have to realize that virtually every floating point computation is an approximation--even multiplication and even addition).

In my opinion, the solution is to "cheat". Use a higher precision structure to calculate the value then round to your lower precision. For instance in C you could use Newton's method with doubles and require a higher precision than float could possibly offer, then cast your answer to a float--this will give the closest float or more precisely, one of the two closest floats--which one will depend on the compiler (I think the compiler chooses the rounding method, but I may be wrong--it might be the architecture).

If you want to find the closest double value then you need to use something with more precision than a double which would probably require either assembly or, worse, programmatically creating a higher precision value (that would be extremely slow).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.