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

Question

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.

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?

*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.

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 – 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.

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.

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.

Answer 1

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.

Answer 2

1. Multiple all the numbers by 10 until you have integers.
2. Divide by 2,3,5,7 while you still have all integers.

I think that covers all cases.

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

That's assuming your multiplier can be a rational fraction.