Re: Coding of ordered pairs

In article <1189457957.326375.184770@xxxxxxxxxxxxxxxxxxxxxxxxxxx> hagman <google@xxxxxxxxxxxxx> writes:
On 10 Sep., 11:02, Han de Bruijn <Han.deBru...@xxxxxxxxxxxxxx> wrote:
....
I've been sloppy, rather thinking about sqrt(4) = 1.999999999999.. and
sqrt(25) = 4.999999999999.. in a computer.

OK, if you want to have your computer calculate the true value of
trunc(sqrt(integer)), simply use trunc(sqrt(x + .5))
This is safer than trunc(sqrt(x) + eps) -- your sqrt should not
be so bad that it can produce sqrt(n^2+.5) < n for reasonable values
of n

This is actually a ridiculous discussion. If your computer computes
sqrt(4) = 1.999999999.., you better upgrade the software. Getting the
correct answer is trivial. And what a computer does in computing is
part of mathematics, but it is in the field of numerical mathematics. So
if you want to allow such discrepancies, you have to look what that field
has to say about it. In mathematics, sqrt(4) = 2, period. Or is Han
also considering computers that have no representation for "0.0"? (Yes,
they *did* exist, so on those computers 2 * 0.0 != 0.0.) Or computers
where "a + b" is not necessarily "b + a"? And I can go on.

On the other hand, trunc(sqrt(n^2 + .5)) does not necessarily work...
Especially if .5 is much smaller than n^2. But let me give some
actual facts (long ago I did analyse them with truncating arithmetic).
Given floating point numbers with k bits of precision, and assume
truncating arithmetic and N-R for the calculation of the square root.
In the range (1 - 2^(-2k), 1) there are exactly *two* numbers where
N-R does not converge. In all other cases N-R converges to the
properly truncated square root. In those two cases N-R oscillates
between two numbers, one too small and one too large. But neither of
the two cases is the square of a number. I have good reasons to suspect
that something similar happens with rounding arithmetic.

And beware a bit about Cody and Waite. Especially for the square root
their algorithm is slightly wrong. That explains why IBM's software got
better results than their algorithm when implemented on that machine.
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast