4
$\begingroup$

Suppose I want to do arithmetic without any loss of precision. Floats and doubles are inappropriate. I want to use dynamic memory allocations to store any real number obtained after a finite amount of finite operations (addition, subtraction, multiplication, division), starting from natural numbers without ever losing the slightest chunk of the result.

This means, I don't care at all about Pi or the square root of 2, because I have no finite method to obtain them in the first place. I don't want to apply any transcendental function either (cos/sin) because by definition they would never end.

Intuitively, it is obvious that 1/3 cannot be stored in base 2 or 10 using a finite amount of memory (0.33333...), therefore a correct representation would have to be at least fractional.

If this is possible, surely there must be some software out there who already does this. What would be the standard way to go? Preferably, I want a fast (hardware-accelerated) solution, for example using words as digits instead of bits.

$\endgroup$
2
$\begingroup$

A number is obtained from natural numbers using addition, subtraction, multiplication, or division if and only if it is rational. You can store rational numbers as pairs $(p,q)$ of integers, which represent the number $p/q$ (so $q \neq 0$). You can further assume that $p,q$ are mutually prime.

Libraries implementing rational numbers using arbitrary-precision integers are available, for example GMP.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.