Re: BigNum -- Floating Point

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

Date: Sun, 21 Dec 2003 08:51:57 GMT

In article <3FE35325.CC0546D1@Sonnack.com>, Chris@Sonnack.com says...
> Paul Hsieh wrote:
> > 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.
>
> Well, the hardware catches up eventually. It always does.

Factorial is roughly (n/e)^n. Hardware performance and memory increases
roughly at a rate of 2x every 1.5 years (2^t). Factorial growth will beat
Moore's Law any day.

> [...] But a more serious answer is that, in those cases, the hardware limit
> is the real limit. Period. Want bigger numbers, get more stuff.

But why snub a solution that can hold much larger numbers? Why not allow
bigger numbers just come from better software?
 
> And you can represent some pretty large numbers with 40000 bits or so!

For some definitions of "large" ....
 
> > By using an approximation/exponent based representation you can
> > work with these unbelievably large numbers with relative ease.
>
> Certainly, but just to be very clear: my goal is less being able
> to work with huge (but slightly inaccurate) numbers than with
> perhaps smaller but fully precise ones.

But any of the solutions I proposed are scalable to doing both.
 
> >> 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.
>
> Yes, I understood that much. But don't those series contain
> divides?

Usually, but that's not what makes their digits such a convoluted mess. Go
look up the Borwein(?) formula for PI. Its an infinite series in which all the
denominators for the fractions are powers of 2. That means each term in the
series is expressible with a finite number of decimal places in any power of
two base. However, PI is still transcendental regardless of this.

> > In general real numbers are categorized as "real" [...] which is
> > split into the two disjoint sets "transcendental" and "algebraic".
> > [...]
>
> With ya so far! I think I'd heard of "algebraic" numbers long ago.
> The refresher is much appreciated!
>
> > 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.
>
> NOW we're entering territory marked: HERE THERE BE DRAGONS! (-:

I was actuallly trying to find a way to express all this in a way that was as
geared towards a non-mathematician as possible (which still expressing the
concerns of a mathematician.)
 
> > 1) "integers" are closed over +, -, * (though other operators can
> > be defined such as modulo, and integral-approximate-divide.)
>
> And this is what I was getting at when I said that division is the
> source of the need to truncate fractional results. Now I know it's
> because integers are not closed for division (did I say that right?).

Yes you got it right ... but part of the point of going through the other
categories is to help you understand that each category really just represents
larger and larger "closures". Each larger closure allows you access to more
operations (in a mathematical sense -- its still up to you to model your chosen
category in a computer program.) Rather than hacking a solution for division
that can lose some accuracy, you need only augment your numeric model to
represent rationals, then you get division as a property of rational numbers.

> > [...snip more Good Stuff...]
> > 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.
>
> Understood and agreed. It might help to understand some of my
> interests and intended uses. I'd like the user to be able to
> write an RSA algorithm, for example.

Well, you just need an integer library for that -- though you should add in
prime number / factorization support, as well as probabably the Montgomery
Method for performing the RSA modulo product.

> [...] I'm also interested in the
> idea that all books, magazine articles, webpages,... all text
> can be considered as a very large number.

Exercise left to the reader: Excluding the potential use of compression, which
requires more memory -- the raw text or the numeric encoding of that raw text?

> In all cases, accuracy is paramount (I recognize it's not achievable
> in all situations). Even *range* is secondary.

I believe my original proposal called for a totally dynamically settable
accuracy.
 
> > A rational number package in of itself is a useful thing, and
> > rather than using "digital approximation" as you seem to want
> > to do,...
>
> Could you define "digital approximation"? My proposed design takes
> as many digits as the user provides. Since the internal model is
> a binary *integer*, I should only need to be concerned with how
> division can explode fractional digits. That I fix by allowing the
> user to specify division precision.

But that's a hack, and that's what I mean by "digital approximation" ...
 
> > ...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.
>
> Well, consensus does seem to be coming down on the ratios idea.
> I hope to be working on this this weekend, so I'll be thinking
> about algorithms and such.

Well hopefully its worth while for you. Certainly you should be able to get
some reasonably mileage out of a rational number library. 

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

Relevant Pages

  • Re: PEP 327: Decimal Data Type
    ... packed group of digits increases. ... where decimal is more natural for people, so decimal representations ... But rationals at least have a standardized normalization. ... I don't see the point of supporting all bases. ...
    (comp.lang.python)
  • Re: In a Bad Mood
    ... the rationals are a proper subset of ... finite time by a Turing Machine". ... Cauchy sequence or whose digits can be computed by a Turing ... a countably infinite number of Turing Machines, ...
    (sci.logic)
  • Re: Is the question answered?
    ... the reason it has not is that Mr. bimms is unwilling to ... All he can do is repeat his ... To claim that the digits of pi are random is at best completely misleading. ... If suddenly the pool balls started jumping randomly around the table, ...
    (talk.origins)
  • Re: An uncountable countable set
    ... That the calculation of the digits can be done in parallel? ... Yes, as I said, for every finite n your list of transpositions will have ... transformed the list of rationals to another list ... So you claim that with that process you get a well-ordering of the rationals ...
    (sci.math)
  • Re: can BD organize a MIT seminar?? ; #112; 2nd ed; Euclid
    ... And probably another reason Bill Dubuque wants you to ... Iain Davidson further writes: ... Do you think that 100 has two digits or three ...
    (sci.math)