numerical conditioning MAGNITUDE and / Aubrey Jaffer (19 Jun 2006 19:40 UTC)
Re: numerical conditioning MAGNITUDE and / Bradley Lucier (22 Jun 2006 02:52 UTC)

numerical conditioning MAGNITUDE and / Aubrey Jaffer 19 Jun 2006 18:47 UTC

Writing arithmetic routines in Scheme does not eliminate the need to
do the proper numerical analysis.  For example, the naive
implementation of complex magnitude and / are:

(define (square z) (* z z))

(define (mag z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))

(define (div z1 z2)
  (define den (+ (square (real-part z2)) (square (imag-part z2))))
  (make-rectangular (/ (+ (* (real-part z1) (real-part z2))
			  (* (imag-part z1) (imag-part z2)))
		       den)
		    (/ (- (* (imag-part z1) (real-part z2))
			  (* (real-part z1) (imag-part z2)))
		       den)))

But these routines both generate intermediate results larger or
smaller than their inputs, overflowing on:

  (/ 1e300+1e300i (* 4 1e300+1e300i))
  (magnitude 1e300+1e300i)

and underflowing on:

  (/ 1e-300+1e-300i (* 4 1e-300+1e-300i))
  (magnitude 1e-300+1e-300i)

MzScheme is broken for both magnitude and /; MIT-Scheme only for /.
Tests for both cases are in "r4rstest.scm"
(http://cvs.savannah.gnu.org/viewcvs/*checkout*/scm/scm/r4rstest.scm?rev=HEAD).

Does SRFI-77 (or R5RS) mandate that floating-point procedures work
for arguments generating the full range of possible outputs?

			      -=-=-=-=-

A correct implementation is:

(define (mag z)
  (define c (abs (real-part z)))
  (define d (abs (imag-part z)))
  (if (< d c)
      (* c (sqrt (+ 1 (square (/ d c)))))
      (if (zero? d) d (* d (sqrt (+ 1 (square (/ c d))))))))

(define (div z1 z2)
  (define a (real-part z1))
  (define b (imag-part z1))
  (define c (real-part z2))
  (define d (imag-part z2))
  (if (< (abs d) (abs c))
      (let ((r (/ d c)))
	(define den (+ c (* d r)))
	(make-rectangular (/ (+ a (* b r)) den)
			  (/ (- b (* a r)) den)))
      (let ((r (/ c d)))
	(define den (+ d (* c r)))
	(make-rectangular (/ (+ b (* a r)) den)
			  (/ (- a (* b r)) den)))))

			      -=-=-=-=-

[1] David Goldberg, "What Every Computer Scientist Should Know About
Floating-Point Arithmetic",
http://cch.loria.fr/documentation/IEEE754/ACM/goldberg.pdf