Mathematical Exactness

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Prelates, Moderators General

Mathematical Exactness

Postby Anachrome » Sun Dec 18, 2011 9:02 pm UTC

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).
Anachrome
 
Posts: 42
Joined: Sun Sep 04, 2011 5:31 am UTC

Re: Mathematical Exactness

Postby Laguana » Sun Dec 18, 2011 11:00 pm UTC

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.
Laguana
 
Posts: 49
Joined: Sat Jan 19, 2008 10:13 pm UTC

Re: Mathematical Exactness

Postby thoughtfully » Sun Dec 18, 2011 11:07 pm UTC

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.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery
User avatar
thoughtfully
 
Posts: 2115
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN

Re: Mathematical Exactness

Postby Steax » Mon Dec 19, 2011 12:20 am UTC

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.
In Minecraft, I use the username Rirez.
User avatar
Steax
SecondTalon's Goon Squad
 
Posts: 3037
Joined: Sat Jan 12, 2008 12:18 pm UTC

Re: Mathematical Exactness

Postby thoughtfully » Mon Dec 19, 2011 2:14 am UTC

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.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery
User avatar
thoughtfully
 
Posts: 2115
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN

Re: Mathematical Exactness

Postby Steax » Mon Dec 19, 2011 5:13 am UTC

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.
In Minecraft, I use the username Rirez.
User avatar
Steax
SecondTalon's Goon Squad
 
Posts: 3037
Joined: Sat Jan 12, 2008 12:18 pm UTC

Re: Mathematical Exactness

Postby Anachrome » Mon Dec 19, 2011 10:09 am UTC

Thanks for all the great responses guys, I'll see if I can answer your questions and cetera now.
Laguana wrote: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.
thoughtfully wrote: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.
thoughtfully wrote: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.
thoughtfully wrote:If you told us what your exact requirements are, we could help better.
Steax wrote: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).
Anachrome
 
Posts: 42
Joined: Sun Sep 04, 2011 5:31 am UTC

Re: Mathematical Exactness

Postby thoughtfully » Mon Dec 19, 2011 2:54 pm UTC

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.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery
User avatar
thoughtfully
 
Posts: 2115
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN

Re: Mathematical Exactness

Postby korona » Mon Dec 19, 2011 4:58 pm UTC

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.
korona
 
Posts: 375
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Mathematical Exactness

Postby Yakk » Mon Dec 19, 2011 5:30 pm UTC

"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.
Last edited by Yakk on Tue Dec 20, 2011 3:21 am UTC, edited 1 time in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10466
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Mathematical Exactness

Postby phlip » Tue Dec 20, 2011 2:59 am UTC

Yakk wrote: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.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Mathematical Exactness

Postby Yakk » Tue Dec 20, 2011 3:26 am UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10466
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Mathematical Exactness

Postby Anachrome » Tue Dec 20, 2011 10:22 am UTC

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?'
Anachrome
 
Posts: 42
Joined: Sun Sep 04, 2011 5:31 am UTC

Re: Mathematical Exactness

Postby Yakk » Tue Dec 20, 2011 1:17 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10466
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove


Return to Coding

Who is online

Users browsing this forum: Divinas and 6 guests