Calculate Biggest Rational Fraction Within Some Bounds

Question

I am trying to place currency trades that match an exact rate on a market that only accepts integral bid/offer amounts. I want to make the largest trade possible at a specific rate. This is a toy program, not a real trading bot, so I am using C#.

I need an algorithm that returns an answer in a reasonable amount of time even when the numerator and denominator can be large (100000+).

static bool CalcBiggestRationalFraction(float target_real, float epsilon, int numerator_max, int denominator_max, out int numerator, out int denominator)
{
    // target_real is the ratio we are tryig to achieve in our output fraction (numerator / denominator)
    // epsilon is the largest difference abs(target_real - (numerator / denominator)) we are willing to tolerate in the answer
    // numerator_max, denominator_max are the upper bounds on the numerator and the denominator in the answer
    //
    // in the case where there are multiple answers, we want to return the largest one
    //
    // in the case where an answer is found that is within epsilon, we return true and the answer.
    // in the case where an answer is not found that is within epsilon, we return false and the closest answer that we have found.
    //
    // ex: CalcBiggestRationalFraction(.5, .001, 4, 4, num, denom) returns (2/4) instead of (1/2).


}

I asked a previous question that is similar (http://stackoverflow.com/questions/4385580/finding-the-closest-integer-fraction-to-a-given-random-real) before I thought about what I was actually trying to accomplish and it turns out that I am trying to solve a different, but related problem.

Answer 1

If you want the unreduced fraction, then here's one optimization you can do: Since you'll never be interested in n/2, because you want 2n/4, 4n/8, or 1024n/2048, we only need to check some of the numbers. As soon as we check any multiple of 2, we never need to check 2. Therefore, I believe you can try denominators denominator_max through denominator_max/2, and you'll have implicitly checked all of the factors of those numbers, which would be everything 2 through denominator_max/2.

I'm not at a compiler at the moment, so I haven't checked this code for correctness, or even that it compiles, but it should be close.

static bool CalcBiggestRationalFraction(float target_real, float epsilon, 
    int numerator_max, int denominator_max, 
    out int numerator, out int denominator)
{
    if((int)Math.Round(target_real * denominator_max) > numerator_max)
    {
        // We were given values that don't match up.
        // For example, target real = 0.5, but max_num / max_den = 0.3
        denominator_max = (int)(numerator_max / target_real);
    }

    float bestEpsilon = float.MAX_VALUE;
    for(int den = denominator_max; den >= denominator_max/2, den--)
    {
        int num = (int)Math.Round(target_real * den);
        float thisEpsilon = Math.abs(((float)num / den) - target_real);
        if(thisEpsilon < bestEpsilon)
        {
            numerator = num;
            denominator = den;
            bestEpsilon = thisEpsilon;
        }
    }

    return bestEpsilon < epsilon;
}