Re: BigNum -- Floating Point

From: Paul Hsieh (qed_at_pobox.com)
Date: 12/19/03 

Date: 19 Dec 2003 07:55:46 -0800

Programmer Dude <Chris@Sonnack.com> wrote:
> Paul Hsieh wrote:
> >> I've come to believe the [IEEE-754] semantics don't provide what
> >> I want. I require lossless precision (to the highest extent
> >> possible).
> >
> > First of all, at least *some* of the semantics of IEEE-754 don't
> > necessarily mean that you lose precision. Second of all, I don't
> > think you quite appreciate the difficulty of the requirement of
> > lossless precision.
>
> Hence the "to the highest extent possible". What that ends up
> meaning for me is not truncating results *except* when the result
> (fractional part) runs beyond a user-controllable limit.
>
> > You just want infinite sized fixed point then? You want to
> > represent 2^1000000 using 125K of memory?
>
> Yes (assuming the user's hardware supports it--I don't want the
> software NOT to support it). Because I want to be able to allow
> the user to add one to that and maintain the full number.
>
> > Maybe you have a specific reason for doing this -- in which
> > case "ignoring the exponent" still is not the right answer.
>
> Okay. I stand ready for education!..
>
> > You would still want something like:
> >
> > (fixedPoint*2 + 1) * 2 ^ exponent
> >
> > (Exercise to the reader: What is the ___*2 + 1 doing in there?)
>
> I confess I don't understand what the equation *means*, let alone
> the *2... bit.

I mean that you would represent the floating point number using two
big integers called "fixedPoint" and "exponent". The idea is that
these number pairs would represent that number computed from the
expression I showed above. So the challenge is to make sure that each
number pair represents a unique number, and that numbers in each range
can be covered in a way that is useful to your model for numbers.
 
> What, exactly, am I getting by having an exponent?

It means the memory required for representing a number is just related
to its desired accuracy, rather than its size. Certain useful
mathematical expressions (like factorials, or permutations and
combinations) create enormous numbers that not even an aggressive
bignum library can hold in reasonable memory. By using an
approximation/exponent based representation you can work with these
unbelievably large numbers with relative ease.

> >> Yes. This--from what I can tell (and IANAM!)--only becomes a
> >> major problem with division.
> >
> > So you don't plan on supplying square roots or any transcendental
> > functions either?
>
> Doesn't the (same) problem with those come from having divisions
> IN the algorithms ("series"?) for generating them? I thought I
> had understood that all higher math operations were built on the
> basic four: add, subtract, multiply, divide. Not so?

Uhhh ... no. The reason why transcendental and irrational expressions
like sin/cos/exp/log/sqrt etc are not expressable in any sort of
finite digit represenation in general is because they are computed by
"inifinite series", not just because they have divides in them.

I think a large part of your problem may be that you might not
understand the nature of numbers in a precise way. Dividing numbers
into "integer" and "decimals" is not really a useful classification.
In general real numbers are categorized as "real" (every 1-dimensional
scalar) which is split into the two disjoint sets "transcendental" and
"algebraic". "algebraic" is then contains a subset called "rational"
which contains a subset "integer". A number which is "real" but not
"rational" is usually called "irrational".

Now "integer" I assume you understand. "rationals" are just ratios of
integers (the denominator cannot be 0.) "algebraic" are somewhat more
difficult to describe, but they include rationals and expressions of
sums, products, divisions, and numbers taken to fractional powers of
other "algebraics". They also include the roots of any polynomial,
which often cannot be expressed in a single closed form expression.
"transcendentals" are basically everything else -- these are numbers
like Pi, E(1), and the sum of all 1/(p^2), where p is a positive prime
number.

Now, "rationals" are what is called "dense" over the real line. What
this means is that for any real number you choose (transcendental,
algebraic, or whatever) and margine of error you can find a rational
number which is close enough to that real number to be within your
chose margin of error. It means that as far as distance or difference
metrics are concerned "rationals" are sufficient for approximating any
real number. In fact all the number systems I described are dense
over the real line except integers.

Ok. So what is the relevance of having so many sub-categories of real
numbers? The reason is because they each have something called a
"closure" property over certain operators. I.e., if you apply one of
the sanctioned operator on that number set, you get a result which is
in that same set (with special exceptions like dividing by 0.):

1) "integers" are closed over +, -, * (though other operators can be
defined such as modulo, and integral-approximate-divide.)
2) "rationals" are closed over +, -, *, /.
3) "algebraics" are closed over +, -, *, /, ^(rational) (i.e., raising
to the power of a rational number) and polynomial roots (over
rationals).
4) "reals" are closed over +, -, *, /, ^ (any power), polynomial
roots, and an operation known as "limit" (which can show up in an
advanced college calculus class.)

More simply put, what this means from a practical point of view is: 1)
you can't always divide "integers", you can't always raise to rational
powers either "rationals" or "integers" or solve polynomial equations
with them, and you can't perform infinite sums over "algebraics".

Now, a computer with its finite amount of memory and with a finite
amount of time available to compute representations, can exactly
express integers and even rationals with little trouble. Its also
possible (I think) to represent algebraics and work with them,
however, its very very complicated and not likely worth the trouble.
There are transcendental numbers you cannot faithfully represent with
any algorithm which finishes in a finite number of steps even though
these numbers exist mathematically. (This is a corollary of a theorem
by Cantor.)

Now given these constraints you need to choose what you are going to
try to accomplish. Exact representations of transcendentals are
basically out of the questions, and Algebraics are too much work. So
that leaves rationals.

The expressions I showed you, are in fact subsets of rationals which
one way or another are memory efficient, have reasonable fast
algorithms for computing basic arithmetic and can represent certain
non-numeric quantities (namely infinity, -infinity, and pseudo-illegal
sentinals called "Not a number"s.)

> > In that case, then why not create a rational number package
> > instead? This solves the problem of division and the other
> > elementary arithmetic functions without any loss of precision:
> >
> > numerator / denominator
>
> You're certainly not the first to suggest the idea. Which is
> very definitely under consideration.

Given what you want, and what you have, you'd probably get the
furthest by just taking this step first. A rational number package in
of itself is a useful thing, and rather than using "digital
approximation" as you seem to want to do, you can instead work on
rational approximations which are at least as useful and will provide
a more sane basis from which to perform whatever numerical tasks you
have in mind.

> > The idea would just be to always automatically normalize the
> > fraction by making sure that the denominator was always positive
> > (though you still need to define what you do about dividing by
> > zero) and that the fraction was reduced to its lowest terms by
> > dividing out the greatest common divisor of the numerator and
> > denominator.
> >
> > So in addition to a bare bones bigint package, you would need gcd()
> > and integer division (i.e., best division approximation by integers,
> > rounding down.) Using these one can easily build complete rational
> > number arithmetic and extract digits (in base 10 or whatever you
> > like) easily.
> >
> > Oh and by the way, IAAM, which can sometimes be a useful thing.
>
> Sure! It probably makes the above two paragraphs crystal clear. (-:
> It almost sounds like I need to implement most of what I already
> plan to implement just to support the representation. For example,
> wouldn't the gcd() itself need to be able to handle bigints?

Yes it would. gcd (using the Knuth algorithm) on integers can be
reduced to the following operations: bit shift, bit test, comparison,
subtraction. You can find an example of a gcd algorithm that does not
use a divide here:

    http://www.pobox.com/~qed/32bprim.c

But you also need other special algorithms like modulo, and
integer-approximation-division. 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: time complexity
    ... The modern term ... But it is certainly not the case that algebraics < trancendentals! ... I vaguely remember a proof that between any two rationals we can ... find an infinity of transcendentals. ...
    (comp.lang.c)
  • Re: Cardinality question
    ... >> irrationals but not transcendentals. ... > Algebraics include all of the rationals and a subset ... >> Ergo transcendentals are irrationals. ...
    (sci.math)
  • Re: "irrational" and "transcendental"
    ... irrationals: ... rationals and infinite many irrational algebraics and infinte many ... transcendentals. ...
    (sci.math)
  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... If these sequences are all constructed within the rationals and prior to ... real numbers as Cauchy sequence equivalence classes was abstracted. ... There are some expressions whose solutions correspond ...
    (sci.math)
  • Re: Surrogate factoring approach, analysis
    ... John Roberts-Jones wrote: ... >>I've found I can use some simple expressions to consider my approach ... That I have a finite set out of rationals is an important issue though, ... The mathematics is fascinating and beautiful. ...
    (sci.crypt)