7
\$\begingroup\$

I have written some code which works out which sums of reciprocals of whole numbers sum to one, e.g:

\$\frac 12 +\frac 13 +\frac 16 =1 \$

\$\frac 17 +\frac 18 +\frac 19 + \frac1{10} + \frac1{11}+ \frac1{14}+ \frac1{15}+ \frac1{18} + \frac1{20}+ \frac1{22}+ \frac1{24} + \frac1{28}+ \frac1{30} + \frac1{33}=1 \$

RecipSumToOneCalc class:

/// <summary>
/// Works out which reciprocals sum to one e.g. 1/2 + 1/3 + 1/6 = 1
/// </summary>
public class RecipSumToOneCalc
{
    private readonly byte max;
    private readonly bool allowRepetitions;
    private Dictionary<Fraction, CachedResult> cache;

    /// <summary>
    /// Creates a new RecipSumToOneCalc
    /// </summary>
    /// <param name="max">The maximum denominator, inclusive</param>
    /// <param name="allowRepetitions">if true repetitions are allowed e.g. 1/2 + 1/2 = 1; if false they are not</param>
    public RecipSumToOneCalc(byte max, bool allowRepetitions=true)
    {
        this.max = max;
        this.allowRepetitions = allowRepetitions;
        cache = new Dictionary<Fraction, CachedResult>();   
    }

    /// <summary>
    /// Used to store the results of Decompose in the cache
    /// </summary>
    private class CachedResult
    {
        public byte Min;
        public List<byte[]> Results;
    }

    /// <summary>
    /// Returns the result of the calculation
    /// </summary>
    /// <returns>Each array is a series of reciprocals which sums to the number 1; the elements of the array are the denominators of the reciprocals</returns>
    public List<byte[]> Decompose()
    {
        return Decompose(1, Fraction.One) ?? new List<byte[]>();
    }

    /// <summary>
    /// Divides a number by another, returning the result rounded up 
    /// </summary>
    /// <param name="a">the dividend</param>
    /// <param name="b">the divisor</param>
    /// <returns>the quotient, if necessary rounded up to the nearest whole number</returns>
    private static long DivideRoundUp(long a, long b)
    {
        return (a - 1) / b + 1;
    }

    private List<byte[]> Decompose(byte min, Fraction f)
    {         
        if (min>max)    //there are no numbers in the range (min to max) so there can be no results!
        {
            return null;
        }

        byte theMin = Math.Max((byte)DivideRoundUp(f.Denominator, f.Numerator), min);
        if(theMin<=max)
        {
            CachedResult cachedResult;
            List<byte[]> result;
            if (cache.TryGetValue(f, out cachedResult))
            {
                if (cachedResult.Min == min)    //found exact match from the cache, just use this
                {
                    return cachedResult.Results;
                }
                if (cachedResult.Min <= min)    //match on the fraction found but the minimum is lower so need to remove invalid results
                {
                    result = cachedResult.Results.Where(a => a[0] >= min).ToList();
                    return result;
                }
            }

            result = new List<byte[]>();
            for (byte n = theMin; n <= max; n++)
            {
                Fraction oneOver = new Fraction(1, n);
                Fraction remainder = f.Subtract(oneOver);
                if (remainder.IsZero())
                {
                    result.Add(new byte[] { n });   //there is no remainder so an array with a single element is returned
                }
                else
                {
                    List<byte[]> subResults = Decompose(allowRepetitions ? n : (byte)(n + 1), remainder);
                    if (subResults != null)     //we have a remainder and have recursively explored the decomposition of that, which we concatenate to get our results
                    {
                        foreach (byte[] subResult in subResults)
                        {
                            byte[] copy = new byte[subResult.Length + 1];
                            subResult.CopyTo(copy, 1);
                            copy[0] = n;
                            result.Add(copy);
                        }
                    }
                }
            }
            if(cachedResult==null)  //if there is a cachedResult it means a result was previously calculated but the min is not low enough so that result is superceded by this one
            {
                cachedResult = new CachedResult();
                cache[f] = cachedResult;
            }
            cachedResult.Min = min;
            cachedResult.Results = result;
            return result;
        }
        return null;
    }
}

Fraction class:

/// <summary>
/// A fraction of two whole numbers
/// </summary>
public class Fraction
{
    public static readonly Fraction One = new Fraction(1, 1);

    public readonly long Numerator, Denominator;

    /// <summary>
    /// Creates a new fraction
    /// </summary>
    /// <param name="numerator"></param>
    /// <param name="denominator"></param>
    public Fraction(long numerator, long denominator)
    {
        if(denominator < 0)
        {
            numerator = -numerator;
            denominator = -denominator;
        }

        long d = GCD(numerator, denominator);
        if(d>1)
        {
            Numerator = numerator / d;
            Denominator = denominator / d; 
        }
        else
        {
            Numerator = numerator;
            Denominator = denominator;
        }
    }

    /// <summary>
    /// Gets the greatest common divisor of two numbers
    /// </summary>
    /// <returns>the greatest common divisor</returns>
    public static long GCD(long a, long b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }

    public override string ToString()
    {
        return Numerator + "/" + Denominator;
    }

    /// <summary>
    /// Finds out if this fraction is equivalent to zero
    /// </summary>
    /// <returns>true if this is zero; false otherwise</returns>
    public bool IsZero()
    {
        return Numerator == 0;
    }

    public override int GetHashCode()
    {
        return (31 * Numerator + Denominator).GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if(obj==null || !(obj is Fraction))
        {
            return false;
        }
        return Equals((Fraction)obj);
    }

    public bool Equals(Fraction f)
    {
        return f.Numerator == Numerator && f.Denominator == Denominator;
    }

    /// <summary>
    /// Subtracts another fraction from this fraction
    /// </summary>
    /// <param name="f">the other fraction</param>
    /// <returns>a new fraction which is the result of the subtraction</returns>
    public Fraction Subtract(Fraction f)
    {
        return new Fraction(Numerator * f.Denominator - Denominator * f.Numerator, Denominator * f.Denominator);
    }
}

Example of usage:

    RecipSumToOneCalc calc = new RecipSumToOneCalc(33, false);
    List<byte[]> results = calc.Decompose();
    File.WriteAllLines(@"C:\Temp\Reciprocals.csv", results.Select(arr => string.Join(",", arr.Select(f => f))));

I find on my computer that I can't go about max=33 on my computer with allowRepetitions=false (see above) as I get an out of memory error. If you remove the dictionary cache, then this would presumably not happen although it is much slower.

I find a lot of the entries in the cache have no results in the value.

Is their any way of improving this algorithm, i.e. can it be made faster with the same memory usage, or to use less memory with the same efficiency?

\$\endgroup\$
1
\$\begingroup\$

To me a simpler approach would be to calculate the LCM of the denominators as you build a List<Fraction>. Now one more iteration through the list can get a sum of the numerators converted to the LCM equivalent. If that sum matches the LCM of the denominators the sum of the fractions is 1. Here's a demonstration that builds the list from the MathML in your sample:

static void Main()
{
    List<Fraction> fracs = new List<Fraction>();
    XmlDocument xDoc = new XmlDocument();
    xDoc.Load("xmlfile1.xml");
    long accumulatedLCM = 0;
    foreach(XmlNode n in xDoc.GetElementsByTagName("mfrac"))
    {
        fracs.Add(new Fraction(long.Parse(n.ChildNodes[0].InnerText), long.Parse(n.ChildNodes[1].InnerText)));
        if(fracs.Count() == 2)
        {
            accumulatedLCM = LCM(fracs[0].Denominator, fracs[1].Denominator);
        }
        if(fracs.Count() > 2)
        {
            accumulatedLCM = LCM(accumulatedLCM, fracs.Last().Denominator);
        }
    }
    long numSum = 0;
    foreach(Fraction f in fracs)
    {
        numSum += accumulatedLCM / f.Denominator;
    }
    if(numSum == accumulatedLCM)
    {
        Console.WriteLine("True");
    }
    else
    {
        Console.WriteLine("False");
    }
    return;
}
static long GCD(long a, long b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
static long LCM(long a, long b)
{
    return a * (b / GCD(a, b));
}
\$\endgroup\$
0
\$\begingroup\$
  • Document your code better. In particular, there is quit a bit going on in Decompose that is not obvious. Even some comments you do have lead to more questions than answers. For example:

    if (cachedResult.Min <= min)    //match on the fraction found but the minimum is lower so need to remove invalid results
    

    How did these "invalid results" get in our cache to begin with?

  • What good are RecipSumToOneCalc objects? The only thing we can do with one is call Decompose(), which should return the same result no matter how many times it's called. So there's really not any point to constructing one and passing it around in a program. It seems like it would be better to make Decompose static, and make RecipSumToOneCalc's constructor private. Alternatively, I suppose we could call Decompose() in the constructor -- but usually we don't think of constructors being used for heavy computations like that.
  • Fraction components are represented using both longs and bytes. A byte is significantly smaller than a long. (I'm guessing -- but can only guess -- that you use bytes because it leads to a smaller memory footprint? If that's the case, at least document it.)
  • Your Fraction class uses longs to represent numerators and denominators. This probably isn't an issue for this particular problem, but it would be useful for more problems if Fraction supported arbitrary precision. This could be accomplished via BigInteger.
  • Operations on Fractions would be easier to read if you used operator overloading. For example:

    Fraction remainder = f.Subtract(oneOver);

    would become:

    Fraction remainder = f - oneOver;

  • Fraction is incomplete. The only binary operation it supports are Equals and Subtract. But even Subtract could be expressed in terms of + (along with negation).
  • Don't reinvent the wheel. Consider using an existing implementation of rational numbers.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.