Mathematical Exactness

[Anachrome]

For a couple of projects I'm working on, it makes sense to have a way to use mathematically exact numbers in my code (e.g. representing sqrt(2) as sqrt(2) instead of trying to approximate it). Before I start trying to reinvent the wheel, though, I'd like to know if anything like this has been done before, or if anyone has any ideas how to go about doing this. (Because too be honest, I have only a tenuous idea of how to begin, and a quick google search hasn't been very helpful so far).

[Laguana]

I've heard of this kind of thing being done in haskell before: http://www.haskell.org/haskellwiki/Exac ... arithmetic

Essentially rather than storing a bitstring of the number in some base (fixed point numbers) or scientific notation (floating point numbers), you essentially store a way to calculate the number to an arbitrary precision. Operations on the numbers become operations on these functions.


If you are in a more limited setting, such as only talking about square roots, then you could store them as such, and when combining them use simplification. For example, (1+sqrt(2)) * (1-sqrt(3)) = 1-sqrt(3)+sqrt(2)-sqrt(6). When you want to make use of the end result, you could either print it as such, giving the exact answer, or calculate it to some appropriate precision, where the only inaccuracies are introduced in the last step.

[thoughtfully]

It sounds like you want to keep track of your math symbolically. There are Computer Algebra Systems (the main open source one is Maxima, others you might be familiar with are Maple and Mathematica). Usually, there is some way to link to them from your code. If your needs aren't too sophisticated, a simple, lightweight CAS such as mathomatic would be worth checking out.

If you want to roll your own, then yes, functional languages like Haskell are very well suited to the task. Students of functional programming often do a simple CAS as part of their studies.

As a practical matter, you almost certainly aren't going to gain any precision doing this, and you will sacrifice a lot of development time and some run time. Always keeping in mind the pitfalls of working with floating point arithmetic, of course, but you're stuck with those in either case. You might have other reasons for wanting to work with symbolic math, of course.

[Steax]

Pretty much every major programming language has a library that supports precision math, try searching for it (or tell us your language of choice). These are generally precise enough that doing it symbolically only yields very, very little benefit.

[thoughtfully]

Precision comes down to how your numbers are represented. These libraries work by improving on the IEEE 754 floating point standard formats. Enormous integers (for instance, the ones used in public key cryptography), for example, can fit into a double precision float, but not with exact precision. So unless you are working with numbers that are extremely large or small, they probably won't help you in a measurable way. You might find one that supports some symbolic manipulation, though. You might check out the GMP library.

If you told us what your exact requirements are, we could help better.

[Steax]

Yes, it'd be best to know what we're dealing with here. I was under the impression that Anachrome was in need of some sort of precise math, such as for mathematics or physics.

Both options work, really, and it depends more on what limitations one needs to avoid, what libraries are available for a particular language, etc.

[Anachrome]

Thanks for all the great responses guys, I'll see if I can answer your questions and cetera now.

Essentially rather than storing a bitstring of the number in some base (fixed point numbers) or scientific notation (floating point numbers), you essentially store a way to calculate the number to an arbitrary precision. Operations on the numbers become operations on these functions.

It sounds like you want to keep track of your math symbolically. There are Computer Algebra Systems (the main open source one is Maxima, others you might be familiar with are Maple and Mathematica). Usually, there is some way to link to them from your code. If your needs aren't too sophisticated, a simple, lightweight CAS such as mathomatic would be worth checking out.

Yeah, this seems like what I wanted. I'll have to check out the links and other things you mentioned when I've more time.

If you want to roll your own, then yes, functional languages like Haskell are very well suited to the task. Students of functional programming often do a simple CAS as part of their studies.

That seems like it would be interesting to try. I was originally composing this (if composing is a valid word to use there) in C++, though it occurs to me that it's probably not the best language for problems like these.

If you told us what your exact requirements are, we could help better.

Yes, it'd be best to know what we're dealing with here. I was under the impression that Anachrome was in need of some sort of precise math, such as for mathematics or physics.

The project I've in mind with this is a base-coversion program (base as in binary) which I want eventually to be able to convert between things like base i +/- 1 or phi or sqrt(2). I'd like it to be able to perform exact conversions (the most relavant thing that comes to mind are radix points and repeating decimals: 1/3 should be interpreted as 0.3(...) or somesuch, and I don't want to have to make a thing which tries to guess if some float (or double) is a repeating decimal or just happens to look like one.

Anyways, I don't know if I'm going about this the wrong way or in a way far more tedious than any of the other ways or something, so if you have any ideas, I'd love to hear them.

(And, though I'm working in C++ right now, I don't have any strong reason to remain with it other than the fact that it's a language I know well and enjoy. Though Haskell was mentioned a couple of times, so I'll definitely have a look into that as well, and possibly others).

[thoughtfully]

A rational number class will take care of the repeating decimal problem. That might be enough for you. There are many good rational number libraries for C++. If you want a CAS and are using only a limited number of operations, you might want to roll your own, which would suggest a functional language like Scheme/LISP/OCaml. You could also use Haskell, but that might not be the best first functional language for someone to take on.

[korona]

The concept Laguana referred to is called "computable number". A (real) number is called computable if there exists a turing machine that emits the k-th digit of the number.
Note that the problem of determining whether two computable reals are equal is undecidable (determining whether two computable reals are unequal is semi-decidable).
Also note: there are numbers that are definable but not computable so if you want to work with those numbers you'll need a different representation.

[Yakk]

"Naked" computable numbers will perfectly represent sqrt(2), but won't tell you if sqrt(2)^2 = 2. It will tell you that, for every epsilon you try, that sqrt(2)^2 is within epsilon of 2 -- but it won't give you equality.

To pull off the equality, you need do carry with the number information about how it was constructed, and do transformations on it to see if you can clean it up and deduce equality. It is basically a proof generating problem. As this problem is not solvable in general, your method of solving the problem will be bounded by your toolkit of heuristics.

So you can start with a pretty simple symbolic engine, and a few rules, and improve from there. A high end solution will get ridiculously hard.

Edit: I replaced a few 1s with 2s. Oops.

[phlip]

It will tell you that, for every epsilon you try, that sqrt(2)^2 is within epsilon of 1

Subtly different, but I'd word it as "For every epsilon you try, it will tell you that sqrt(2)^2 is within epsilon of 2". That is, "for all x, you can prove P(x)" holds, but "you can prove that for all x, P(x)" does not hold. Now, this being English, I think your wording could be interpreted either way... better to be unambiguous. Also, I assume the "1"s in your post are a typo.

[Yakk]

Yep. Bad ones. No cookie.

And yes, as it is difficult to feed the naked computable number every epsilon > 0 in finite time, you cannot use such a number to prove that for all epsilon > 0, it is within epsilon of 2, even if that is true.

[Anachrome]

I expect that what I'll actually end up doing is making a system for rational numbers and complex integer bases, and then adding further capabilities on a case by case basis (base sqrt(x) seems like it'd be simple enough to implement by itself). Which actually just raised another question for me (and if this really belongs in its own topic on the maths fora, please let me know): is it possible to determine if a number is representable as a rational number in some base? As in, sqrt(2) is representable in base sqrt(2) as if it were an integer (10) even though it isn't. I'd expect this is related to what Yakk mentioned about equality, so this is more of an abstract, 'assuming I'm able to store and test for equality exact real or complex values, and given a number k and a base b, can k be finitely (or infinitely repeating a la 0.(3)) represented in base b?'

[Yakk]

Every number can be represented as a rational number in some base. The base is itself, and its representation is 10. (This line is a joke)

That sort of looks like the kind of problem that continued fraction mathematics might be able to handle -- I know next to nothing about that subject, however.

The other place I'd peer into is the root polynomials of the two of them. This won't help for transcendental values, but it might help for algebraic values.