Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!lll-lcc!ames!amdahl!drivax!tyler
From: tyler@drivax.UUCP
Newsgroups: comp.lang.c
Subject: Re: C and Floating Point
Message-ID: <1163@drivax.UUCP>
Date: Mon, 6-Apr-87 19:25:43 EST
Article-I.D.: drivax.1163
Posted: Mon Apr  6 19:25:43 1987
Date-Received: Thu, 9-Apr-87 02:19:34 EST
References: <15958@sun.uucp> <5716@brl-smoke.ARPA> <14681@cca.CCA.COM>
Reply-To: tyler@drivax.UUCP (William Tyler)
Organization: Digital Research, Monterey
Lines: 64
Keywords: C Fortran Floating Point

In article <14681@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes:
>We have a iterative process which generates a floating point number,
>x, with the following iteration equation

>	x <- x + delta

>where delta is a function of x and where it is expected that the
>iteration converges to some limit point x0.  We have the generic
>problem of determining when the iterative sequence has converged,

>The iteration will have converged if the iteration equation does
>not change the value of x; ..... Is the following pseudo code acceptable?

>	if ((x+delta)==x) then terminate_iteration
>	else continue_iteration

This is unacceptable in general, because, at the limit, in our discrete 
world, you may find that the successive values for x cycle through 2 or 
more very nearly equal values.  That is, x1+delta(x1) = x2; x2+delta(x2)=x1 
where x1 and x2 are both very close together.  This could well happen 
when the mathematical limit of the sequence lies between x1 and x2.

>Alternatively should one use

>	if (delta>0.) then
>		if ((x+delta)<=x) then terminate_iteration
>		else continue_iteration
>	else if (delta<0.) then
>		if ((x+delta)>=x) then terminate_iteration
>		else continue_iteration
>	else terminate_iteration

>or is this also unacceptable?  If so, why?  Is there a best method?
>What is it, and what are the issues involved?

This method suffers from the same problem, as well as being costly to
compute.  

I don't know a best method, however if you know something about the 
direction of approach to the limit, you can do fairly well with one of 
the two following approaches:

1.  If the x values alternately are above and below the limit, just go
    till the absolute value of delta is less than your acceptable error
    level.

2.  If x monotonically increases (decreases) to the limit, go until
    EITHER two successive values are the same, OR until a change in 
    direction is observed.

If you know the convergence rate of the sequence, you can do reasonably
well by just counting iterations, especially if you have a good starting
value.  This has the additional virtue that counting iterations doesn't add
much overhead to your loop.

>You will be given a test on this at the end of the week.  No grade
>will be given, but, if your answers are incorrect, World War III
>will happen.

Please direct flames to me personally, rather than starting WW III.

-- 

Bill Tyler ... {seismo,hplabs,sun,ihnp4}!amdahl!drivax!tyler