Click here to Skip to main content
14,929,864 members
Articles / Programming Languages / C#
Tip/Trick
Posted 15 Feb 2015

Stats

25.7K views
728 downloads
21 bookmarked

C# Fast Rational Arithmetic

Rate me:
Please Sign up or sign in to vote.
4.81/5 (19 votes)
22 Feb 2015CPOL5 min read
New Rational class to solve epsilon and robustness problems especially for graphics algorithms.

Introduction

Floating point arithmetic is fast, however, the precision is limited. This is a problem for many algorithms, especially for vector arithmetics. The result of intersection calculations of lines and planes are usually not accurate.
The intersection point of two lines is not exactly on these lines. Therefore it is necessary to compare the results with epsilon tolerances. In result, for all of such algorithms we have only a robustness, there is always input with wrong output.

To solve the problem, it is a known approach to calculate with rational numbers instead with floating point or decimal numbers. This is not as fast but the results are always correct and the precision is unlimited. Internal such number works with numerator and denominator and like school mathematics, we can multiply add, subtract and divide without restrictions.

We can exactly calculate with fractions like 1/3 what would be 0.3333... as floating point number. And fortunately, these operations are enough for the critical vector calculations like dot- and cross product.

Background

Unfortunately, we have no rational number class as part of the system but there are several very similar implementations. For C#, I found the class BigRational in several versions and from several locations, numerator and denominator mostly as System.Numeric.BigInteger.

It works to use such solution but I found out that it is not very efficient.

There is the problem with size. BigInteger has internal int sign and uint[] bits field. The structure size is already 64 bit (32 bit system) and they need two for the Rational class. Therefore Rational is something like a 128 bit data type.
For vector algorithms with thousands of vertices, it needs a lot of memory.

There is the problem with speed. I saw that the Microsoft implementation of BigInteger is not very efficient, probably based on old C++ code without special CLI optimizations.

Therefore, I wrote my own Rational class with some new approaches and I can show that this solution is at least 5 times faster than a solution based on Microsoft BigInteger or similar BigInteger classes.

To solve the size problem, I decided not to use BigInteger. Therefore, I keep numerator and denominator in one array if necessary. In result, I need only half of memory. Additionally, for small numbers, I keep numerator and denominator in the sign field, no array memory is necessary. This works well for a great range of typical numbers: +/- (0..32768) / (1..65536)
Numbers like 0,1,-1, 0.1, 100.5, etc.

To solve the speed problem, I have a set of approaches. I found out that it is definitely faster to use unsafe code for this. Unsafe code can be faster and must not be necessarily unsafe so long as the code is correct.

The typical case is that we need the most memory for interim results. To allocate this memory always in C# arrays is possible but long term we get a lot of GC loops which costs time and is not necessary.

Therefore, I use stackalloc where possible to keep interim results short term. There is additionally a small ring buffer on unmanaged memory in use to keep interim results between operator calls. This is a little bit dangerous, a long sequence of operator calls could end in overflow but only at development time.

To make speed, I reduced function calls where possible. We have no real inline function steering in C# and therefore I wrote self inline code where possible.
Now the code is not very good readable but this is the compromise for 5% more speed.

The bottleneck function for rational arithmetics is always to calculate the greatest common divisor (GCD algorithm). I took the Microsoft BigInteger GCD algorithm and found some nice improvements. The GCD for small numbers was not optimal, many checks and code for cases that are not possible is gone. So we have all together 10% more speed and less code.

Another new concept to make speed is to reduce the GCD calls itself. I found out that especially for interim results, it is many times faster to calculate internal with larger fractions and to apply GCD only at the end before it is necessary to allocate managed memory to keep the final result.

For other important functions like Sign, I never call GCD. The Sign test is important, many calls if we test points against planes for example. For such calls, we need no memory allocation, no GCD and it can be 50 times faster if we process a big array of vertices.

Using the Code

The demo project is a small speed test application.

As reference, I added the class BigRational based on Microsoft BigInteger.

The class NewRational is the new implementation and as one file solution, it is easy to import in other applications.

The speed test is a meaningless calculation on lots of random numbers just to make a lot of calculations similar to sequences of typical vector calculations.

In result, I show and compare the times using BigRational and NewRational. It shows on my i7 machine that NewRational is more than 5 times faster. In 64Bit mode, I get additional 15% more.

Finally, the same calculation in parallel what is more than 3 times faster. Interesting that in parallel mode NewRational is more than 8 times faster. I don't know why.

Don't forget to test in Release mode. In Debug, it's only two times faster because BigInteger is always in release.

Points of Interest

I publish this and hope that others find improvements, extensions or bugs. Some internal details like the ring buffer approach is probably not the best solution. Maybe someone has a general faster implementation. This would be interesting.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

No Biography provided

Comments and Discussions

 
BugPerforming .ToString() on a NewRational, which was created using a double-value, returns a value that deviates from its source. Pin
Member 1268818431-Aug-16 22:23
MemberMember 1268818431-Aug-16 22:23 
GeneralRe: Performing .ToString() on a NewRational, which was created using a double-value, returns a value that deviates from its source. Pin
D. Christian Ohle4-Sep-16 5:35
MemberD. Christian Ohle4-Sep-16 5:35 
GeneralRe: Performing .ToString() on a NewRational, which was created using a double-value, returns a value that deviates from its source. Pin
Member 126881844-Sep-16 21:52
MemberMember 126881844-Sep-16 21:52 
GeneralRe: Performing .ToString() on a NewRational, which was created using a double-value, returns a value that deviates from its source. Pin
D. Christian Ohle4-Sep-16 22:29
MemberD. Christian Ohle4-Sep-16 22:29 
GeneralRe: Performing .ToString() on a NewRational, which was created using a double-value, returns a value that deviates from its source. Pin
Member 126881844-Sep-16 22:34
MemberMember 126881844-Sep-16 22:34 
QuestionGreat Job! Pin
TaiZhong14-Jun-15 17:39
MemberTaiZhong14-Jun-15 17:39 
AnswerRe: Great Job! Pin
D. Christian Ohle14-Jun-15 21:04
MemberD. Christian Ohle14-Jun-15 21:04 
GeneralRe: Great Job! Pin
TaiZhong6-Jul-15 21:56
MemberTaiZhong6-Jul-15 21:56 
SuggestionMy vote of 5 Pin
Oliver Kohl D.Sc.18-Feb-15 22:43
MemberOliver Kohl D.Sc.18-Feb-15 22:43 
GeneralMy vote of 5 Pin
BillWoodruff16-Feb-15 12:23
mveBillWoodruff16-Feb-15 12:23 
QuestionSome more thoughts - epsilon problem still exists also with big-rational numbers Pin
Andreas Gieriet16-Feb-15 10:18
professionalAndreas Gieriet16-Feb-15 10:18 
While your class is useful for sure, your statement on removing the epsilon problem is not correct.
You claim that rational numbers solve the problem of epsilon.
- This is only true if you have calculations in the rational number range only.
- It is not true in general for numbers like (square)roots, trigonometric functions, pi, e.

The best you can get with rational numbers for non-rational numbers is an approximation, which leads to epsilon problems again. The epsilon might be somewhere else than with long double type. I.e. You cannot spirit away the intrinsic problem of limited computer arithmetic, no matter if you use fix point, floating point, (big-)rational, continued fraction, etc.

To consider: graphics algorithms involve also rotations and projections by arbitrary angles (trigonometric operations and/or square roots), intersections with spheres (e.g. for some collision algorithms), etc. Integral or rational numbers are approximations for such numbers/vectors/matrices only.

Example: what is the result with big-rational numbers for the expression sin<sup>-1</sup>(1) - pi/2? Probably not exactly zero.

Big-Rational numbers in computer arithmetic provides a wider range of precision (which you may need for your problem domain) compared with the build-in types like long double. Epsilon problematic still exists, just for other numbers than compared to long double.

Cheers
Andi
AnswerRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
D. Christian Ohle16-Feb-15 11:40
MemberD. Christian Ohle16-Feb-15 11:40 
GeneralRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
D. Christian Ohle16-Feb-15 11:42
MemberD. Christian Ohle16-Feb-15 11:42 
AnswerRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
D. Christian Ohle16-Feb-15 11:49
MemberD. Christian Ohle16-Feb-15 11:49 
GeneralRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
Andreas Gieriet16-Feb-15 11:58
professionalAndreas Gieriet16-Feb-15 11:58 
GeneralRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
D. Christian Ohle16-Feb-15 23:38
MemberD. Christian Ohle16-Feb-15 23:38 
GeneralRe: Some more thoughts - epsilon problem still exists also with big-rational numbers Pin
Andreas Gieriet17-Feb-15 0:10
professionalAndreas Gieriet17-Feb-15 0:10 
GeneralThoughts Pin
PIEBALDconsult16-Feb-15 4:04
professionalPIEBALDconsult16-Feb-15 4:04 
GeneralRe: Thoughts Pin
D. Christian Ohle16-Feb-15 4:53
MemberD. Christian Ohle16-Feb-15 4:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.