This week's book giveaway is in the JavaScript forum.
We're giving away four copies of Svelte and Sapper in Action and have Mark Volkmann on-line!
See this thread for details.
Win a copy of Svelte and Sapper in Action this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

overflow and underflow

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Hi everybody out there, I just recently joined the Code Ranch community so this is my first post.

I have a problem trying to calculate the roots of the well known quadratic equation ax^2 + b^1 + c = 0 using the formula x =  −b ± √(b2 − 4ac)2a

The problem occurs when a, b, c are big because the result was not the expected. I was searching on the Internet and found that because they are big, a problem known as an overflow happened.

I also found some examples about how to deal with the problem, by checking a + b or a + c if they produced the aforementioned error, but the situation here is that I have a solution formula, with more tan 2 variables (instead of 2 variables examples I have found) and more than add and subtract (/, sqrt)

any ideas?

thanks in advance

 
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can perform your intermediate results using a larger data type. For instance, if your parameters are ints, you can calculate your determinant by casting b to long, and using a long literal for 4.
 
author
Posts: 23883
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

First, welcome to the ranch.

Regarding your question, can you elaborate a bit? Generally, the issues or overflow and underflow are in regards to the fixed point types -- such as byte, short, int, and long. However, for the quadratic equation, the floating point types are generally used -- so, what do you mean by overflow and underflow? Or are you just referring to the lost of precision?

Henry
 
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you get overflow with integers, you get incorrect results and may suffer a change of sign.
System.out.println(45678 * 56789);     45678 ×  56789 =   2594007942
System.out.println(45678 * −56789);   45678 × −56789 = −2594007942
Try that code and you will see what integer overflow looks like. You get overflow in one direction in one line and the other direction in the other, in both cases with a change of sign.
You can see floating‑point overflow discussed in this thread; simply, if the value of a double goes beyond its range, it is converted to ±∞.
I always thought underflow was specifically a floating‑point problem; it the values get so small that the last 1 bit drops off the end of the number's representation, the result degenerates to 0.
 
Julio Moreno
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I really appreciate the answers given to my post, related with overflow and underflow.

In my case I have to work only with integers, maybe the proposal of working with long inside the operators could work. Since the beginning of the problema, it demands to work with integer. In the main method there is a single

line Set<Integer> result = roots(a, b, c) and in the method skeleton: public static Set<Integer> roots(int a, int b, int c), obviously the main goal in this excercise was to get stuck with the types and to resolve it

They probe it with a JUnit test, It passed all, except for big values in a, b, c my program ALWAYS RETURNED a single negative value when calculate the determinant(d) so the roots are imaginary, but in the test they got 2

ROOTS

therefore implying that the d they got is positive

the determinant is calculate as follows: d = (b * b) - (4 * a * c)

My roots were calculated as follows (when determinant are positive are 2 roots because the + -)  

r1 = (int)((-b) + Math.sqrt(d))/(2 * a);
r2 = (int)((-b) - Math.sqrt(d))/(2 * a);

when I reformuled the equation, now without doing the int casting an error saying appears: Type mistmach cannot convert from double to int

Thanks in advance
 
Henry Wong
author
Posts: 23883
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Julio Moreno wrote:
In my case I have to work only with integers, maybe the proposal of working with long inside the operators could work. Since the beginning of the problema, it demands to work with integer. In the main method there is a single



Unfortunately, you already violated that requirement. You are already using double variables; albeit, arguably, it is temporary double variables... but you are using double variables nonetheless.

Julio Moreno wrote:
My roots were calculated as follows (when determinant are positive are 2 roots because the + -)  

r1 = (int)((-b) + Math.sqrt(d))/(2 * a);
r2 = (int)((-b) - Math.sqrt(d))/(2 * a);

when I reformuled the equation, now without doing the int casting an error saying appears: Type mistmach cannot convert from double to int



This is because you are temporarily converting the ints to doubles, which you need to convert back at the end.

So, my recommendation? If you are truly not allowed to use doubles, then you should not use the sqrt() method at all. Or if you are only allowed to use temporary variables (which I still regard as cheating the requirement), then I recommend casting everything to double, do the whole expression as a double expression, and casting back just before assigning the result.

Henry
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When calculating your determinant, there are two terms that can fail due to overflow: (b * b) and (4 * a * c). That means that both of these terms has to be performed in long precision separately. Since the operators inside the terms all have the same precedence, you can do this by converting the first value in each term (b and 4 respectively) to a long. You can cast the b, and you can use a long literal for the 4.
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:. . . there are two terms that can fail due to overflow: (b * b) and (4 * a * c). . . . .

That would mean that
b > √(2³¹ − 1)
and
a × c ≥ 2²⁹
Now, √(2³¹ − 1) = 46340.95... and √(2²⁹) = 23170.475..., so you will need reasonably large ints before you get overflow. The corresponding roots for longs would be 3037000499.976... and
1518500249.988... The first number is beyond the range of an int and the second is about 70% of the maximum for an int.

By root I mean positive square root.
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm assuming your point is that if a and c are large enough, (4 * a * c) will overflow, even if we're performing the calculation in long precision.

I suppose there are two solutions to this problem. Either perform the calculation using BigInteger, or throw an exception when |ac| exceeds (Long.MAX_VALUE / 4).
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was hoping to make enough space that values actually passed won't overflow. If the numbers are so large that 4ac overflows a long, then the precision of a double will be insufficient to handle the size of number and calculate the square roots accurately enough. Remember that a long holds up to 19 digits and a double only has precision enough for 15.9 to 16 digits.
Can you calculate the square root of a BigInteger? Might as well throw an Exception.
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, wow I could have sworn that you can take the root of at least a BigDecimal.

In that case I think the easiest solution is to just convert all parameters to long at the start of the method, and then perform a check that throws an exception:
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Hmm, wow I could have sworn that you can take the root of at least a BigDecimal. . . .

No, I searched the BigDecimal link with ctrl‑F‑root and got no hits. BigDecimal is intended for precise calculations; almost all rational numbers have irrational square roots, so their value cannot be calculated precisely, so BigDecimal doesn't seem to have a square root method. If you go to Math#sqrt, that method is not overloaded; it takes a double parameter. A double is intended for situations where absolute precision is not essential, and the rounding errors in calculating a square root can be tolerated.
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can still calculate them to a given precision right? BigDecimal also stores repeating rational numbers with a finite precision. It wouldn't even have to be very precise, because we're only interested in the positive square root of the determinant if it's an integer.
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How do you know the determinant will be a perfect square of an integer?
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can truncate the positive square root, multiply it by itself and see if the result is equal to the determinant.

⌊√D⌋² == D
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But what if the determinant goes into 19 digits? Your truncated root won't be correct. What if the calculated root as a double ends .9999999...? You can sort out the second problem with round() rather than truncating. Unless you write a square root function with a BigDecimal parameter, you cannot expect any particular precision.
 
Stephan van Hulst
Saloon Keeper
Posts: 12254
259
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah that was my point, that's what I would have done if we could take the root of a BigDecimal.
 
Campbell Ritchie
Marshal
Posts: 70260
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think I might transfer this thread to the Threads forum where it would make a good example of livelock A case for the resolved button?
 
A timing clock, fuse wire, high explosives and a tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    Bookmark Topic Watch Topic
  • New Topic