# Exact arithmetic

This topic is 2593 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello,
I'm in need of a good tutorial or how-to about real numbers exact arithmetic.
I know gmp and leda libs, however I need not much, just a few operators like * / + -
And these libraries ae quite much for me. I need a qiute fast, robust and possible to parallelize approach.
I found a few on the net, but none of them is exactly what I need.
(I need something I can manage myself)

Any ideas? :]
Misery

##### Share on other sites
A real number in general contains an infinite amount of information and thus cannot be represented in a computer. You can restrict yourself to rational numbers or to algebraic numbers, and then there are libraries that can help you. What exactly do you need?

And what's wrong with GMP? It's C++ wrapper is quite usable...

##### Share on other sites

I'm in need of a good tutorial or how-to about real numbers exact arithmetic.

Exact isn't possible unless using algebra system.

Think R = 2 * Pi * r. R cannot be expressed accurately.

So the question needs to be refined - how accurate, for what purpose.

One solution is interval arithmetic. It isn't accurate, but gives bounded errors. It's possible to implement using double precision using SIMD somewhat efficiently.

GPUs aren't known for accuracy, so it again comes down to structuring calculations in such a way to minimize error.

Or, better yet, use Matlab or Mathematica or similar. Matlab has GPU support.

A fair warning - accuracy errors literally destroyed oil platforms and rockets. They are non-trivial to solve it and one needs to approach the problem as a whole. There is no library that just magically makes them disappear.It's all about determining how accurate is accurate enough.

##### Share on other sites
Nothing's wrong with gmp. It's just that I need something really simple. I have to write my own 2D mesh generator, and I need only most basic usability.
Like
bool IsInCircle(Tpt&,TCircle&);
REAL TriangleArea(Tr&)
etc...

Thats all. And GMP is quite huge thing really with lots of bugs. And even more important issue - I cannot change it easily.
I'm quite aware of what rounding errors may lead to
And I am also aware that some real numbers cannot be stored because of their infinity (Pi for example).

The program which I am to create (CFD app) is predicted to work on debian cluster with few (4 to 8) CUDA cards so it would be nice
if exact arithmetic operations could be parallelized.

Thx

##### Share on other sites
If your points have rational coordinates, you should be able to do this with exact arithmetic (squares of distances will stay rational, and areas of triangles will stay rational).

Why do you think GMP has lots of bugs? I've only ever found one, and it wasn't a big deal.

I don't know of a bignum library that can make use of your GPUs.

##### Share on other sites
The thing is that this app will count quite important things and I cannot allow any bugs. I know that gmp is very good. But as i said: I need something I can implement myself. It doesn't have to be
as efficient as gmp, but it hs to be as robust as possible.
I just need some info on how to implement such things. How to store numbers, what data structures to use, what kind of algorithms and so on.

##### Share on other sites
I have made my own libraries for this that are very simple. I can't guarantee that they have no bugs, I can only tell you that the unit tests I have created for them do not currently indicate any bugs with all the compilers I used to compile and run the tests.

Still, I have no way of knowing if what I have, or what else I know about is going to suit you. I can't even be sure that the common double data type isn't sufficient for your needs. You probaly need to do more than just assume that it isn't sufficient, you need to try using it in order to prove that it is not sufficient.

"I cannot allow any bugs" is a very tough, if not impossible, requirement to fulfil. Your code may even have no bugs, but the compiler may have bugs that turn the correct code into incorrect assembly.

##### Share on other sites

The thing is that this app will count quite important things and I cannot allow any bugs. I know that gmp is very good.

I thought you said it had lots of bugs. Now it's good.

But as i said: I need something I can implement myself. It doesn't have to be as efficient as gmp, but it hs to be as robust as possible. [/quote]
Is this homework? I can't imagine any other reason to resist using a library so badly.

I just need some info on how to implement such things. How to store numbers, what data structures to use, what kind of algorithms and so on.[/quote]
Here you go.

##### Share on other sites

The thing is that this app will count quite important things and I cannot allow any bugs. I know that gmp is very good. But as i said: I need something I can implement myself. It doesn't have to be
as efficient as gmp, but it hs to be as robust as possible.
I just need some info on how to implement such things. How to store numbers, what data structures to use, what kind of algorithms and so on.
You use the optimal algorithm, efficient data structures and prove it's correct.

It's the best answer that can be given to such broad question.

I have to write my own 2D mesh generator, and I need only most basic usability.[/quote]
CFD [/quote]
A FEM/BEM mesh?

This type of problems often involves matrices and there is a ton of solutions and documentation out there since it's such an important topic. BLAS is de-facto standard for almost anything related.

It's just impossible to give any kind of useful answer to a non-question. As said, only some very specific edge cases can be solved accurately. For everything else one needs to constrain the error via the solution itself. Hardware it will run on or software written will not matter much.

And GMP is quite huge thing really with lots of bugs[/quote]Every software has bugs. Every. Single. Piece. Of. Code. Binary search, the staple of every CS book is incorrect in almost every single case. And other algorithms are also buggy since they will not work correctly under certain edge cases on certain hardware or platforms.

##### Share on other sites
Perhaps you could represent your numbers using fractions. When you get to the point of integer overflow, you can reduce them with the Euclidean algorithm.

• 36
• 15
• 9
• 23
• 10