Re: BigNum -- Floating Point

From: Programmer Dude (Chris_at_Sonnack.com)
Date: 12/19/03 

Date: Fri, 19 Dec 2003 13:36:05 -0600

There's much meat in your post I need to digest, but here's some
brief replies so you know I'm not ignoring you (and thanks for
takin the time to write all that!)....

Paul Hsieh wrote:

>> 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.

Okay, that much I did know. My issue is that--to the greatest
extent *possible*--accuracy is a paramount criterion. It may
be, in fact, THE primary criterion. Speed and space are definitely
secondary. I'm willing to wait a little for the most precise
answer possible.

> 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. But
a more serious answer is that, in those cases, the hardware limit
is the real limit. Period. Want bigger numbers, get more stuff.

And you can represent some pretty large numbers with 40000 bits
or so!

> 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.

>> 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? Isn't that (during generation) the source of all those
fractional digits?

> I think a large part of your problem may be that you might not
> understand the nature of numbers in a precise way.

THAT is quite possible! (-:

? Dividing numbers into "integer" and "decimals" is not really a
> useful classification.

Agreed. I'm not THAT lame!!

> 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! (-:

> 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?).

> [...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. I'm also interested in the
idea that all books, magazine articles, webpages,... all text
can be considered as a very large number. (In a large base--at
the *minimum* you need base 37--which forces you to mono-case
and drops all punctuation and control chars. On the other end
of the spectrum, you could use base 256 or base 128.) Another
interest might be something like pi...in base N...to M digits.

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

> 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.

> ...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.

>> 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.

:-\

Very tasty food for thought. Thanks, Paul!! 

-- 
|_ CJSonnack <Chris@Sonnack.com> _____________| How's my programming? |
|_ http://www.Sonnack.com/ ___________________| Call: 1-800-DEV-NULL  |
|_____________________________________________|_______________________|

Relevant Pages

  • "Algorithmic Randomness, Quantum Physics, and Incompleteness"
    ... all finite sequences are to be found infinitely often and ... different members of the infinite set of random numbers. ... Just using random numbers with initial digits 1 thru 9, ... it generated by a shorter input algorithm than the length ...
    (sci.logic)
  • Re: BCD List to HEX List
    ... nibbles, shifting, and adding, Those are pretty simple, so I asked ... algorithm what the algorithm is intended to achieve ... ... input was a list of decimal digits. ... was to go from BCD to a normal binary integer, ...
    (comp.lang.python)
  • Re: BCD List to HEX List
    ... nibbles, shifting, and adding, Those are pretty simple, so I asked ... algorithm what the algorithm is intended to achieve ... ... that he had lists of digits rather than an integer datatype. ... input was a list of decimal digits. ...
    (comp.lang.python)
  • Re: singleton vs static
    ... it broadcasts the digits to Martians... ... this might be an algorithm that returns n ... All you need is sufficient analysis to be able ... test involving one time through the loop is sufficient to conclude that the ...
    (comp.object)
  • Base64String
    ... How does one represent values in base-64 strings? ... what is the process of converting numerals from other ... These we know of as digits of that system. ... that is so because I am representing them in base 10. ...
    (microsoft.public.dotnet.languages.csharp)