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

StackOverflow https://stackoverflow.com/questions/58493

  •  09-06-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

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

Мне очень хотелось, чтобы решение Decimal.GetBits было самым быстрым, но оно было очень медленным, я не уверен, связано ли это с преобразованием Double в Decimal или с маскированием и сдвигом битов.Должен быть аналогичное полезное решение для прямого 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 но мои глаза просто тускнели каждый раз, когда я читал эту статью, и в конце концов у меня не хватило времени, чтобы попытаться реализовать решение.

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

Это было полезно?

Решение

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top