Back to General and Gameplay Programming

Exact arithmetic

General and Gameplay Programming Programming

Started by Misery April 12, 2011 05:35 PM

11 comments, last by Zahlman 13 years ago

Misery

354

Author

April 12, 2011 05:35 PM

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? :]
Thanks in advance,

Misery

alvaro

21,604

April 12, 2011 06:23 PM

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...

Antheus

2,410

April 12, 2011 06:34 PM

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.

Misery

354

Author

April 12, 2011 08:18 PM

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

alvaro

21,604

April 12, 2011 09:38 PM

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.

Misery

354

Author

April 13, 2011 06:02 AM

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.

iMalc

2,466

April 13, 2011 07:10 AM

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.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

alvaro

21,604

April 13, 2011 02:00 PM

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.

Antheus

2,410

April 13, 2011 04:01 PM

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.

smart_idiot

1,298

April 14, 2011 12:57 AM

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.

Chess is played by three people. Two people play the game; the third provides moral support for the pawns. The object of the game is to kill your opponent by flinging captured pieces at his head. Since the only piece that can be killed is a pawn, the two armies agree to meet in a pawn-infested area (or even a pawn shop) and kill as many pawns as possible in the crossfire. If the game goes on for an hour, one player may legally attempt to gouge out the other player's eyes with his King.

Exact arithmetic

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Exact arithmetic

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines