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

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

什么是最有效的算法，它还能给出最佳的结果，以完成我需要的操作，是否有Im的数学名称和/或者公式？

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

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

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

• 格雷格乘以大，然后除以GCD 63毫秒
• Andy String解析199毫秒
• Eric Decimal.GetBits 160毫秒
• Eric Binary搜索32毫秒
• 抱歉，我无法弄清楚如何在.Net中轻松实现解决方案(我不想花太多时间在它上面)
• 比尔我认为答案与格雷格斯非常接近，所以没有执行它。我相信它会更快，但准确性可能会降低。

因此，格雷格斯乘以大数然后除以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得出的数字。我们将得到一堆最小的整数，我们可以将它们输入其他算法。得到结果后，请反向进行操作以恢复原始范围。

回答

我们正在使用哪种语言编程？就像是

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

将为我们提供C＃中双精度的小数位数。我们可以对每个数字进行运算，找到最大的小数位数(x)，然后将每个数字乘以10乘以x的幂。

编辑：出于好奇，我们只能将整数传递给它的密封系统是什么？

回答

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

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

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

回答

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

回答

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

因此，这里有两个建议：

• 如果我们可以控制所有相关代码，请寻找另一种方法。例如，如果我们有一些仅使用int的函数，但是我们有浮点数，并且想要将浮点数填充到该函数中，则只需重写或者重载此函数以接受浮点数即可。
• 如果我们无法控制系统中需要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，例如：

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：我们不会将证券价格传递给期权定价引擎吗？恰到好处的味道...

回答

• 将所有数字乘以10，直到得到整数。
• 除以2,3,5,7即可得到所有整数。

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

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

假设乘数可以是有理数。