VeryLong Fractions

[GMarco]

Hi,

I think, I invented the wheel the thousandst time by writinig a very long integer-Library.

Now I wonder how to work with divisions. Of course you can divide with integers and look at the rest.
It is also easy to think about a fraction as a set ot two integers, implementing the known rules for adding, multiplying, ... them.
An other approach is to work with very long integers and remember the position of the comma.
Disadvantage of this is, that you cannot divide by 3 exactly. I do not know how to proceed.

Is there any description of a library working with very long fractions or very long decimal fractions?

A very interesting question is, how to implement the rounding in the different models.
Continued fraction maybe?

Whatever: I am shure that somebody thought about these problems, but with Google i need some keywords to search for. Any hints?


Best Regards
GMarco

[laserlight]

Look at existing bignum libraries, e.g., GMP.

[GMarco]

Look at existing bignum libraries, e.g., GMP.

Hi Laserlight,

i looked at GMP-reference and Java.BigInteger, nice methods provided (like next Prime...), but nothing about fractions.

With fractions I mean some strutcure like
x=(BigInteger p, BigInteger q);
x1*x2=(p1*p2,q1+q2),
x1+x2=(p1*q2+p2*q1,q1*q2),
...

I am especcially interested in fast algorithms for approximate fractions of given fractions.


GMarco

[nuzzle]

Whenever ordinary hardware floating point won't do you need to carefully consider why not?

Is it really inherent to the problem domain? If not it may be possible to do calculations differently for example by algebraic manipulations of formulas and/or adequate approximations.

My point is that maybe it's possible to stay withing hardware supported arithmetics after all.

[superbonzo]

if you're using C++, take a look at the boost rational library. It's specifically designed to be used with an underlying integer type that behaves at least as the usual C integer types with respect to operations complexities and range representability. Indeed, it can be used in conjunction with any C++ big integer library to represent arbitrary rational numbers.

anyway, as nuzzle pointed out, are you sure this really meets your requirements ? for example, if your aim is to represent real numbers with arbitrary precision then it's certainly a bad choice, in general. Just consider that in an arbitrary vicinity of each rational number representable by n-bits there are infinitely many rational numbers that require strictly more than n-bits in order to be represented, for every n. In other words, given a fixed range underlying integer type, you can overflow any such rational via an arbitrarily small step ...

Unless there are specific reasons to not do so ( note that there are infinitely many ways of finitely representing dense subsets of the reals ... ), I think you should stick to floating point numbers or, if you need more accuracy, to some sort of decimal representation with prescribed rounding semantics.

[MikeAThon]

Hi Laserlight,

i looked at GMP-reference and Java.BigInteger, nice methods provided (like next Prime...), but nothing about fractions.

The GMP page explicitly states that it provides for rational numbers of arbitray precision. See http://gmplib.org/

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers.

Here is the link to the GMP manual for describing the functions available for rational numbers: "Rational Number Functions" at http://gmplib.org/manual/Rational-Number-Functions.html

Mike