This is probably really more of a math problem.
I hope I want have to go into too much (for you, boring) detail about the code,
as the problem resides in this loops.
Please let me know if I provided too little detail :)

Now for the problem:
I would have thought the && decimals <10 would mean 'only' 10 decimals where provided, as the integer named decimals will increase every time the incremental factor is divided by 10, which should mean adding a decimal.

Why am I wrong? The following code outputs 16 decimals when the integer n is set to eg. 3 or 2, but 15 decimals if n is set to 257.

Changing 10 to 100 will make the code take hours to execute, so I'm guessing quite a few decimals are in play :)

int n; //input number
			double itn = 0; //incremental test number
			double i = 1; //incremental factor
			n = Integer.valueOf(args[0]);
			int j = 0;
			int decimals = 0;
	
			while ((itn * itn) != n && decimals < 10) {
	
				if (j > 0) {
					itn = itn - i;
					i = i / 10;
					decimals++;
				}

				if (j == 0) {
					j++;
				}
						
				while ((itn * itn) < n) {
					itn = itn + i;
				}

			}

Recommended Answers

All 11 Replies

Its because of the numerical errors you get when you repeatedly divide i by 10. You should multiply i by 10 and use 1/i instead. You will still get numerical errors and there will be 16 decimals because you are working with doubles and it will prob. not end with zeros, but you will at least not add as much numerical errors as before.

int n; //input number
			double itn = 0; //incremental test number
			double i = 1; //incremental factor
			//n = Integer.valueOf(args[0]);
			n = 10;
			int j = 0;
			int decimals = 0;
	
			while ((itn * itn) != n && decimals < 10) {
	
				if (j > 0) {
					itn = itn - 1/i;
					i = i*10;
					decimals++;
				}

				if (j == 0) {
					j++;
				}
						
				while ((itn * itn) < n) {
					itn = itn + 1/i;
				}
			}
			System.out.println(itn);

I think also it is safe to say that your algoritm is calculating the square root of n. Are you supposed to do it like this? Because there are much faster ways. Google newton-rhapson for example or read this...

http://en.wikipedia.org/wiki/Square_root

Oh and I forgot! You should have posted this under computer science.

Hope I was helpful!

Sorry about posting in the wrong forum :/
It's calculating the square root allright.
Guess you could call it an example of how not to do it :)
I was simply debating with a friend how efficient it would be, but thanks for pointing it out anyway.
I think for efficiency I would try Heron's method.

Back on track:
Thanks for answering :)
I don't get this about numerical errors and why using 1/i is better. Could you please explain it?
Or provide a link for further reading:)

And with 1/i it will still calculate 16 decimals you say?
Why is this?

I don't get this about numerical errors and why using 1/i is better. Could you please explain it?
Or provide a link for further reading:)
Why is this?

Im no expert on exactly how numerical error occur, but computers has limited precision and resources. But specifically, numerical errors get larger when calculating stuff that are approaching singularities.

when you write i = 1/10 you get a small error in your result. Then when you divide i by 10 again you already have an error and are adding more because of the singularity ( i -> 0 ). This might not happen when dividing 1/10, but later in when i is small.

My point was that if you multiply i by 10 instead and do the calculation 1/i once you don't get the accumulating error in i since multiplying 10*10 or 100*10 and so on does't give as much numerical errors, if any. Then you only make the division 1/i once which gives you less error.

Try to print the value of i in your loop after you divide it by 10. You will se that the value isn't exactly what you are expecting. And then print 1/i when you multiply it by 10.

And with 1/i it will still calculate 16 decimals you say?

As I said I'm not completely sure myself about how the errors work, but the first 10 decimals should be correct and the last part is crap which you can throw away. 1/i will probably give some errors to when i is large.

You always try to avoid singularities (like dividing values that are very close to 0) in any calculations since this can cause huge accumulating errors. How you do that can be different for each problem. I didn't find any hardcore links to numerical analysis and errors but here's the wikipedia page which has some useful links.

http://en.wikipedia.org/wiki/Numerical_error

commented: Provided information which helped cast light over the sollution +2

Okay, I can't say I fully understand, but now I see why 1/i is better.
You have been very informative :)

So, I am to understand that the number turns out with 16 decimals instead of 10,
because, to the computer, 0,1 / 10 is not 0,01?
Would it help to use some other classes? like BigDecimal or parts of the Math class?
Or is it simply impossible to get this right?

EDIT:
I tried changing it to

if (j > 0) {
					itn = itn - 1/i;
					i = i * 10;
					decimals++;
					
					NumberFormat formatter = new DecimalFormat("###.###############");
					String f = formatter.format(1/i);
					System.out.println(f);
				}

And the output of f is actually not messed up at all?

0,1
0,01
0,001
0,0001
0,00001
0,000001
0,0000001
0,00000001
0,000000001
0,0000000001

However there are still 16 decimals on itn.

Yeah I know, but there seem to be some kind of numerical errors along the way, maybe when adding to itn. You should really not get hung up on this. I would be happy with the answer and would just throw away the last 6 decimals. The important thing is that you know that, what you have calculated, has 10 decimals of accuracy and the rest is error.

You could also instead of counting how many decimals you have progressed, just calculate the difference between the numerical value and the "real" value and stop the iteration when it reaches a certain accuracy. Like this...

r = numerical root
R = real root
X = R*R, i.e. your n variable.

error = abs(X-(r*r))

In your while loop you say - while(error<someSmallValue) - where someSmallValue is 0.0000000001 if you want 10 decimals of accuracy - instead of counting decimals, this is usually how you handle this when making numerical approximations.

And yes, you should not use types like integers, floats and doubles if you want to do hardcore math stuff. Use the classes that are made for these kind of calculations like BigDecimal etc. (check the java api, java.math), or GMP if your'e into C/C++.

Okay, I'll try and see if using the proper classes might help:)
Hmm I'm not sure I understand though, how would you get the 'real root'?
Or am I missing the point here?

Another thing: I'd suppose using BigDecimal would be enough. I mean, how imprecise can these integers get?
So no need for BigInteger.
Or Is this just a lack of knowledge from my behalf? :)

Of course you don't have the real square root, thats what you want to approximate. But you do have the square of the "real" root which is your input data "n". You only need the square and the approximated root to do the error calculation. The "real" root was used just to to make a point. You want itn*itn to be very close to n, hence abs(n-itn*itn) should be a small number of your choice.

Its not that using integers and doubles are imprecise, as I said you can get the precision you want in your calculation by knowing how big the error is. But if you use BigDecimal etc. you can have an arbitrary amount of precision and size, with your computers memory as a limit. For example you can't use integers, floats or doubles if you want to calculate the square root of a huge number, or if you want more precision than 16 decimals. It all depends on what your doing, if there's no reason to use BigInt then you shouldn't, using integers will probably yield faster execution. But in your case I would use BigDecimal for the input value n also. Real numbers have roots to :) Also an integers max value is not very large.

The important thing here, as in all numerical calculations, is to know how large your error is and to know how much error you can afford to have. This is really important as errors accumulate with time and you often need a way to compensate for the errors.

Imagine a robot with wheels turning 90 degrees around its own center and then driving 10 meters straight forward. If you don't exactly know the precision of the wheels and hence the amount of error when it turns, you cant really say where the robot will end up after it has turned and driven forward. You might measure that it has turned 90 degrees but in real life it is 91 degrees or worse. The outcome of the robots position will vary greatly depending on the errors our hardware and software makes. Knowing the error gives you the possibility to say that the robot is around point x according to some probability function. If you don't know the precision and error, the robot can be almost anywhere, which is a bad robot.

Hope i didn't confuse you with the robot example :)

commented: The problem has been solved, and I really have gotten so much more than just the sollution out of theese answers. +2

No the robot example was clear enough :)
I guess I just don't really understand where the errors occur.
However, I changed the variables BigDecimal's (pretty much all of them, as you cant compare BigDecimals with anything other than BigDecimals)
And guess what, as far as I can tell, the errors are completely gone:)

I'm going to mark the thread as solved. But if you have anything to add on the subject of numerical errors, please feel free to do so as it is an (now almost) entirely unexplored world for me.
Perhaps it will be covered when I start at the university next summer, till then this is really just a hobby:)

Anyway, thank you once more, you have been very very helpful.

Thats great that you want to study more. I'm just done with masters degree in Engineering and Computer Science and I have no good answer to exactly how and when the errors occur. It is a very specific question. You will maybe have to look into how java works and it may also depend on the underlying architecture. If you really want do get into it, I suggest buying a book about numerical analysis. If you are going to study computer science, the best thing to be ahead of is math. You would really benefit from that.

You're probably right :)
I'm actually spending this year studying math, so that (hopefully) i can take a bachelor in software developing starting next summer.

I'll look into to some books on the subject then, thanks for your help, it's much appreciated. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.