Does anybody know of recent work on implementing arbitrary-precision real
arithmetic? I'm especially interested in work based upon Jean Vuillemin's 1988
paper "Exact Real Computer Arithmetic with Continued Fractions", though other
methods would also be welcome.
--
Lawrence C Paulson, University Lecturer
Computer Laboratory, University of Cambridge,
Pembroke Street, Cambridge CB2 3QG, England
Tel: +44(0)1223 334623 Fax: +44(0)1223 334678
In article <··········@cantaloupe.srv.cs.cmu.edu>, Lawrence C Paulson <···@cl.cam.ac.uk> writes:
>> Does anybody know of recent work on implementing arbitrary-precision real
>> arithmetic? I'm especially interested in work based upon Jean Vuillemin's 1988
>> paper "Exact Real Computer Arithmetic with Continued Fractions", though other
>> methods would also be welcome.
>>
I'll start off by saying I know almost nothing about this.
I'll end by asking that given arbitary-precision integers, why
can't they be used for the exponent and mantissa representations,
and thus give you arbitarary-precision reals?
You can find a floating-point emulation package (see Linux or BSD) that could be
converted into Lisp and use bignums. Of course, it
may be arbitrary-slow too. If you want something like
automatic-conversion to/from hardware reals that sounds much harder.
-Kelly Murray ···@franz.com
From: John Doner
Subject: Re: arbitrary-precision real arithmetic
Date:
Message-ID: <41fn3j$c9g@news.aero.org>
In article <··········@sparky.franz.com>,
Kelly Murray <···@math.ufl.edu> wrote:
>In article <··········@cantaloupe.srv.cs.cmu.edu>, Lawrence C Paulson <···@cl.cam.ac.uk> writes:
>>> Does anybody know of recent work on implementing arbitrary-precision real
>>> arithmetic? I'm especially interested in work based upon Jean Vuillemin's 1988
>>> paper "Exact Real Computer Arithmetic with Continued Fractions", though other
>>> methods would also be welcome.
>>>
>
>I'll start off by saying I know almost nothing about this.
>I'll end by asking that given arbitary-precision integers, why
>can't they be used for the exponent and mantissa representations,
>and thus give you arbitarary-precision reals?
Once you decide to use integers, however large, for exponent and
mantissa representations in this way, you inevitably introduce
truncation errors. This is so because most reals do not have
finite representations (i.e., they are irrational). Further,
you have to guess how much precision to use at the beginning of
your computations in order to get a desired precision at the
end. An alternative method, maybe better sometimes, would be to
represent a real as a (delayed) function yielding the possibly
infinite stream of integers that constitutes its continued
fraction expansion. If you have ways of performing arithmetic
operations on these objects, you can use them to solve specific
problems and you end up with a function that produces the
continued fraction of the answer, to however many places you
want.
Years ago, Bill Gosper sent me a description of such a system,
and an example of its use to compute pi to thousands on places.
I don't remember whether he included the code, although I still
have it kicking around someplace.
John Doner
In article <··········@news.aero.org>, ·····@aerospace.aero.org (John Doner) writes:
>> In article <··········@sparky.franz.com>,
>> Once you decide to use integers, however large, for exponent and
>> mantissa representations in this way, you inevitably introduce
>> truncation errors. This is so because most reals do not have
>> finite representations (i.e., they are irrational). Further,
Thanks, now I can say I know a little more than
next to nothing about this topic.
My thoughts are why not use integer ratios? But the magnitudes are not
large enough (with limited memory),
so how about using ratios of big-floats?
-Kelly Murray ···@franz.com
In article <············@mulga.cs.mu.OZ.AU>, Bert THOMPSON
<···@munta.cs.mu.OZ.AU> says...
>
>········@munta.cs.mu.OZ.AU (Michael David WINIKOFF) writes:
>
>|>(But the number of computable functions is countable yet the
>|>reals are -un-countable, you say. A logician would point you at the
Loewenheim
>|>- Skolem-Tarski theorem, but I'm not so pretentious. 8^)
>|>(Apologies for the mumbo-jumbo.)
>There are no `real' real numbers. Anything that models the real number
>axioms is real. The Loewenheim-Skolem-Tarski theorem states that any
>axiomatization that has an infinite model has infinite models of all
>possible infinite cardinalities, including countable.
>
>I think the existence of countable models of this sort is called the
Skolem
>Paradox; the resolution of this paradox is trapped somewhere in the
purple
>haze of my undergrad days...
The LST you quoted only applies to first order theories that have a
finite axiomization.
The theory of real numbers has no finite axiomization, because the
statement that "all sets of real numbers that are bounded above have a
least upper bound" has no finite axiomization in first order logic.
So that theorem does not apply. No paradox.
David
--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.
David Richter (········@microsoft.com) wrote:
: In article <············@mulga.cs.mu.OZ.AU>, Bert THOMPSON
: <···@munta.cs.mu.OZ.AU> says...
: >
: >········@munta.cs.mu.OZ.AU (Michael David WINIKOFF) writes:
: >
[stuff deleted..]
: >|>- Skolem-Tarski theorem, but I'm not so pretentious. 8^)
: >|>(Apologies for the mumbo-jumbo.)
: >There are no `real' real numbers. Anything that models the real number
: >axioms is real. The Loewenheim-Skolem-Tarski theorem states that any
: >axiomatization that has an infinite model has infinite models of all
: >possible infinite cardinalities, including countable.
: >
: >I think the existence of countable models of this sort is called the
: Skolem
: >Paradox; the resolution of this paradox is trapped somewhere in the
: purple
: >haze of my undergrad days...
The resolution is simple. You can have a countable model that models the
statement "There are uncountable sets" because of the following.
For a set to be uncountable, we have to show that there is no injective
function from the set of integers to the set (essentially that the set is
not enumerable). It could very well happen that the function that
enumerates some set in the "real world" does not exist in the "small"
countable model. So as far as the model is concerned, the set is uncountable.
So that is the resolution of the Skolem's paradox, indeed it is not paradox
at all.
cheers,
Kannan
Kannan Govindarajan (·······@cs.buffalo.edu) wrote:
: The resolution is simple. You can have a countable model that models the
: statement "There are uncountable sets" because of the following.
: For a set to be uncountable, we have to show that there is no injective
: function from the set of integers to the set (essentially that the set is
: not enumerable).
Oops.. I made the cardinal error. There should be no injective function
from the set to the set of integers, not the other way around. (:-)..
cheers,
Kannan
> Does anybody know of recent work on implementing arbitrary-precision real
> arithmetic? I'm especially interested in work based upon Jean Vuillemin's 1988
> paper "Exact Real Computer Arithmetic with Continued Fractions", though other
> methods would also be welcome.
The paper ``Vuillemin's Exact Real Arithmetic'' from David R. Lester may be of
help. It appeared in the ``Proceedings of the Glasgow Functional Programming
Workshop 1991'' which are published by the Springer-Verlag in the ``Workshops
in Computing Series''. From the acknowledgments given in the paper, I assume
that David wrote an implementation in Orwell.
Cheers,
Manuel
--
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Manuel M.T. Chakravarty, Technical University of Berlin, Germany
World-Wide Web: http://www.cs.tu-berlin.de/~chak/
····@cs.tu-berlin.de, IRC: Chilli
Lawrence C Paulson <···@cl.cam.ac.uk> writes:
Does anybody know of recent work on implementing arbitrary-precision real
arithmetic?
The classical approach to arbitrary-precision real and complex arithmetic
(floating-point numbers with mantissa of any size) is implemented in many
computer algebra systems and the CLISP Common Lisp implementation.
The lazy digit sequence approach (similar to lazy power series) has, for
example, been implemented by Michael Stoll in Common Lisp, 1988.
I'm especially interested in work based upon Jean Vuillemin's 1988
paper "Exact Real Computer Arithmetic with Continued Fractions", though
other methods would also be welcome.
Is the implementation of transcendental functions in a continued fraction
based format as easy as in a floating-point number format?
Bruno
Bruno Haible email: <······@ilog.fr>
Software Engineer phone: +33-1-49083585
In article <··········@cantaloupe.srv.cs.cmu.edu>, Bruno Haible
<···················@ilog.fr> wrote:
> Is the implementation of transcendental functions in a continued fraction
> based format as easy as in a floating-point number format?
See HAKMEM:
ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/cf.html
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <··········@sparky.franz.com> ···@math.ufl.edu (Kelly Murray) writes:
In article <··········@news.aero.org>, ·····@aerospace.aero.org (John Doner) writes:
>> In article <··········@sparky.franz.com>,
>> Once you decide to use integers, however large, for exponent and
>> mantissa representations in this way, you inevitably introduce
>> truncation errors. This is so because most reals do not have
>> finite representations (i.e., they are irrational). Further,
Thanks, now I can say I know a little more than
next to nothing about this topic.
My thoughts are why not use integer ratios?
Read the mans lips :-)
"This is so because most reals do not have
finite representations (i.e., they are irrational)."
Most reals cannot be represented as a rational regardless of
the precision. Examples of such numbers are sqrt(2), e, and pi.
They can however be represented as a (infinite) sequence of rationals
of better and better approximations.
--
-- Lennart Augustsson
[This signature is intentionally left blank.]
>> >> Once you decide to use integers, however large, for exponent and
>> >> mantissa representations in this way, you inevitably introduce
>> >> truncation errors. This is so because most reals do not have
>> >> finite representations (i.e., they are irrational). Further,
>> Thanks, now I can say I know a little more than
>> next to nothing about this topic.
Allow me please to apologize for my bad wording, which I did not
want to imply any "little"ness of the information in the post,
but was referring to my own understanding...
>>
>> My thoughts are why not use integer ratios?
>> Read the mans lips :-)
>> "This is so because most reals do not have
>> finite representations (i.e., they are irrational)."
...which is aptly demonstrated by Lennarts comment!
-Kelly Murray ···@franz.com