我有一个数字数组,可能有多达8个小数位,我需要找到我可以乘以它们的最小公共数,以便它们都是整数.我需要这个所以所有的原始数字都可以乘以相同的比例并由一个只处理整数的密封系统处理,然后我可以检索结果并用公共乘数除以得到我的相对结果.
目前我们对这些数字进行了一些检查并乘以100或1,000,000,但是*密封系统完成的处理在处理大数字时可能会非常昂贵,因此为了它而将所有内容乘以一百万并不是真的一个很好的选择.可以说,每次乘以10倍时,密封算法的成本会高出10倍.
什么是最有效的算法,也将提供最好的结果,以实现我需要的东西,是否有我需要的数学名称和/或公式？
*密封系统没有真正密封.我拥有/维护它的源代码,但它的100,000个奇怪的专有魔法线,它已经彻底的bug和性能测试,改变它来处理浮动不是一个选项有很多原因.它是一个创建X×Y单元网格的系统,然后X by Y的网格被放入网格中,"专有魔法"发生并且结果被吐出 - 显然这是现实的极简化版本,但它是一个足够好的近似值.
到目前为止,有一些很好的答案,我想知道如何选择"正确"的答案.首先,我认为唯一公平的方法是创建每个解决方案并对其进行性能测试,但后来我意识到纯粹的速度并不是唯一的相关因素 - 更准确的解决方案也非常相关.无论如何我写了性能测试,但目前我正在使用"肠道感觉"公式,根据速度和准确度选择正确的答案.
我的性能测试处理了1000组不同的100个随机生成的数字.使用相同的随机数集测试每个算法.算法是用.Net 3.5编写的(虽然到目前为止兼容2.0)我努力使测试尽可能公平.
Greg - 乘以大数,然后除以GCD - 63毫秒
安迪 - 字符串解析 - 199毫秒
Eric - Decimal.GetBits - 160毫秒
Eric - 二进制搜索 - 32毫秒
对不起 - 抱歉,我无法弄清楚如何在.Net中轻松实现您的解决方案(我不想花太多时间)
比尔 - 我认为你的答案非常接近格雷格,所以没有实施.我确信它会更快,但可能不太准确.
所以格雷格乘以大数乘以然后除以GCD"解决方案是第二快算法,它给出了最准确的结果,所以现在我称之为正确.
我真的希望Decimal.GetBits解决方案是最快的,但它非常慢,我不确定这是由于Double转换为Decimal还是Bit掩码和转换.使用BitConverter.GetBytes和这里包含的一些知识应该有一个类似的可用解决方案:http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-类型 - 好 - 坏 - 丑陋 - inbar-gazit-matthew-greig.aspx但是每次我读这篇文章时我的眼睛都会不停地上釉,我最终没时间试图实现一个解.
如果有人能想到更好的东西,我总是愿意接受其他解决方案.
我会乘以足够大的东西(小数点后8位为100,000,000),然后除以结果数字的GCD.你最终会得到一堆最小的整数,你可以提供给另一个算法.获得结果后,请反转该过程以恢复原始范围.
京公网安备 11010802040832号 | 京ICP备19059560号-6 