Calculate the largest rational fraction at some boundaries

Question

I am trying to place foreign exchange trades that correspond to the exact rate in the market, which accepts only whole amounts of bids / offers. I want to make the largest deal at a certain rate. This is a toy program, not a real trading bot, so I use C #.

I need an algorithm that returns a response 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 similar (http://stackoverflow.com/questions/4385580/finding-the-closest-integer-fraction-to-a-given-random-real) before I thought about what I'm on I actually tried to achieve it, and it turns out that I'm trying to solve another, but related problem.

Answer 1

If you want an unrestored share, here you can do one optimization: since you are never interested in n / 2, because you want 2n / 4, 4n / 8 or 1024n / 2048, we just need to check some numbers. As soon as we check a few of the multiples of 2, we do not need to check 2. Therefore, I believe that you can try the denominator_max denominator_max through denominator_max/2 , and you will implicitly check all factors of these numbers, that all 2 through denominator_max/2 .

I am not in the compiler at the moment, so I did not check 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; } 

Answer 2

The canonical way to solve your problem is to continue the fraction . In particular, see this section .

Answer 3

Let's try this:

First, we need to turn the float into a fraction. The easiest way I can do this is to find the order of magnitude of 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 split the fraction into the smallest terms. The most effective way that I know is to try dividing by all primes less than or equal to the square root of a smaller number of 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); } } }