-1

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!

Micahstuh
  • 443
  • 1
  • 5
  • 13
  • Why? This is fundamentally flawed. `int` is base 10. `float` and `double` are base 2. That means `double` cannot accurately represent every number that `int` can. – Zer0 Mar 29 '19 at 03:15
  • 1
    @Zer0 How is `int` base 10? It is still represented in binary. – Nico Schertler Mar 29 '19 at 03:20
  • @NicoSchertler Everything in computers is binary. It's well known `float` and `double` are base 2. [See this link for more info](https://stackoverflow.com/q/618535/3980331) – Zer0 Mar 29 '19 at 03:33
  • @Zer0 Of course. I don't see your point. Every 32-bit `int` can be represented as a 64-bit `double` with a 52 bit mantissa. Anyway, that's not what this question is about. – Nico Schertler Mar 29 '19 at 03:44
  • @NicoSchertler I mentioned this because multiplying an `int` with `double` yields a `double`. And there are plenty of base 10 numbers that binary floating point cannot accurately represent (hence the use of a delta when comparing the result). – Zer0 Mar 29 '19 at 04:40
  • The error is generated by the nature of the algorithm. Some numbers cannot have their decimal components multiplied out, like PI. And for the sake of argument, my solution only needs to handle inputs of less than 1000 with and error of no greater than 0.01. – Micahstuh Mar 29 '19 at 12:11

1 Answers1

2

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
Nico Schertler
  • 32,049
  • 4
  • 39
  • 70