Find the smallest integer that when multiplied by a known double, will produce an integer

Question

I have a double input "a". My goal is to find an integer "b" such that "a * b" will produce an integer, plus some allowable amount of error. For example "100.227273 * 22 = 2205 (+ 0.000006 error)", where the answer I want to find is "22".

I have already studdied this post, but I only partially understand the top answer. I could really use some help creating an algorithm that accomplishes this task. I have some code below that works for some cases, but not all.

    private int FindSmallestMultiplier(double input)
    {
        int numerator = 1;
        int temp;
        double output = input;
        double invert = input;
        int denominator = 1;
        List<int> whole = new List<int>();
        double dec = input;
        int i = -1;
        while (Math.Abs(Math.Round(numerator * input)-numerator*input) > 0.001)
        {
            i = i + 1;
            //seperate out the whole and decimal portions of the input
            whole.Add(Convert.ToInt32(Math.Floor(invert)));
            dec = output - whole[i];
            //get the decimal portion of the input, and invert
            invert =  1 / dec;

            //create nested fraction to determine how far off from a whole integer we are
            denominator = 1;
            numerator = 1;
            for(int j = whole.Count-1; j >= 0; j--)
            {
                temp = whole[j] * denominator + numerator;
                numerator = denominator;
                denominator = temp;
            }
        }
        return numerator;
    }

The code above works for many input cases, such as 0.3333, 0.5. An example of where it doesn't work is 0.75, or 0.101, just to name couple out of infinity. Please help me to figure out what is wrong with my code or provide a code example that will produce the desired result. Thank you!

Answer 1

Here is an example implementation of the method described in the linked question. If iteratively calculates new coefficients of the continued fraction. Doing so, it checks if the reconstructed number gives the desired accuracy. And if so, it returns the denominator of the reconstructed fraction as the result

// Reconstructs a fraction from a continued fraction with the given coefficients
static Tuple<int, int> ReconstructContinuedFraction(List<int> coefficients)
{
    int numerator = coefficients.Last();
    int denominator = 1;

    for(int i = coefficients.Count - 2; i >= 0; --i)
    {
        //swap numerator and denominator (= invert number)
        var temp = numerator;
        numerator = denominator;
        denominator = temp;

        numerator += denominator * coefficients[i];
    }
    return new Tuple<int, int>(numerator, denominator);
}

static int FindSmallestMultiplier(double input, double error)
{
    double remainingToRepresent = input;
    List<int> coefficients = new List<int>();
    while (true)
    {
        //calculate the next coefficient
        var integer = (int)Math.Floor(remainingToRepresent);                
        remainingToRepresent -= integer;
        remainingToRepresent = 1 / remainingToRepresent;
        coefficients.Add(integer);

        //check if we reached the desired accuracy
        var reconstructed = ReconstructContinuedFraction(coefficients);

        var multipliedInput = input * reconstructed.Item2;
        var multipliedInputRounded = Math.Round(multipliedInput);
        if (Math.Abs(multipliedInput - multipliedInputRounded) < error)
            return reconstructed.Item2;
    }
}

An example program that attempts to find the multiplier for Pi ...

public static void Main()
{
    var number = Math.PI;
    var multiplier = FindSmallestMultiplier(number, 0.001);
    Console.WriteLine(number + " * " + multiplier + " = " + number * multiplier);

}  

... gives the following output:

3.14159265358979 * 113 = 354.999969855647