查找公用乘数以将十进制数转换为整数的算法 [英] Algorithm to find a common multiplier to convert decimal numbers to whole numbers

问题描述

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

I have an array of numbers that potentially have up to 8 decimal places and I need to find the smallest common number I can multiply them by so that they are all whole numbers. I need this so all the original numbers can all be multiplied out to the same scale and be processed by a sealed system that will only deal with whole numbers, then I can retrieve the results and divide them by the common multiplier to get my relative results.

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

Currently we do a few checks on the numbers and multiply by 100 or 1,000,000, but the processing done by the *sealed system can get quite expensive when dealing with large numbers so multiplying everything by a million just for the sake of it isn’t really a great option. As an approximation lets say that the sealed algorithm gets 10 times more expensive every time you multiply by a factor of 10.

最有效的算法是什么，它还能给出最好的结果，从而完成我需要的东西，并且为我需要的东西提供数学名称和/或公式?

What is the most efficient algorithm, that will also give the best possible result, to accomplish what I need and is there a mathematical name and/or formula for what I’m need?

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

*The sealed system isn’t really sealed. I own/maintain the source code for it but its 100,000 odd lines of proprietary magic and it has been thoroughly bug and performance tested, altering it to deal with floats is not an option for many reasons. It is a system that creates a grid of X by Y cells, then rects that are X by Y are dropped into the grid, "proprietary magic" occurs and results are spat out – obviously this is an extremely simplified version of reality, but it’s a good enough approximation.

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

So far there are quiet a few good answers and I wondered how I should go about choosing the ‘correct’ one. To begin with I figured the only fair way was to create each solution and performance test it, but I later realised that pure speed wasn’t the only relevant factor – an more accurate solution is also very relevant. I wrote the performance tests anyway, but currently the I’m choosing the correct answer based on speed as well accuracy using a ‘gut feel’ formula.

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

My performance tests process 1000 different sets of 100 randomly generated numbers. Each algorithm is tested using the same set of random numbers. Algorithms are written in .Net 3.5 (although thus far would be 2.0 compatible) I tried pretty hard to make the tests as fair as possible.

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

• Greg – Multiply by large number and then divide by GCD – 63 milliseconds
• Andy – String Parsing – 199 milliseconds
• Eric – Decimal.GetBits – 160 milliseconds
• Eric – Binary search – 32 milliseconds
• Ima – sorry I couldn’t figure out a how to implement your solution easily in .Net (I didn’t want to spend too long on it)
• Bill – I figure your answer was pretty close to Greg’s so didn’t implement it. I’m sure it’d be a smidge faster but potentially less accurate.

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

So Greg’s Multiply by large number and then divide by GCD" solution was the second fastest algorithm and it gave the most accurate results so for now I’m calling it correct.

我真的希望Decimal.GetBits解决方案最快，但速度非常慢，我不确定这是由于Double转换为Decimal还是Bit进行了掩码和移位.应该有一个 使用BitConverter.GetBytes进行直接Double的类似可用解决方案，以及此处包含的一些知识:

I really wanted the Decimal.GetBits solution to be the fastest, but it was very slow, I’m unsure if this is due to the conversion of a Double to a Decimal or the Bit masking and shifting. There should be a similar usable solution for a straight Double using the BitConverter.GetBytes and some knowledge contained here: 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 but my eyes just kept glazing over every time I read that article and I eventually ran out of time to try to implement a solution.

如果有人能想到更好的方法，我总是愿意接受其他解决方案.

I’m always open to other solutions if anyone can think of something better.

推荐答案

我将乘以足够大的值(100,000,000个8位小数)，然后除以

I'd multiply by something sufficiently large (100,000,000 for 8 decimal places), then divide by the GCD of the resulting numbers. You'll end up with a pile of smallest integers that you can feed to the other algorithm. After getting the result, reverse the process to recover your original range.

这篇关于查找公用乘数以将十进制数转换为整数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！