Алгоритм поиска общего множителя для преобразования десятичных чисел в целые числа

Я бы умножил на что-то достаточно большое (100000000 для 8 знаков после запятой), а затем разделил бы на НОД полученных чисел. В итоге вы получите кучу наименьших целых чисел, которые можно передать другому алгоритму. После получения результата повторите процесс в обратном порядке, чтобы восстановить исходный диапазон.

На каком языке ты программируешь? Что-то вроде

myNumber.ToString().Substring(myNumber.ToString().IndexOf(".")+1).Length

даст вам количество десятичных знаков для двойника в C#. Вы можете пропустить через это каждое число и найти наибольшее количество десятичных знаков (x), а затем умножить каждое число на 10 в степени x.

Обновлено: из любопытства, что это за запечатанная система, в которую вы можете передавать только целые числа?

Грег: Хорошее решение, но не станет ли вычисление НОД, которое является обычным для массива из 100+ чисел, немного дороже? И как бы вы это сделали? Легко сделать НОД для двух чисел, но для 100 становится сложнее (я думаю).

Злой Энди: Я программирую в .Net, и решение, которое вы предлагаете, в значительной степени соответствует тому, что мы делаем сейчас. Я не хотел включать его в свой первоначальный вопрос, потому что я надеялся на какое-то нестандартное (или, по крайней мере, мое) мышление, и я не хотел портить ответы людей потенциальным решением. Хотя у меня нет надежной статистики производительности (потому что у меня не было другого метода для сравнения), я знаю, что синтаксический анализ строк был бы относительно дорогим, и я полагал, что чисто математическое решение потенциально может быть более эффективным. Честно говоря, текущее решение для синтаксического анализа строк находится в производстве, и пока не было претензий к его производительности (оно даже находится в производстве в отдельной системе в формате VB6, и там тоже нет никаких претензий). Просто это кажется неправильным, я предполагаю, что это оскорбляет мою чувствительность к программированию - но это вполне может быть лучшим решением.

Тем не менее, я все еще открыт для любых других решений, чисто математических или иных.

В цикле получить мантиссу и показатель степени каждого числа как целые числа. Вы можете использовать frexp для экспоненты, но я думаю, что для мантиссы потребуется битовая маска. Найдите минимальный показатель степени. Найдите самые значащие цифры в мантиссе (перебирайте биты в поисках последней "1") или просто используйте заранее определенное количество значащих цифр. Тогда ваш множитель будет примерно таким, как 2 ^ (numberOfDigits-minMantissa). «Что-то вроде», потому что я не помню смещения / смещения / диапазоны, но думаю, что идея достаточно ясна.

Если вы хотите найти какое-то целое число N, чтобы N * x также было точным целым числом для набора чисел с плавающей запятой, x в данном наборе - все целые числа, тогда у вас есть в основном неразрешимая проблема. Предположим, что x = наименьшее положительное число с плавающей запятой, которое может представлять ваш тип, скажем, 10 ^ -30. Если вы умножите все свои числа на 10 ^ 30, а затем попытаетесь представить их в двоичном формате (иначе почему вы так стараетесь сделать их целыми числами?), То вы потеряете практически всю информацию о других числах из-за переполниться.

Итак, вот два предложения:

1. Если у вас есть контроль над всем связанным кодом, найдите другой подход. Например, если у вас есть функция, которая принимает только int, но у вас есть поплавки, и вы хотите поместить свои поплавки в функцию, просто перепишите или перегрузите эту функцию, чтобы принять тоже плавает.
2. Если у вас нет контроля над той частью вашей системы, которая требует int, затем выберите точность, которая вам нужна, примите это вам просто иногда придется потерять некоторую информацию (но это будет всегда будьте в каком-то смысле "маленькими"), а потом просто умножьте все свои float на эту константу и округляется до ближайшего целого числа.

Кстати, если вы имеете дело с дробями, а не с числами с плавающей запятой, то это другая игра. Если у вас есть связка дробей a / b, c / d, e / f; и вам нужен наименьший общий множитель N такой, чтобы N * (каждая дробь) = целое число, тогда N = aбc / gcd (a, b, c); и gcd (a, b, c) = gcd (a, gcd (b, c)). Вы можете использовать Алгоритм Евклида, чтобы найти НОД любых двух чисел.

Итак, в основном вы хотите определить количество цифр после десятичной точки для каждого числа.

Было бы проще, если бы у вас было двоичное представление числа. Преобразовываются ли числа из рациональных или научных представлений ранее в вашей программе? Если это так, вы можете пропустить более раннее преобразование, и вам будет намного легче. В противном случае вы можете передать каждое число функции во внешней DLL, написанной на C, где вы могли бы напрямую работать с представлением с плавающей запятой. Или вы можете преобразовать числа в десятичные и поработать с Decimal.GetBits.

Самый быстрый подход, который я могу придумать на месте и следуя вашим условиям, - это найти наименьшую необходимую степень десяти (или 2, или что-то еще), как предлагалось ранее. Но вместо того, чтобы делать это в цикле, сэкономьте некоторые вычисления, выполнив двоичный поиск возможных степеней. Предполагая максимум 8, что-то вроде:

int NumDecimals( double d )
{
   // make d positive for clarity; it won't change the result
   if ( d<0 ) d=-d;

   // now do binary search on the possible numbers of post-decimal digits to 
   // determine the actual number as quickly as possible:

   if ( NeedsMore( d, 10e4 ) )
   {
      // more than 4 decimals
      if ( NeedsMore( d, 10e6 ) )
      {
          // > 6 decimal places
          if ( NeedsMore( d, 10e7 ) ) return 10e8;
          return 10e7;
      }
      else
      {
         // <= 6 decimal places
         if ( NeedsMore( d, 10e5 ) ) return 10e6;
         return 10e5;
      }
   }
   else
   {
      // <= 4 decimal places
      // etc...
   }

}

bool NeedsMore( double d, double e )
{
   // check whether the representation of D has more decimal points than the 
   // power of 10 represented in e.
   return (d*e - Math.Floor( d*e )) > 0;
}

PS: вы бы не передавали цены на ценные бумаги в систему ценообразования опционов, не так ли? У него именно аромат ...

1. Умножьте все числа на 10 пока у вас не будут целые числа.
2. Разделять на 2,3,5,7, пока у вас есть все целые числа.

Я думаю, это касается всех случаев.

2.1 * 10/7 -> 3
0.008 * 10^3/2^3 -> 1

Это при условии, что ваш множитель может быть рациональной дробью.