Re: Coding of ordered pairs

Dik T. Winter wrote:

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.

There is _no_ problem with the floating point values as such - they are
accurate enough for most purposes. But a problem could occur with the
_truncation_ which is required in order to implement Daryl McCullough's
algorithm. If the (numerical) logarithm would give 1.99999999, instead
of 2.000000001, then Trunc(ln()) would give 1 instead of 2, which is a
significantly different outcome. I didn't actually check out if it can
happen on my computer, with my favorite programming language. It's just
a matter of precaution. Any suggestion better than this is appreciated.

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.

Han de Bruijn

.

Relevant Pages

  • Re: Coding of ordered pairs
    ... part of mathematics, but it is in the field of numerical mathematics. ... 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. ...
    (sci.math)
  • Re: Vector Rotation
    ... if you can do multiplications (for the division, ... For some reason I seem to overlook Newton-Raphson as ... I'm pretty certain that for the square root, N-R is guaranteed ... finding the square root by pairing bits and using trial subtractions. ...
    (comp.dsp)
  • Re: Vector Rotation
    ... Then iterating with N-R: ... so you trade-in the square root for another division. ...
    (comp.dsp)