0

I have one simple question.. I have this code: 

program wtf;
var i:integer;
begin
   for i:=1 to 20 do
      if sqrt(i)*sqrt(i)<>i then writeln(i);
   readln
end.

... it goes through the loop 20 times and for numbers from 1 to 20 and it checks if square root multiplied buy square root of same number is equal to that number. If we use mathematical rules this program should never have anything on output but .... I get this :

2
3
5
6
7
8
10
12
13
15
18
19
20

can sombody explain what is going on?

Anders Forsgren
  • 10,827
  • 4
  • 40
  • 77
  • `sqrt` generates floating point numbers. When using floats, on a computer, you cannot compare values and expect absolute equality. You must use a threshold difference comparison. floats are not used to ***count*** things, they are used to ***measure*** things. No two measured values are ever ***exactly*** the same. they are only "close enough". – Charles Bretana Dec 17 '16 at 22:04
  • That's not a very productive mental model. The most useful way to think of this is that not all values can be represented exactly. – David Heffernan Dec 18 '16 at 00:02
  • You cannot represent 0.1 exactly in binary any more than you can 1/3 in decimal. – duffymo Dec 18 '16 at 00:47

2 Answers2

2

This is because of precision. The square root of a number that is not a perfect square will give an irrational number, which cannot be represented in memory properly using floating-point arithmetic.

Instead, the number gets truncated after some digits (in binary, but the concept is the same as in decimal).

The number is now very close to, but not quite, the square root of the original number. Squaring it will produce a number that is very close to the original, but not quite.

Imagine it like this, the square root of 2 is 1.4142135623........(etc.) but it gets cut off to 1.414213 for memory reasons. 1.414213 * 1.414213 = 1.99999840937 and not 2.

However, the square root of 4 is 2, and this can be stored in memory fully, without being cut off after a few decimal places. When you then do 2 * 2 you do get exactly 4.

Sometimes the number might get cut off, but when squaring it is still close enough to produce the original value. This is why 11 does not show.

Max
  • 1,325
  • 9
  • 20
  • Ha you realy think that i didnt think of that xd –  Dec 17 '16 at 22:13
  • That is not quite true couse in the output... there is no 11 or even 1 –  Dec 17 '16 at 22:16
  • You are correct, I will edit my answer – Max Dec 17 '16 at 22:17
  • Wait.. 1 is a square number. It should not be on there. The output is correct for `1`. – Max Dec 17 '16 at 22:29
  • Sry my bad for 1 but i still dont get it for 11 –  Dec 17 '16 at 22:34
  • it gets cut off, but when multiplying you get something like 11.0000000001 which gets cut off to 11 – Max Dec 17 '16 at 22:35
  • I dont think that pascal cuts anything soo i will keep looking for another answer but ty –  Dec 17 '16 at 22:40
  • This question is a duplicate (http://stackoverflow.com/questions/588004/is-floating-point-math-broken). That question has clearer answers. Pascal does cut things off, because it cannot store an infinite string of digits. It stores things in binary for efficiency, and it cuts things off – Max Dec 17 '16 at 22:42
  • @Max: Nonsense. Pascal does not cut things off until they reach the limits of accuracy for the data type in use. You may see things *cut off* when viewing in the debugger, but that's because the *display* is truncated in the debugger. The digits are still there even if the debugger doesn't display them. – Ken White Dec 17 '16 at 22:54
  • @KenWhite I might be wrong, but I think that `sqrt` produces irrational numbers for non-perfect-squares. These, when represented as floating-point numbers in binary (which I think Pascal does), will need to be truncated (as they have an infinite amount of binary digits). They are truncated in binary, as they have reached the limits of the accuracy of the hardware – Max Dec 17 '16 at 22:58
  • No, you're wrong, I"m afraid. Sqrt returns `Extended` which is limited only by the number of significant digits described in the [documentation](http://docwiki.embarcadero.com/RADStudio/Berlin/en/Simple_Types_%28Delphi%29#Real_Types) for that data type (between 10 and 20 significant digits). They are not *truncated in binary*. – Ken White Dec 17 '16 at 23:03
  • @KenWhite Uh, I still don't quite understand. Won't `sqrt` still get rounded after 10 to 20 digits? – Max Dec 17 '16 at 23:06
  • @KenWhite Ok, I just thought I should say `round` because you were saying that `truncated` was wrong. I still do not understand why I was wrong originally? Is it because I said it was truncated in binary, not in decimal? – Max Dec 17 '16 at 23:12
  • There is a lot of confusion here. Irrationality is not relevant. 0.1 is rational but not representable. And there is rounding. Calculations are performed exactly but then rounded to the nearest representable value. – David Heffernan Dec 18 '16 at 00:05
  • @ken Wrong. Results of arithmetic are rounded to nearest representable l and not truncated. – David Heffernan Dec 18 '16 at 00:06
  • @DavidHeffernan `0.1` is not representable, but my point was that any irrational value is not representable. And since (I think?) all `sqrt`s are either integers or irrational, then they are either integers or unrepresentable. – Max Dec 18 '16 at 00:08
  • A naive reader might infer, falsely, that irrationals are not representable but rationals are. That's my point. You didn't draw that out. Anyway, this is a dupe of a question with far better answers. We have a canonical answer to such questions here. – David Heffernan Dec 18 '16 at 00:12
  • @DavidHeffernan Ah, I understand, thanks! – Max Dec 18 '16 at 00:14
  • @KenWhite: floating point does not really "cut off", but it **rounds** to the nearest representable value after every calculation. That means that if the actual result is **very** close to 11, it can get rounded to exactly 11. That is probably why 11 doesn't appear in the list. – Rudy Velthuis Dec 18 '16 at 13:10
  • FWIW, truncating (a.k.a. rounding towards 0) is one of the possible rounding modes an FPU can have. – Rudy Velthuis Dec 18 '16 at 13:12
  • For further reading: [Floating point numbers - sand or dirt](http://www.rvelthuis.de/articles/articles-floats.html) – Rudy Velthuis Dec 18 '16 at 13:14
1

sqrt generates floating point numbers. When using floats, on a computer, you cannot compare values and expect absolute equality. You must use a threshold difference comparison. floats are not used to count things, they are used to measure things, (to count things, use integers),. No two measured (even in the real world) values are ever exactly the same. they are only "close enough".

On a computer, it is impossible to represent every possible real number. SO every calculated value gets represented by the "closest" number in the set of possible numbers, (for that data type), that can be represented on the computer. This means that it is very slightly incorrect, and therefore after a few calculations, it will not conform to perfect equality comparisons.

Charles Bretana
  • 143,358
  • 22
  • 150
  • 216