4

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

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

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

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

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

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

  • Greg – 乘以大数然后除以 GCD – 63 毫秒
  • Andy – 字符串解析 – 199 毫秒
  • Eric – Decimal.GetBits – 160 毫秒
  • Eric – 二进制搜索 – 32 毫秒
  • Ima - 抱歉，我无法弄清楚如何在 .Net 中轻松实现您的解决方案（我不想花太长时间在上面）
  • 比尔——我认为你的答案与格雷格的很接近，所以没有实施。我敢肯定它会更快，但可能不太准确。

所以 Greg 的乘以大数然后除以 GCD”解决方案是第二快的算法，它给出了最准确的结果，所以现在我称之为正确的。

我真的希望 Decimal.GetBits 解决方案是最快的，但它非常慢，我不确定这是由于将 Double 转换为 Decimal 还是由于 Bit 掩码和移位。使用 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但每次我读到那篇文章时，我的眼睛一直在发呆，最终我没时间尝试实现一个解决方案。

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

4

7 回答 7

6

我会乘以足够大的值（100,000,000 小数点后 8 位），然后除以结果数字的GCD。你最终会得到一堆最小的整数，你可以将它们提供给其他算法。得到结果后，反转过程以恢复您的原始范围。

于 2008-09-12T08:21:43.077 回答
1

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

所以这里有两个建议：

  1. 如果您可以控制所有相关代码，请找到另一种方法。例如，如果你有一些只接受 int 的函数，但你有浮点数，并且你想将你的浮点数填充到函数中，只需重写或重载这个函数以接受浮点数。
  2. 如果您无法控制需要 int 的系统部分，则选择您关心的精度，接受有时您将不得不丢失一些信息（但在某种意义上它总是“小” )，然后将所有浮点数乘以该常数，然后四舍五入到最接近的整数。

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

于 2008-09-12T11:19:02.137 回答
1
  1. 将所有数字乘以 10，直到得到整数。
  2. 除以 2,3,5,7，而您仍然拥有所有整数。

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

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

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

于 2008-09-12T23:01:05.710 回答
0

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

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

将为您提供 C# 中双精度的小数位数。您可以通过它运行每个数字并找到最大的小数位数（x），然后将每个数字乘以 10 的 x 次方。

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

于 2008-09-12T08:36:29.360 回答
0

Greg：很好的解决方案，但是计算一个包含 100 多个数字的数组中常见的 GCD 会不会有点贵？你会怎么做呢？对两个数字进行 GCD 很容易，但对于 100，它变得更加复杂（我认为）。

邪恶的安迪：我正在.Net 中编程，你提出的解决方案与我们现在所做的非常匹配。我不想将它包含在我最初的问题中，因为我希望有一些跳出框框（或无论如何是我的框框）的想法，并且我不想用潜在的解决方案来污染人们的答案。虽然我没有任何可靠的性能统计数据（因为我没有任何其他方法可以比较它），但我知道字符串解析会相对昂贵，而且我认为纯数学解决方案可能更有效。公平地说，当前的字符串解析解决方案正在生产中，并且还没有关于它的性能的投诉（它甚至在一个单独的 VB6 格式的系统中生产，也没有任何投诉）。就是感觉不太对劲

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

于 2008-09-12T09:03:59.093 回答
0

在循环中获取每个数字的尾数和指数作为整数。您可以将 frexp 用于指数，但我认为尾数需要位掩码。找到最小指数。在尾数中查找最高有效数字（循环查找最后一个“1”） - 或简单地使用预定义的有效数字数。你的倍数就像 2^(numberOfDigits-minMantissa)。“类似”是因为我不记得偏差/偏移量/范围，但我认为这个想法很清楚。

于 2008-09-12T10:47:54.117 回答
0

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

如果你有数字的二进制表示，这会更容易。在你的程序中，数字是从有理数还是科学记数法转换而来的？如果是这样，您可以跳过较早的转换并轻松得多。否则，您可能希望将每个数字传递给用 C 编写的外部 DLL 中的函数，您可以在其中直接使用浮点表示。或者您可以将数字转换为十进制并使用Decimal.GetBits做一些工作。

我能想到的最快的方法是按照你的条件找到最小的必要的 10 次方（或 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：您不会将证券价格传递给期权定价引擎吗？它的味道完全...

于 2008-09-12T22:26:20.753 回答