首页 / 知识

关于数学：找到通用乘法器以将十进制数转换为整数的算法

2023-04-15 02:19:00

Algorithm to find a common multiplier to convert decimal numbers to whole numbers

我有一个数字数组，可能最多有8个小数位，我需要找到最小的公用数字，然后将它们相乘，以便它们都是整数。我需要这样做，以便所有原始数字都可以乘以相同的比例，并由仅处理整数的密封系统处理，然后我可以检索结果并将其除以公共乘数以得到我的相对结果。

目前，我们对数字进行了一些检查，然后乘以100或1,000,000，但是*密封系统完成的处理在处理大数时可能会变得非常昂贵，因此仅将数字乘以一百万并不是真正的事情。一个很好的选择。可以近似地说，每次乘以10的倍数时，密封算法的成本将增加10倍。

什么是最有效的算法，它还能给出最好的结果，从而完成我需要的工作，是否有数学名称和/或公式满足我的需要？

*密封系统不是真正密封的。我拥有/维护它的源代码，但是它有100,000行奇数行的专有魔术，并且已经过全面的错误和性能测试，出于多种原因，不建议对其进行更改以处理浮点数。它是一个系统，它创建一个由X个Y单元格组成的网格，然后将按X个Y单元格排列的矩形放入网格中，"专有魔术"出现并且结果被吐出来-显然，这是现实的极其简化的版本，但这是一个足够好的近似值。

到目前为止，这里有一些不错的答案，我想知道应该如何选择"正确的"答案。首先，我认为唯一公平的方法是创建每个解决方案并对其进行性能测试，但后来我意识到纯速度并不是唯一的相关因素–更精确的解决方案也非常重要。无论如何，我都编写了性能测试，但是目前，我正在基于速度和准确性来选择正确的答案，并使用"直觉"公式。

我的性能测试处理了1000套随机生成的100个数字的不同集合。
每种算法均使用相同的随机数集进行测试。
算法是用.Net 3.5编写的(尽管到目前为止是2.0兼容的)
我尽力使测试尽可能公平。

格雷格–乘以大
然后除以GCD – 63
毫秒
安迪–字符串解析
– 199毫秒
Eric – Decimal.GetBits – 160毫秒
Eric –二进制搜索– 32
毫秒
伊玛–对不起，我不能
弄清楚如何实施您的
.Net中轻松解决方案(我没有
想要花太长时间)
比尔–我想你的答案很漂亮
接近Greg，所以没有实施
它。我敢肯定这会更快
但可能准确性较低。

因此，格雷格的乘以大数然后除以GCD的方法是第二快的算法，它给出了最准确的结果，所以现在我称之为正确。

我确实希望Decimal.GetBits解决方案是最快的，但是它非常慢，我不确定这是由于Double转换为Decimal还是Bit进行了掩码和移位。应该有一个
使用BitConverter.GetBytes进行直接Double的类似可用解决方案，以及此处包含的一些知识：http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-types-the-好坏的丑陋的inbar-gazit-matthew-greig.aspx，但是每次阅读该文章时，我的眼睛都一直呆呆，最终我用光了时间来尝试实现解决方案。

如果有人能想到更好的解决方案，我将随时欢迎其他解决方案。

我乘以足够大的值(100,000,000个8位小数)，然后除以所得数字的GCD。您将得到一堆最小的整数，您可以将它们馈入另一种算法。得到结果后，请反向进行操作以恢复原始范围。

所有数字乘以10
直到你有整数。

划分
到2、3、5、7的时候
整数。

我认为这涵盖了所有情况。

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

假设您的乘数可以是有理数。

如果要找到某个整数N，以便N * x也是给定集合中所有浮点x的精确整数，则所有整数都是整数，那么您将遇到一个基本无法解决的问题。假设x =您的类型可以代表的最小正浮点数，例如10 ^ -30。如果将所有数字乘以10 ^ 30，然后尝试用二进制表示它们(否则，为什么还要努力使它们成为整数？)，则基本上所有其他数字的信息都将丢失溢出。

因此，这里有两个建议：

如果您可以控制所有相关代码，请查找另一个
方法。例如，如果您有一些仅需要
int，但是您有浮点数，并且您想将浮点数塞入
该函数，只需重写或重载此函数即可接受
浮动。

如果您无法控制需要的系统部分
整数，然后选择您要关注的精度，接受
您有时有时只会丢失一些信息(但是
在某种意义上总是"小")，然后乘以所有
以该常量为单位进行浮点运算，然后四舍五入到最接近的整数。

顺便说一句，如果您要处理分数，而不是浮点数，那是另一回事。如果您有一堆分数a / b，c / d，e / f；并且您想要一个最小公倍数N，使得N *(每个分数)=整数，则N = abc / gcd(a，b，c);和gcd(a，b，c)= gcd(a，gcd(b，c))。您可以使用Euclid算法查找任意两个数字的gcd。

因此，基本上，您想确定每个数字小数点后的位数。

如果您使用数字的二进制表示形式，这将更加容易。这些数字是在程序的早期从理性或科学符号转换而来的吗？如果是这样，您可以跳过较早的转换并获得更轻松的时间。否则，您可能希望将每个数字传递给用C编写的外部DLL中的函数，您可以在其中直接使用浮点表示形式。或者，您可以将数字转换为十进制，然后对Decimal.GetBits进行一些处理。

我能想到的并随您所处条件而定的最快方法就是找到以前建议的最小必要的十进制幂(或2，或其他任意值)。但是，与其循环执行，不如通过对可能的功率进行二进制搜索来节省一些计算。假设最大为8，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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：您不会将证券价格传递给期权定价引擎吗？确实有味道...

循环获取每个数字的尾数和指数作为整数。您可以将frexp用于指数，但我认为尾数将需要位掩码。查找最小指数。查找尾数中的最高有效数字(循环查找最后的" 1"的位)-或仅使用预定义数量的有效数字。
那么您的倍数就是2 ^(numberOfDigits-minMantissa)。"有点像"，因为我不记得有偏差/偏移/范围，但我认为想法很明确。

格雷格：不错的解决方案，但是不会计算100个以上的数字中常见的GCD会有点贵吗？您将如何处理？对两个数字进行GCD很容易，但是对100来说，它变得更加复杂(我认为)。

邪恶的安迪(Evil Andy)：我正在使用.Net编程，您提出的解决方案几乎可以满足我们现在所做的一切。我不想将其包含在我的原始问题中，因为我希望开箱即用(或无论如何要在框内)进行思考，并且我不想用可能的解决方案来污染人们的答案。尽管我没有任何可靠的性能统计信息(因为我没有任何其他方法可以将其与之进行比较)，但我知道字符串解析相对昂贵，而且我认为纯数学解决方案可能会更高效。
公平地讲，当前的字符串解析解决方案已投入生产，并且尚未对其性能提出任何抱怨(即使是在单独的VB6格式系统中也没有抱怨)。只是感觉不对，我猜它冒犯了我的编程敏感性-但这可能是最好的解决方案。

也就是说，我仍然可以接受任何其他解决方案，无论是数学上还是其他方面。

您用什么语言编程？就像是