寻找将十进制数转换为整数的通用乘数的算法-解网

问：

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

目前，我们对数字进行了一些检查，然后乘以 100 或 1,000,000，但是在处理大量数字时，*密封系统完成的处理可能会变得非常昂贵，因此仅仅为了它而将所有内容乘以 100 万并不是一个好的选择。作为一个近似值，假设密封算法每乘以 10 倍，成本就会增加 10 倍。

什么是最有效的算法，它也将提供最好的结果，以完成我需要的东西，是否有我需要的数学名称和/或公式？

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

到目前为止，有一些很好的答案，我想知道我应该如何选择“正确”的答案。一开始，我认为唯一公平的方法是创建每个解决方案并对其进行性能测试，但后来我意识到，纯粹的速度并不是唯一的相关因素——更准确的解决方案也非常重要。无论如何，我都写了性能测试，但目前我正在使用“直觉”公式根据速度和准确性选择正确答案。

我的性能测试处理 1000 组不同的 100 个随机生成的数字。每个算法都使用同一组随机数进行测试。算法是用 .Net 3.5 编写的（尽管到目前为止与 2.0 兼容）我非常努力地使测试尽可能公平。

格雷格 – 乘以大数然后除以 GCD – 63 毫秒
Andy – 字符串解析 – 199 毫秒
Eric – Decimal.GetBits – 160 毫秒
埃里克 – 二进制搜索 – 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-good-the-bad-and-the-ugly-inbar-gazit-matthew-greig.aspx 但每次我读到那篇文章时，我的眼睛都会一直呆滞，最终我没有时间尝试实现解决方案。

如果有人能想到更好的方法，我总是对其他解决方案持开放态度。

算法数学

Evil Andy：我是用 .Net 编程的，你提出的解决方案几乎与我们现在所做的相匹配。我不想把它包含在我最初的问题中，因为我希望有一些跳出框框（或者无论如何我的框框）思考，我不想用潜在的解决方案玷污人们的答案。虽然我没有任何可靠的性能统计数据（因为我没有任何其他方法可以与之进行比较），但我知道字符串解析会相对昂贵，我认为纯数学解决方案可能会更有效。公平地说，当前的字符串解析解决方案正在生产中，并且还没有关于其性能的投诉（它甚至在 VB6 格式的单独系统中投入生产，也没有投诉）。只是感觉不对劲，我想它冒犯了我的编程敏感性——但它很可能是最好的解决方案。

也就是说，我仍然对任何其他解决方案持开放态度，无论是纯粹的数学解决方案还是其他解决方案。

在一个循环中，将每个数字的尾数和指数作为整数。您可以将 frexp 用于指数，但我认为尾数需要位掩码。求最小指数。在尾数中查找最高有效数字（遍历位，寻找最后一个“1”） - 或者简单地使用预定义数量的有效数字。您的倍数类似于 2^（numberOfDigits-minMantissa）。“类似的东西”，因为我不记得偏差/偏移/范围，但我认为想法已经足够清晰了。

1赞 Tyler 9/12/2008 #5

如果你想找到一些整数 N，使 N*x 也是一组浮点数的精确整数，给定集合中的 x 都是整数，那么你就有一个基本上无法解决的问题。假设 x = 您的类型可以表示的最小正浮点数，假设它是 10^-30。如果你把所有的数字乘以 10^30，然后尝试用二进制表示它们（否则，你为什么还要这么努力地让它们变成整数？），那么由于溢出，你基本上会丢失其他数字的所有信息。

所以这里有两个建议：

如果您可以控制所有相关代码，请查找另一个方法。例如，如果您有一些函数只需要 int，但是你有浮点数，你想把你的浮点数塞进去函数，只需重写或重载此函数即可接受也会漂浮。
如果您无法控制系统中需要的部分 int，然后选择一个你关心的精度，接受它有时您只需要丢失一些信息（但它会在某种意义上总是“小”），然后乘以你所有的 float 的常数，并四舍五入到最接近的整数。

顺便说一句，如果你处理的是分数，而不是浮点数，那么这是一个不同的游戏。如果你有一堆分数 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。

0赞 Eric 9/13/2008 #6

所以基本上你要确定每个数字的小数点后位数。

如果您有数字的二进制表示形式，这将会更容易。这些数字是在程序的早期从有理数还是科学记数法转换而来的？如果是这样，您可以跳过较早的转换并享受更轻松的时间。否则，您可能希望将每个数字传递给用 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：你不会把证券价格传递给期权定价引擎吧？它的味道完全不同......

1赞 Douglas Leeder 9/13/2008 #7

将所有数字乘以 10 直到你有整数。
分通过 2,3,5,7，而你仍然拥有所有整数。

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

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

这是假设你的乘数可以是一个有理分数。

寻找将十进制数转换为整数的通用乘数的算法

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

评论

评论

评论