Рассчитать наибольшую рациональную дробь в некоторых границах

Question

Я пытаюсь разместить валютные сделки, которые соответствуют точному курсу на рынке, который принимает только целые суммы заявок / предложений. Я хочу сделать максимально возможную сделку по определенной ставке. Это игрушечная программа, а не настоящий торговый бот, поэтому я использую C #.

Мне нужен алгоритм, который возвращает ответ в разумные сроки, даже если числитель и знаменатель могут быть большими (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).


}

Я задал предыдущий вопрос, который аналогичен (/3812531/nahozhdenie-blizhaishei-tselochislennoi-zadannomu-sluchainomu-veschestvennomu-diapazonam-chislitelya-znamenatelya), прежде чем я подумал о том, что на самом деле пытался выполнить, и оказалось, что я пытаюсь решить другую, но связанную проблему.

Answer 1

Каноническим способом решения вашей проблемы является продолжение дробной части .В частности, см. этот раздел .

Answer 2

Если вам нужна нередуцированная дробь, то вот одна оптимизация, которую вы можете сделать: так как вас никогда не заинтересует n / 2 , потому что вы хотите 2n / 4 , 4n / 8 или 1024n / 2048 , нам нужно проверить только некоторые цифры. Как только мы проверяем любое кратное 2, нам никогда не нужно проверять 2. Поэтому я считаю, что вы можете попробовать знаменатели от denominator_max до denominator_max/2, и вы неявно проверили все факторы этих чисел, что быть всем с 1011 по 1012.

В данный момент я не работаю с компилятором, поэтому я не проверял этот код на правильность или даже на то, что он компилируется, но он должен быть закрыт.

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 3

Давайте попробуем это:

Сначала нам нужно превратить число с плавающей точкой в ​​дробь.Самый простой способ сделать это - найти порядок величины эпсилона, умножить число с плавающей точкой на этот порядок и усечь, чтобы получить числитель.

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

Теперь мы можем разбить дробь на наименьшее число.Самый эффективный способ, который я знаю, - попытаться разделить на все простые числа, меньшие или равные квадратному корню меньшего из числителя и знаменателя.

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