Алгоритм нахождения общего множителя для преобразования десятичных чисел в целые числа
Вопрос
У меня есть массив чисел, которые потенциально могут иметь до 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 знаков после запятой), а затем разделил бы на НОД полученных чисел.В итоге вы получите кучу наименьших целых чисел, которые можно передать другому алгоритму.После получения результата повторите процесс в обратном порядке, чтобы восстановить исходный диапазон.
Другие советы
- Умножьте все числа на 10 до тех пор, пока у вас не появятся целые числа.
- Делить на 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, а затем попытаетесь представить их в двоичном виде (иначе зачем вы так стараетесь сделать их целыми числами?), то вы потеряете практически всю информацию о других числах из-за переполниться.
Итак, вот два предложения:
- Если у вас есть контроль над всем связанным кодом, найдите другой подход.Например, если у вас есть какая-то функция, которая принимает только int, но у вас есть поплавки, и вы хотите запихнуть свои поплавки в функцию, просто перепишите или перегрузите эту функцию, чтобы принять также плавает.
- Если у вас нет контроля над той частью системы, которая требует 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;
}
ПС:вы бы не передавали цены ценных бумаг в механизм ценообразования опционов, не так ли?У него именно тот вкус...