[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **BClib and real arithmetic**
**From**: Gavin Wraith <gavin@<a href="/cgi-bin/echo.cgi?wraith.u-net.com">...</a>>
**Date**: Mon, 18 Feb 2002 12:43:04 +0000 (GMT)

Thanks for the BCLib which will be a useful
thing to have.
I hope I do not seem to carp if I mention that
though BC gives you big integers it does not
give you real numbers in the sense I meant in
a former posting; modulo problems of storage,
it only gives exact arithmetic for rational
numbers whose denominators (in lowest terms)
are powers of 10. What I meant was a format
that gives, modulo problems of storage, ALL
computable real numbers. In this case the
size is measured not by the number of decimal
digits but by the algorithmic complexity of
the number.
An integral unimodular 2x2 matrix (element of
SL_2(Z))
a b
c d
(unimodular <=> ad-bc = 1) defines a conformal
transformation x => (ax+b)/(cx+d). This in turn
defines a rational interval (b/d, (a+b)/(c+d)),
the image of the unit interval (0,1) under the
transformation. The datatype for a real number
used for the Imperial College exact real arithmetic
system is that of a lazy stream of elements of
SL_2(Z). Real numbers are represented by
code defining an iterator that produces a stream
satisfying conditions that ensure a nested sequence
of rational intervals. The clever part is having
efficient methods implementing addition and
multiplication that preserve the conditions.
In performing a calculation you have to supply
a threshold width, so that the calculation stops
when the result lies in an interval whose width is
smaller, but other than that no truncations or
approximations are made.
--
Gavin Wraith (gavin@wraith.u-net.com)
Home page: http://www.wraith.u-net.com/