Guest User

Untitled

a guest
Feb 24th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.58 KB | None | 0 0
  1. Let's assume we have a `BigRational` class. This class is used to represent fractions
  2. like A/B (e.g. 1/3, 4/5, 5/4) with a precision that is only limited by the memory your
  3. runtime has available. This means the use-case is numbers that don't typically fit in 64
  4. bits (so we can't just convert them to a pair of `double` or `long` values for example).
  5.  
  6. Now suppose we have a `Round(BigRational a, int digits)` function that rounds the `BigRational`
  7. value to a specified number of digits. How can we do this? We can't just simply convert it
  8. to a `decimal` or `double` and do some rounding before converting it back again in a reasonable
  9. way. Are we stuck? No not at all. In fact, rounding fractions is even easier than rounding
  10. decimal or floating point values. And the best thing is that we will preserve our fractional
  11. quality as well.
  12.  
  13. Let's start with something concrete. Take the `BigRational` below, it's **1/3** which, in
  14. decimal, translates to `0.333333..` that is, a 0 followed by a never ending sequence of 3s.
  15. ```
  16. var oneOverThree = new BigRational(1, 3);
  17. var a = oneOverThree.Numerator;
  18. var b = oneOverThree.Denominator;
  19. ```
  20.  
  21. Now let's say we wanna round this to two decimals. So instead of `0.333...` we get just `0.33`
  22. that is, a 0 followed by two 3s. The first instinct (at least for me) was to try to convert
  23. this into a decimal, cut off any digits that we don't need and be done with it. Sadly, that
  24. approach is not feasible at all.
  25.  
  26. The solution is actually quite simple if we step back. If we had no built-in rounding routine
  27. then how would we round? Well we would multiply by some power of 10 and then just chop off
  28. everything we don't need before dividing it by 10 again. Can we use the same trick? Turns
  29. out we can, we just have to follow the laws of rational numbers a bit more clearly and do
  30. a little bit of switcharoo.
  31.  
  32. We start with creating a new var `c` that is initialized to a value of `10**digits`. So if
  33. we want 3 digits that will be `c = 10**3 = 1000`. Since we're dealing with `BigRational` we
  34. will also use `BigInteger` for our calculations.
  35. ```
  36. var c = BigInteger.Pow(10, digits);
  37. ```
  38.  
  39. Once we have this scaling factor it's super easy to create a new `BigRactional` that is
  40. equivalent to the amount of digits we need. First we need a new *numerator* (this is
  41. the `a2` in the fraction `a2/b2`). This numerator will be equal to `c / b` (that is `100/3` in
  42. this case since the denominator of the fraction we want to round is equal to `3`).
  43. ```
  44. var a2 = a * BigInteger.Divide(c, b); // a2 == 1 * 100 / 3 == 33
  45. ```
  46.  
  47. Since `BigInteger.Divide` does a so-called *integer divide* it has no decimals. They are just
  48. chopped off. This basically gives us a new numerator by scaling the old one up by `10**digits`.
  49.  
  50. For our new demoninator `b2` it's even easier. We'll just multiply our old `a` with our
  51. scaling factor.
  52. ```
  53. var b2 = BigInteger.Divide(a / digits);
  54. ```
  55.  
  56. Yep. We just set it to equal `c` and now we can create our perfectly rounded to `digits` digits
  57. fraction:
  58. ```
  59. var oneOverThreeRoundedToTwoDecimals = BigRational.Normalize(new BigRational(a2, b2));
  60. oneOverThreeRoundedToTwoDecimals.Dump();
  61. // 33/100
  62. ```
  63.  
  64. In the actual code, the method looks like this:
  65. ```
  66. static BigRational Round(BigRational a, int digits)
  67. {
  68. var c = BigInteger.Pow(10, digits);
  69. return BigRational.Normalize(new BigRational(
  70. a.Numerator * BigInteger.Divide(c, a.Denominator),
  71. c));
  72. }
  73. ```
  74.  
  75. If we try it out with a bit more challenging rational like **2/3** (wow!) we expect to
  76. see something like (`66666/100000 == 333333/50000`) when we round it to 5 digits. Let's try it out:
  77. ```
  78. var r2 = new BigRational(2, 3);
  79. Round(r2, 5).Dump()
  80. // 33333/50000
  81. ```
Add Comment
Please, Sign In to add comment