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

Question

У меня есть массив чисел, которые могут иметь до 8 десятичных знаков, и мне нужно найти наименьшее общее число, на которое я могу умножить их, чтобы они были целыми числами. Мне это нужно, чтобы все исходные числа можно было умножить до одного и того же масштаба и обработать в запечатанной системе, которая будет работать только с целыми числами, затем я могу получить результаты и разделить их на общий множитель, чтобы получить мои относительные результаты. .

В настоящее время мы делаем несколько проверок чисел и умножаем на 100 или 1 000 000, но обработка, выполняемая * запечатанной системой, может быть довольно дорогой при работе с большими числами, поэтому умножение всего на миллион просто ради Это действительно отличный вариант. В качестве приблизительного предположения скажем, что запечатанный алгоритм становится в 10 раз дороже каждый раз, когда вы умножаете в 10 раз.

Каков наиболее эффективный алгоритм, который также даст наилучший возможный результат для достижения того, что мне нужно, и есть ли математическое имя и / или формула для того, что мне нужно?

* Запечатанная система на самом деле не запечатана. Я владею / поддерживаю исходный код для него, но его 100 000 нечетных строк проприетарной магии, и он был тщательно проверен на наличие ошибок и производительности, и изменение его для работы с плавающими объектами не вариант по многим причинам. Это система, которая создает сетку из ячеек X по Y, затем в сетку сбрасываются тары, которые по X по Y, возникает «запатентованная магия» и результаты выплевываются - очевидно, это чрезвычайно упрощенная версия реальности, но это достаточно хорошее приближение.

Пока что есть несколько хороших ответов, и я подумал, как мне выбрать «правильный». Для начала я подумал, что единственный честный способ - это создать каждое решение и протестировать его, но позже я понял, что чистая скорость - не единственный важный фактор - более точное решение также очень важно. В любом случае, я написал тесты производительности, но в настоящее время я выбираю правильный ответ на основе скорости, а также точности, используя формулу «интуитивного ощущения».

Мои тесты производительности обрабатывают 1000 различных наборов из 100 случайно сгенерированных чисел. Каждый алгоритм проверяется с использованием одного и того же набора случайных чисел. Алгоритмы написаны на .Net 3.5 (хотя до сих пор совместим с 2.0) Я очень старался сделать тесты максимально честными.

• Грег - Умножить на большое число а затем разделить на GCD - 63 миллисекунды
• Энди - Разбор строк - 199 миллисекунд
• Эрик - Decimal.GetBits - 160 миллисекунд
• Eric - двоичный поиск - 32 миллисекунды
• Има - извините, я не мог выяснить, как реализовать свой решение легко в .Net (я не хочу потратить на это слишком долго)
• Билл - я полагаю, ваш ответ был довольно близко к Грегу, так что не реализовали Это. Я уверен, что это будет чуть-чуть быстрее но потенциально менее точный.

Таким образом, решение Грега «Умножить на большое число, а затем разделить на GCD» было вторым самым быстрым алгоритмом, и оно дало самые точные результаты, поэтому сейчас я называю его правильным.

Я действительно хотел, чтобы решение Decimal.GetBits было самым быстрым, но оно было очень медленным, я не уверен, связано ли это с преобразованием двойного в десятичное или битовое маскирование и сдвиг. Там должно быть похожее пригодное для использования решение для простого Double с использованием BitConverter.GetBytes и некоторыми знаниями, содержащимися здесь: http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew-greig.aspx, но мои глаза просто продолжали стекаться каждый раз, когда я читал эту статью, и у меня, в конце концов, не хватало времени, чтобы попытаться реализовать решение .

Я всегда открыт для других решений, если кто-то может придумать что-то лучше.

Answer 1

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

Answer 2

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

Я думаю, что охватывает все случаи.

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

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

Answer 3

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

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

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

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

Answer 4

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

Это было бы намного проще, если бы у вас было двоичное представление числа. Числа, преобразованные из рациональных или научных обозначений ранее в вашей программе? Если это так, вы можете пропустить более раннее преобразование и вам будет намного проще. В противном случае вы можете захотеть передать каждое число в функцию во внешней 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: вы бы не передавали цены на ценообразование в систему оценки опционов? У этого есть точно аромат ...

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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

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

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