Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Let's assume we have a `BigRational` class. This class is used to represent fractions
- like A/B (e.g. 1/3, 4/5, 5/4) with a precision that is only limited by the memory your
- runtime has available. This means the use-case is numbers that don't typically fit in 64
- bits (so we can't just convert them to a pair of `double` or `long` values for example).
- Now suppose we have a `Round(BigRational a, int digits)` function that rounds the `BigRational`
- value to a specified number of digits. How can we do this? We can't just simply convert it
- to a `decimal` or `double` and do some rounding before converting it back again in a reasonable
- way. Are we stuck? No not at all. In fact, rounding fractions is even easier than rounding
- decimal or floating point values. And the best thing is that we will preserve our fractional
- quality as well.
- Let's start with something concrete. Take the `BigRational` below, it's **1/3** which, in
- decimal, translates to `0.333333..` that is, a 0 followed by a never ending sequence of 3s.
- ```
- var oneOverThree = new BigRational(1, 3);
- var a = oneOverThree.Numerator;
- var b = oneOverThree.Denominator;
- ```
- Now let's say we wanna round this to two decimals. So instead of `0.333...` we get just `0.33`
- that is, a 0 followed by two 3s. The first instinct (at least for me) was to try to convert
- this into a decimal, cut off any digits that we don't need and be done with it. Sadly, that
- approach is not feasible at all.
- The solution is actually quite simple if we step back. If we had no built-in rounding routine
- then how would we round? Well we would multiply by some power of 10 and then just chop off
- everything we don't need before dividing it by 10 again. Can we use the same trick? Turns
- out we can, we just have to follow the laws of rational numbers a bit more clearly and do
- a little bit of switcharoo.
- We start with creating a new var `c` that is initialized to a value of `10**digits`. So if
- we want 3 digits that will be `c = 10**3 = 1000`. Since we're dealing with `BigRational` we
- will also use `BigInteger` for our calculations.
- ```
- var c = BigInteger.Pow(10, digits);
- ```
- Once we have this scaling factor it's super easy to create a new `BigRactional` that is
- equivalent to the amount of digits we need. First we need a new *numerator* (this is
- the `a2` in the fraction `a2/b2`). This numerator will be equal to `c / b` (that is `100/3` in
- this case since the denominator of the fraction we want to round is equal to `3`).
- ```
- var a2 = a * BigInteger.Divide(c, b); // a2 == 1 * 100 / 3 == 33
- ```
- Since `BigInteger.Divide` does a so-called *integer divide* it has no decimals. They are just
- chopped off. This basically gives us a new numerator by scaling the old one up by `10**digits`.
- For our new demoninator `b2` it's even easier. We'll just multiply our old `a` with our
- scaling factor.
- ```
- var b2 = BigInteger.Divide(a / digits);
- ```
- Yep. We just set it to equal `c` and now we can create our perfectly rounded to `digits` digits
- fraction:
- ```
- var oneOverThreeRoundedToTwoDecimals = BigRational.Normalize(new BigRational(a2, b2));
- oneOverThreeRoundedToTwoDecimals.Dump();
- // 33/100
- ```
- In the actual code, the method looks like this:
- ```
- static BigRational Round(BigRational a, int digits)
- {
- var c = BigInteger.Pow(10, digits);
- return BigRational.Normalize(new BigRational(
- a.Numerator * BigInteger.Divide(c, a.Denominator),
- c));
- }
- ```
- If we try it out with a bit more challenging rational like **2/3** (wow!) we expect to
- see something like (`66666/100000 == 333333/50000`) when we round it to 5 digits. Let's try it out:
- ```
- var r2 = new BigRational(2, 3);
- Round(r2, 5).Dump()
- // 33333/50000
- ```
Add Comment
Please, Sign In to add comment