Sign in to follow this  
Misery

Exact arithmetic

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1302629736' post='4797575']
I'm in need of a good tutorial or how-to about real numbers exact arithmetic.[/quote]
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
I have made [url="http://homepages.ihug.co.nz/~aurora76/Malc/Useful_Classes.htm"]my own libraries[/url] 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 [i]double[/i] 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 this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1302674541' post='4797794']
The thing is that this app will count quite important things and I cannot allow any bugs. I know that gmp is very good.[/quote]
I thought you said it had lots of bugs. Now it's good.

[quote]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.

[quote]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]
[url="http://www.amazon.com/Art-Computer-Programming-Seminumerical-Algorithms/dp/0201896842"]Here you go[/url].

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1302674541' post='4797794']
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.
[/quote]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.

[quote]I have to write my own 2D mesh generator, and I need only most basic usability.[/quote][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.

[quote]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 this post


Link to post
Share on other sites
Well... what a discussion :]
First of all: thank You for all Your comments. :)
They are really helpful.

I am aware of many interesting libs out there like lapack, blas, cgal, gmp, leda, mpfr and so on...
but the thing is that very often You just get to the point where You're stuck on the bug you canno't repair yourself.
As my older Colleagues suggested it is much better to use slower algorithms implemented by Yourself than highly optimized
code You cannot understand at all. If I implement everything myself it won't be so fast as the stuff I mentioned.
But I will be able to repair my code myself :] I won't have to wait (up to year) for libs next release until bug gets fixed for me.
Therefore I decided to buy a little cluster (8 GPUs 4 CPUs) to make it faster, instead of using "black box" code that I cannot control.

When huge commercial app is created (f.x. nastran, fluent etc) every part is made by a speciallist in the matter, under computer specialists control.
And every bug can be fixed without any problems.
I have to create quite huge thing myself so I want to keep as much control as possible. I will possibly include GMP, CGAL LAPACK in my app, but I also want
to have my own - not-super mega highly optimized efficient piece of code just in case, and to have choice if sth goes wrong :)

Thanks again,
I rated You :)

Share this post


Link to post
Share on other sites
If your using GPUs for arbitrary arithmetic and need absolute reliability. I've heard people had issues with low level bit errors within such systems so that might be a concern. Here's a link to a presentation discussing it.


[url="http://saahpc.ncsa.illinois.edu/09/sessions/day2/session2/Maruyama_presentation.pdf"]ECC for GPUs[/url]


-ddn

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this