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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
.

Relevant Pages

  • Re: Coding of ordered pairs
    ... actual facts (long ago I did analyse them with truncating arithmetic). ... truncating arithmetic and N-R for the calculation of the square root. ... N-R does not converge. ... their algorithm is slightly wrong. ...
    (sci.math)
  • Re: Magdalenian (year seven)
    ... square root of 2, and the longer side by the ... Now let us imagine the circle in the finer grid ... -> Experimental approach to early mathematics ... The ancient tin mines were ...
    (sci.lang)
  • Re: what is etymology? (linguistics and biology)
    ... The Non-European Roots of Mathematics_, ... Egyptians and Babylonians had on the Greeks; ... Babylonian value for the square root of 2 was found. ... of Pythagoras long before the time of Pythagoras, ...
    (sci.lang)
  • Re: sci.lang is not meant for religious propaganda
    ... For example the square root of 2. ... mathematics you can find sophisticated methods for the ... three posts in the thread "Magdalenian experiment ... generation of Paleo-linguists will follow me or not. ...
    (sci.lang)
  • Re: Solving k^m = q mod N
    ... except you explicitly lay out the PRNG algorithm. ... is possible to compute any hexadecimal digit in the binary expansion ... quickly (may give a very fast square root algorithm in fact). ... Mathematics is bigger than that. ...
    (sci.math)