In-Reply-To: Message from Nicholas Clark <[EMAIL PROTECTED]>
of "Sun, 05 Oct 2008 22:13:14 BST." <[EMAIL PROTECTED]>
> Studiously ignoring that request to nail down promotion and demotion, I'm
> going to jump straight to implementation, and ask:
> If one has floating point in the mix [and however much one uses rationals,
> and has the parser store all decimal string constants as rationals, floating
> point enters the mix as soon as someone wants to use transcendental functions
> such as sin(), exp() or sqrt()], I can't see how any implementation that wants
> to preserve "infinite" precision for as long as possible is going to work,
> apart from
> storing every value as a thunk that holds the sequence of operations that
> were used to compute the value, and defer calculation for as long as
> possible. (And possibly as a sop to efficiency, cache the floating point
> outcome of evaluating the thunk if it gets called)
>Nicholas Clark
My dear Nicholas,
You mentioned sin(), exp(), and sqrt() as being "transcendental" functions,
but this is not true! Perhaps you meant something more in the way of their
being--um, "irrational". but far be it from me to risk using so loaded a
word in reference to anyone's hypothetical intentions or rationale! :-)
While all transcendentals are indeed irrationals, the opposite relationship
does *not* apply. It's all really rather simple, provided you look at it
as a brief, binary decision-tree.
=> All reals are also one of either rational or irrational:
+ Rational numbers are those expressible as the RATIO of I/J,
where I is any integer and J any non-zero integer.
- Irrationals are all other reals *EXCEPT* the rationals.
=> All irrationals are also one of either algebraic or transcendental:
+ Algebraic numbers are solutions to polynomial equations of a single
variable and integer coefficients. When you solve for x in the
polynomial equation 3*x**2 - 15 == 0, you get an algebraic number.
- Transcendentals are all other irrationals *EXCEPT* the algebraics.
Thinking of the sine function and its inverse, I notice that
sin(pi/2) == 1 and asin(1) is pi/2. Pi is *the* most famous
of transcendental numbers, and sin() is a transcendental function.
Thinking of the exponential function and its inverse, I notice that
exp(1) == e and log(e) == 1. And e, "Euler's number", is likely the
#2 most famous transcendental, and exp() is a transcendental function.
However, we come now to a problem.
If you solved the simple equation I presented above as one whose solution
was by definition *not* a transcendental but rather an algebraic number,
you may have noticed that solution is 5**(1/2), better known as sqrt(5).
So that makes sqrt(5) an algebraic number, and sqrt() is an algebraic
function, which means therefore that it is *not* a transcendental one.
Q.E.D. :-)
Ok, I was teasing a little. But I'd now like to politely and sincerely
inquire into your assertion that floating point need inevitably enter the
picture just to determine sin(x), exp(x), or sqrt(x).
Your last one, sqrt(), isn't hard at all. Though I no longer recall the
algorithm, there exists one for solving square roots by hand that is only a
little more complicated than that of solving "long division" by hand. Like
division, it is an iterative process, somewhat tedious but quite well-defined
easily implemented even on pen and paper. Perhaps that has something to do
with sqrt() being an algebraic function. :-) j/k
As for the two transcendental functions, this does ask for more work. But
it's not as though we do not understand them, nor how to derive them at
need from first principles! They aren't magic black-ball functions with
secret look-up tables that when poked with a given input, return some
arbitrary answer.
We *know* how to *do* these!
Sure, many and probably most solutions, at least for the transendentals, do
involve power series, and usually Taylor Series. But this only means that
you get to joyfully sum up an infinite sequence of figures receding into
infinity ("And beyond!" quoth Buzz), but where each figure in said series
tends to be a reasonably simple and straightforward computation.
For example, each term in the Taylor Series for exp(x) is simply x**N / N!,
and the final answer the sum of all suchterms for N going from 0 to infinity.
Its series is therefore
x**0 / 0! # er: that's just 1, of course :-)
+ x**1 / 1!
+ x**2 / 2!
+ x**3 / 3!
+ x**4 / 4!
+
+ + + + + + + + + + ad infinitum.
For sin(x), it's a bit harder, but not much: the series is a convergent one
of alternating sign, running N from 0 to infinity and producing a series
that looks like this:
(x**1 / 1!) # er: that's just x, of course :-)
- (x**3 / 3!)
+ (x**5 / 5!)
- (x**7 / 7!)
+ (x**9 / 9!)
-
+ - + - + - + - + ad infinitum.
Each term in the sin(x) series is still a comparitively easy one,
reading much better on paper than on the computer with lazy ASCII
equations, for I assume you'd be subkeen on eqn(1) descriptions. :)
( (-1)**N * (x ** (2*N - 1)) )
/
(2*N + 1)!
where that's a factorial bang, not an exclamatory one. :-)
Now you're very nearly done: all you have left to do to get that perfect
answer is add up infinitely many individual terms, for the limit of that
summed-up infinite series is none other than the *exact* answer to those
transcendental functions. They don't have algebraic solutions, but they
do have algorithmic ones, and this is not rocket science. On the other
hand, you probably can't even *do* rocket science without such nifty
mathematical devices. :-)
Nick, you and I both know the secret of infinity, although your average
pedestrian--call him Zeno--will surely falter in its pursuit. And that
secret is that infinity means nothing fancier than "as many as I jolly well
please, thank you very much". In other words, you just keep going (and
going (and going)), until finally you arrive at however many digits of
precision you've been asked to produce.
Now, just where in those equations I've presented above do you see some
need for and need to resort to lossy floating-point numbers? I don't see
any. Sure, I do see plenty of places for Memoize-style caching of these
numbers of infinite (read: arbitrarily great) precision.
But where is the need floating-point that you seem to see, and why?
Beyong the rockety equations I just presented above, I also have to offer
you not just one, but *two* existence-proofs that you've no need to resort
to machine-native floating-point variables or instructions.
The first is bc(1). It reports that the square root of 5 played
out to to 300 digits of precision is:
$ (echo scale=300; echo 'sqrt(5)') | bc -l
2.2360679774997896964091736687312762354406183596115257242708972454105\
209256378048994144144083787822749695081761507737835042532677244470738\
635863601215334527088667781731918791658112766453226398565805357613504\
175337850034233924140644420864325390972525926272288762995174024406816\
11775908909498492371390729
Here are 50 digits of precision for sin(1):
$ (echo scale=50; echo 's(1)') | bc -l
.84147098480789650665250232163029899962256306079837
And here are 500 digits for exp(1)
$ (echo scale=500; echo 'e(1)') | bc -l
2.7182818284590452353602874713526624977572470936999595749669676277240\
766303535475945713821785251664274274663919320030599218174135966290435\
729003342952605956307381323286279434907632338298807531952510190115738\
341879307021540891499348841675092447614606680822648001684774118537423\
454424371075390777449920695517027618386062613313845830007520449338265\
602976067371132007093287091274437470472306969772093101416928368190255\
151086574637721112523897844250569536967707854499699679468644549059879\
3163688923009879312
So, that's one existence proof.
And if you look at Math::BigFloat, you'll fine the other.
Or bignum, if you prefer.
% perl -Mbignum=p,-305 -E 'say sqrt(5)'
2.23606797749978969640917366873127623544061835961152572427089724541052092563780489941441440837878227496950817615077378350425326772444707386358636012153345270886677817319187916581127664532263985658053576135041753378500342339241406444208643253909725259262722887629951740244068161177590890949849237139072972890
or formatted the way bc does it:
2.2360679774997896964091736687312762354406183596115257242708972454105\
209256378048994144144083787822749695081761507737835042532677244470738\
635863601215334527088667781731918791658112766453226398565805357613504\
175337850034233924140644420864325390972525926272288762995174024406816\
1177590890949849237139072972890
And sin(1) to a ways out:
% perl -Mbignum=p,-55 -E 'say sin(1)'
0.8414709848078965066525023216302989996225630607983710657
Followed by a good 500+ digits of e, with formatting:
% perl -Mbignum=p,-505 -E 'say exp(1)'
2.7182818284590452353602874713526624977572470936999595749669676277240\
766303535475945713821785251664274274663919320030599218174135966290435\
729003342952605956307381323286279434907632338298807531952510190115738\
341879307021540891499348841675092447614606680822648001684774118537423\
454424371075390777449920695517027618386062613313845830007520449338265\
602976067371132007093287091274437470472306969772093101416928368190255\
151086574637721112523897844250569536967707854499699679468644549059879\
316368892300987931277362
So, um, what's that floating-point thing about again, eh? :-)
--tom
