Calculate Biggest Rational Fraction Within Some Bounds

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 in开发者_JS百科t 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.

The canonical way to solve your problem is with continued fraction expansion. In particular, see this section.

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;
}

Let's try this:

First, we need to turn the float into a fraction. Easiest way I can think to do this is to find the order of magnitude of the epsilon, multiply the float by that order, and truncate to get the numerator.

long orderOfMagnitude = 1
while(epsilon * orderOfMagnitude <1)
   orderOfMagnitude *= 10;

numerator = (int)(target_real*orderOfMagnitude);
denominator = orderOfMagnitude;

//sanity check; if the initial fraction isn't within the epsilon, then add sig figs until it is
while(target_real - (float)numerator / denominator > epsilon)
{
   orderOfMagnitude *= 10;
   numerator = (int)(target_real*orderOfMagnitude);
   denominator = orderOfMagnitude;
}

Now, we can break the fraction down into least terms. The most efficient way I know of is to attempt to divide by all prime numbers less than or equal to the square root of the smaller of the numerator and denominator.

var primes = new List<int>{2,3,5,7,11,13,17,19,23}; //to start us off

var i = 0;
while (true)
{
   if(Math.Sqrt(numerator) < primes[i] || Math.Sqrt(denominator) < primes[i]) break;

   if(numerator % primes[i] == 0 && denominator % primes[i] == 0)
   {
      numerator /= primes[i];
      denominator /= primes[i];
      i=0;
   }
   else
   {
      i++;
      if(i > primes.Count)
      {
        //Find the next prime number by looking for the first number not divisible
        //by any prime < sqrt(number).
        //We are actually unlikely to have to use this, because the denominator
        //is a power of 10, so its prime factorization will be 2^x*5^x
        var next = primes.Last() + 2;
        bool add;
        do
        {
           add = true;
           for(var x=0; primes[x] <= Math.Sqrt(next); x++)
              if(next % primes[x] == 0)
              {
                add = false;
                break;
              }

           if(add)
              primes.Add(next);
           else
              next+=2;   
        } while(!add);
      }
   }
}