1

I am currently working on a fraction datatype that is written in C#10 (.NET 6).
It is based on two BigIntegers in the Numerator and Denominator, which means that this fraction basically has infinite precision.

The only problem that now arises is memory consumption.
The Numerator and Denominator both get really big quickly, especially when roots are calculated using Newton's method.

An example for this using Newton's method to calculate the square root of 1/16:

x_0 = 1/16  
x_1 = 17/32  
x_2 = 353/1088  
x_3 = 198593/768128  
x_4 = 76315468673/305089687808  
x_5 = 11641533109203575871233/46566125024733548077568 (≈0.2500000398)

The results get accurate quickly but the "size" of the fraction almost doubles every iteration.
When more precise results are required, the memory usage is just way too high.
A solution to this problem is rounding. I want the user to be able to set a maximum error which the rounded fraction should be in.

My approach was using Euclid's GCD algorithm but modified for this max error clause:

public static Fraction Round(Fraction a, Fraction error)
{
    BigInteger gcd = GCD(Math.Max(a.numerator, a.denominator), Math.Min(a.numerator, a.denominator), error);
    return new Fraction(){ numerator = RoundedDivision(a.numerator, gcd), denominator = RoundedDivision(a.denominator, gcd) };
}

public static BigInteger GCD(BigInteger a, BigInteger b, BigFraction maxError) =>
    new Fraction(){ numerator = BigInteger.Abs(b), denominator = 1 } <= maxError ? a : GCD(b, a % b, maxError * a);

// Rounds an integer division: 0.5 -> 1; -0.5 -> -1
public static BigInteger RoundedDivision(BigInteger a, BigInteger b) => (a*2 + a.Sign * b.Sign * b) / (2*b);

The results looked promising at first, but i ran into cases where the rounded result was outside the specified error.
An example for this using pseudo-code:

value = 878/399 (≈2.12531; value is represented as a fraction of two integers, not the division result)  
error = 1/8 (=0.125)  
Round(value, error) = Round(878/399, 1/8) = 2 (=2/1)

2 is outside of the specified max error by ~0.00031 (878/399 - 1/8 ≈ 2.00031 => 2 shouldn't be possible).
Correct results would be eg. 2.125 or 2.25, because these values lie in the range of 878/399 ± 1/8.

Does someone know why this is happening and how can i fix this?

EDIT: The result of the rounding should still be a fraction.

RD4
  • 135
  • 1
  • 12
  • 2
    well, `878/399` is an _integer division_ - which means it can only ever have an _integer result_, which means: whole number. nothing after the comma. try using floating point instead? – Franz Gleichmann Apr 11 '22 at 06:34
  • The problem is that i have fractions with 300 digits in both numerator and denominator, which is only possible due to BigInteger. There is no standard data type that is "infinitely big" and a floating point number at the same time. – RD4 Apr 11 '22 at 06:38
  • the gist still remains: integers _can not_ possibly contain comma values. by design. [maybe this question](https://stackoverflow.com/questions/2863388/what-is-the-equivalent-of-the-java-bigdecimal-class-in-c) has useful information for you. – Franz Gleichmann Apr 11 '22 at 06:41
  • This is why i have two integers representing a fraction and thus a floating point number. I mainly want to program this myself and not use a third-party library is just practice. But in this post i wanted to ask how to lose some of this precision for memory (and time) optimization. – RD4 Apr 11 '22 at 06:47

0 Answers0