2

Hi all I was wondering is there a class in .Net that is used to calculate precise numbers with no rounding errors?

For example, this is not what I want:

decimal dividend = Decimal.One;
decimal divisor = 3;
dividend/divisor * divisor // gives us 0.9999999999999999999999999999 instead of 1

I was thinking if there is a number class that buffers operation until when we need to display it, in other words it would look like this:

Num n = new Num(1);
n.DivideBy(3);
n.MultiplyBy(3);
n.toString(); // gives us "1"

Num n2 = new Num(n);
n2.DivideBy(3);
int decimal_places = 8;
n2.RoundHalfUp(decimal_places);
n2.toString(); // gives us "0.33333333"

Of course this is just an example implementation. Basically the main point here is I'm searching for a class that does not have any rounding errors (usually by delaying calculations to the last moment).

I understand that performance would be slower than Double or Decimal. But it doesn't have to do calculations blindly fast, as long as it is within acceptable time.

Pacerier
  • 86,231
  • 106
  • 366
  • 634
  • Is an algebraic library that would do cancellations to simplify a statement before solving the kind of thing you're looking for? I haven't come across one, but if that's what you're after maybe someone has some insight... – Rick Liddle Oct 28 '11 at 15:06
  • @RickLiddle It's somewhat that. My requirement is that it does the math "properly" (without rounding errors), and within *acceptable* time. So I would consider doing cancellations to simplify the statement an obvious enhancement (doing it the way humans would have done it) but not a requirement, as long as it does the calculations within *acceptable* time. – Pacerier Oct 28 '11 at 15:20

3 Answers3

7

This is a job for rational numbers. No need to delay anything if you're only doing arithmetic operations (including division).

If you need to compute arbitrary continuous functions (eg. logarithms, cosines, square roots, etc), it becomes way more involved. Keeping track of the needed digits to ensure requested precision is tricky, but definitely doable, albeit inefficient in practice. The idea is to store along each function another function computing a modulus of continuity (you get what one would call "intuitionistic continuous functions").

Note that storing an expression tree doesn't simplify matters much, since you'll need to evaluate the resulting (hopefully simpler) expression.

Another approach would be to store a power series along with a radius of convergence, and compute the sum of the series when requested.

Alexandre C.
  • 55,948
  • 11
  • 128
  • 197
  • Re “Keeping track of the needed digits to ensure requested precision”: to me, it seems the requested precision is infinite. – svick Oct 28 '11 at 15:18
  • @svick: the idea is that you only request the precision at the end of the computation (eg. when displaying the number). At this point, everything is computed (a sort of tree is stored along the way), and the needed digits for each subexpression are computed recursively. This is quite easy to implement in functional languages. Numbers are represented as functions which take an integer `n` and return a rational number within `2^{-n}` of the represented number (those are indeed *true* real numbers !). Someone proficient in F# could give it a try. – Alexandre C. Oct 28 '11 at 15:20
  • The caveat is that equality is undecidable for those numbers. – Alexandre C. Oct 28 '11 at 15:21
  • @AlexandreC. thanks this is good stuff I would do some research on the links/class. – Pacerier Oct 28 '11 at 15:27
  • @Pacerier: if you don't mind math, and are ready to tolerate some Haskell, you have some resource there: http://www.haskell.org/haskellwiki/Exact_real_arithmetic – Alexandre C. Oct 28 '11 at 15:34
1

Your specific problem could be solved by a type that can represent any fraction exactly. You can use a library for that or write one yourself (it shouldn't be that hard).

But if you want to solve the general problem, so that Math.Pow(Math.Sqrt(2), 2) == 2 returns true and that works for arbitrary operations, you would need a type that can represent any calculation and be able to reliably simplify it. Just delaying the calculation isn't enough.

I'm not sure something like this exists or that it's even possible.

svick
  • 236,525
  • 50
  • 385
  • 514
  • Yes you are getting the point here, what I was trying to say is that it "doesn't have to be very smart", but as long as it is "like a human" it's great. (for example, a human could easily tell that Math.Pow Math.Sqrt is cancellable) – Pacerier Oct 28 '11 at 15:23
0

Perhaps an arbitrary precision integer library would be sufficient for your needs?

The linked answer deals with C#, but of course they are really general .NET answers.

Community
  • 1
  • 1
dsolimano
  • 8,870
  • 3
  • 48
  • 63