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.

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.

What language are you programming in? Something like

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

would give you the number of decimal places for a double in C#. You could run each number through that and find the largest number of decimal places(x), then multiply each number by 10 to the power of x.

Edit: Out of curiosity, what is this sealed system which you can pass only integers to?

Greg: Nice solution but won't calculating a GCD that's common in an array of 100+ numbers get a bit expensive? And how would you go about that? Its easy to do GCD for two numbers but for 100 it becomes more complex (I think).

Evil Andy: I'm programing in .Net and the solution you pose is pretty much a match for what we do now. I didn't want to include it in my original question cause I was hoping for some outside the box (or my box anyway) thinking and I didn't want to taint peoples answers with a potential solution. While I don't have any solid performance statistics (because I haven't had any other method to compare it against) I know the string parsing would be relatively expensive and I figured a purely mathematical solution could potentially be more efficient. To be fair the current string parsing solution is in production and there have been no complaints about its performance yet (its even in production in a separate system in a VB6 format and no complaints there either). It's just that it doesn't feel right, I guess it offends my programing sensibilities - but it may well be the best solution.

That said I'm still open to any other solutions, purely mathematical or otherwise.

In a loop get mantissa and exponent of each number as integers. You can use frexp for exponent, but I think bit mask will be required for mantissa. Find minimal exponent. Find most significant digits in mantissa (loop through bits looking for last "1") - or simply use predefined number of significant digits. Your multiple is then something like 2^(numberOfDigits-minMantissa). "Something like" because I don't remember biases/offsets/ranges, but I think idea is clear enough.

If you want to find some integer N so that N*x is also an exact integer for a set of floats x in a given set are all integers, then you have a basically unsolvable problem. Suppose x = the smallest positive float your type can represent, say it's 10^-30. If you multiply all your numbers by 10^30, and then try to represent them in binary (otherwise, why are you even trying so hard to make them ints?), then you'll lose basically all the information of the other numbers due to overflow.

So here are two suggestions:

- If you have control over all the related code, find another approach. For example, if you have some function that takes only int's, but you have floats, and you want to stuff your floats into the function, just re-write or overload this function to accept floats as well.
- If you don't have control over the part of your system that requires int's, then choose a precision to which you care about, accept that you will simply have to lose some information sometimes (but it will always be "small" in some sense), and then just multiply all your float's by that constant, and round to the nearest integer.

By the way, if you're dealing with fractions, rather than float's, then it's a different game. If you have a bunch of fractions a/b, c/d, e/f; and you want a least common multiplier N such that N*(each fraction) = an integer, then N = a*b*c / gcd(a,b,c); and gcd(a,b,c) = gcd(a, gcd(b, c)). You can use Euclid's algorithm to find the gcd of any two numbers.

So basically you want to determine the number of digits after the decimal point for each number.

This would be rather easier if you had the binary representation of the number. Are the numbers being converted from rationals or scientific notation earlier in your program? If so, you could skip the earlier conversion and have a much easier time. Otherwise you might want to pass each number to a function in an external DLL written in C, where you could work with the floating point representation directly. Or you could cast the numbers to decimal and do some work with Decimal.GetBits.

The fastest approach I can think of in-place and following your conditions would be to find the smallest necessary power-of-ten (or 2, or whatever) as suggested before. But instead of doing it in a loop, save some computation by doing binary search on the possible powers. Assuming a maximum of 8, something like:

```
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: you wouldn't be passing security prices to an option pricing engine would you? It has exactly the flavor...

- Multiple all the numbers by 10 until you have integers.
- 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.

Similar Questions

Is there a slick way to convert simple numbers (Army time included) to a time format (am, pm format)? I can do the tedious approach, but I was just wondering if there was another way 0800 => 8:00 a

I'm trying to write the Cooley Tukey algorithm for an FFT. Now, The algorithm works well, but, only for 2 numbers - Nothing else. For example, I have used an online FFT calculated, entered the same da

I'm trying to write an algorithm for finding out the number of ways n numbers can be ordered. For example, two number say a and b can be ordered in 3 ways.. Similarly, 3 numbers can be arranged in 13

This question already has an answer here: JavaScript numbers to Words 10 answers How can I use Javascript for converting numbers to words? The display requires Indian rupees and paise format.

Hi I'm working on an assignment and got stuck on this part, how do I validate decimal numbers/numbers in shell? It can accept numbers but not decimal numbers. I want it to be able to accept both. This

I've 2 list a = [1,9] # signifies the start point and end point, ie numbers 1,2,3,4,5,6,7,8,9 b = [4,23] # same for this. Now I need to find whether the numbers from a intersect with numbers from b.

What are the most common/useful SqlException numbers? I don't need the entire sysmessages table, just the typical or common errors you're likely to see in a data access layer so I can do sometihng lik

Suppose I have an array of non-repeating decimal numbers: v1 = 0.0588235294117647, 0.1428571428571429, 0.0526315789473684, 0.0769230769230769 I would like to convert this to an array of integers by m

My return result from my database looks like : a = [Decimal('0.4441'), Decimal('0.3821'), Decimal('0.4414'), Decimal('0.3391')] How can I convert it to : a = [0.4441, 0.3821, 0.4414, 0.3391]

Possible Duplicate: Parsing numbers safely and locale-sensitively How can I validate strings containing decimal numbers in a locale-sensitive way? NumberFormat.parse allows too much, and Double.pars

I am using Birt with Eclipse Indigo. I am using a table in the report. The table will get values from the dataset. I want to convert the numbers to Persian numbers. I tried using java script but it do

I want to be able to enter decimal numbers into a play form. I would like to have the following mapping, but it does not compile. mapping( id -> ignored(NotAssigned:Pk[Long]), date -> date(

This question already has an answer here: Python rounding error with float numbers 2 answers Python weird addition bug [duplicate] 4 answers I'm trying to add decimal numbers a decimal numb

I want to display a number in a report, however I only want to show any decimal points if they are present and the I only want to show 1 decimal space. e.g. if the number is 12 then I want to show 12

There is an array of size n (numbers are between 0 and n - 3) and only 2 numbers are repeated. Elements are placed randomly in the array. E.g. in {2, 3, 6, 1, 5, 4, 0, 3, 5} n=9, and repeated numbers

I have a Recordset obtained by the following query: SELECT DISTINCT [Number] FROM NUMBERS WHERE CODE = 7 ORDER BY [Number] The Recordset will therefore be a list of ordered numbers, eg. [6,14,37,59,8

When rounding up to 2 decimal places, the value 4.01132141 would be rounded to 4.02 because it exceeds 4.01. How can you do this in PL/SQL?

I was wondering if there is an efficient premade algorithm for determining if the sum/difference of a group of numbers can equal a different number. Example: 5, 8, 10, 2, using + or -, to equal 9. 5 -

In R, there is a great function as.roman in the very base setup: as.roman(79) # [1] LXXIX Is there an inverse function that would convert roman numerals to numbers? (I know I can write it myself but

Is booth algorithm for multiplication only for multiplying 2 negative numbers (-3 * -4) or one positive and one negative number (-3 * 4) ? Whenever i multiply 2 positive numbers using booth algorithm

Using JSONObject to read a json response from a server. The server returns some decimal number. Normal numbers are not a problem to but the problem occurs when there is decimal number of form 0.00068.

Is possible to subtract roman numbers without conversion to decimal numbers? For Example: X - III = VII So in input I have X and III. In output I have VII. I need algorithm without conversion to decim

How to convert numbers to words in ruby? I know there is a gem somewhere. Trying to implement it without a gem. I just need the numbers to words in English for integers. Found this but it is very mess

Hi I'm new at programming and Im trying to learn Python. Im trying to make a program that converts numbers into the word for the number. Ex 15 would be fifteen. In the moment Im making a small func

Is there a nice way to show show decimal numbers with one decimal place all the time but without rounding? So you have the following numbers: 3.55 3.5 3 and I want them to show 3.5 3.5 3.0

This question already has an answer here: JavaScript displaying a float to 2 decimal places 3 answers So I made this quick script that calculates some numbers, but the answer ends with many dec

I have a question about running time of an algorithm that express the product of n numbers.. I think the best solution is divide and conquer which is based on halving the n element by 2 recursively an

The following is my java code Pattern p = Pattern.compile(-?\\d*\\.?\\d*); Matcher m = p.matcher(the numbers are -3.4 and 132); while (m.find()) { System.out.println(m.group()); } But it fails to

I just want to know how can I can convert the numbers 1, 2 or 3 into First, second or Third ? Any help would be appreciated.

I have been trying to write a Lex program to convert octal numbers to decimal numbers. But after accepting the number as input, but not doing anything. No output. And no program termination. The progr

I am trying to get the total of my variables containing numbers, some may be decimals. I need this to be to two decimal places and am using the number_format() function. $total = $order->order->

Hi I have a table of characters that I am attempting to convert to numbers as so: vec1 <- c(B,D,E,NA) vec2 <- c(B,D,E,NA) vec3 <- c(B,C,E,NA) vec4 <- c(B,D,E,

I'm trying to round numbers derived from cmath's divide function to a whole number, the results often being negative due to the nature of the program. Example code: strength = input(Input Strength

I have mysql table and DBAdvGrid, decimal numbers of mysql column are shown like 950, 450, 555.45 I would like to be always shown 2 digits after point. like 950.00 I tried event of dataset 'AfterOpen'

I am trying to build a regex which will allow both negative and positive decimal numbers with the following rules. there can not be more than 2 digits after decimal point Decimal point is optional To

I use the data attribute to store strings and numbers in DOM nodes and read them with JavaScript. Unfortunately all values in the dataset are saved as string. So whats is the best way to convert them

I was curious about prime numbers and would like to know the most efficient way to find relatively small prime numbers for a range up to say, 10 million. I read that the sieve of erastosthenes (SOE) i

int array[] = {-1, 4, -2, 5, -5, 2, -20, 6}; If I had that array, my Kadane algorithm implementation to find the maximum subarray works: int max_so_far = INT_MIN; int max_ending_here = 0; for (int i

exist any way to store in database a numbers with or without decimal point? The user can store to database numbers like 10 and 10.1 - for storing numbers in MySQL I use data type column decimal, so fo

I'm writing a program in C# that will find all the prime numbers up to the max size of UInt64, unless there's a numerical data type larger than UInt64. I've already written the simple program but for

In PHP textfield: Prevent the user from entering more then 3 numbers before decimal point for example: if user enter 123.12 its acceptable, if user enter 12.12 its also acceptable, but if user enter 1

I am working on a procedure that retrieves the numbers from some elements that can be found in a select list. For example from test element (100) i am trying to get the number 100. I used this cod

Are there any string methods, that will let me convert a string of numbers, to string of numbers and letters? I am trying to create a page with a button. Once the button has been clicked it will chang

In a sequence of length n, where n=2k+3, that is there are k unique numbers appeared twice and three numbers appeared only once. The question is: how to find the three unique numbers that appeared on

I want to get the first one million prime numbers. I know the way of finding small prime numbers. My problem is, how can I store such large numbers in simple data types such as long, int, etc?

How can I convert all numbers that are more than 3 digits down to a 4 digit or less number? This is exactly what I mean: 10345 = 10.3k 10012 = 10k 123546 = 123.5k 4384324 = 4.3m Rounding is not entir

Is there any way to define an <input> that shows a keyboard input that only allows numbers and the decimal point (or comma for international users)? <input type='tel'> shows phone crap I d

Okay so, I have a column that looks something like this: 20140813000000000 It is displaying a date, in the format of decimal(17,0), but I need to take the first 8 characters out of it to convert it

I am making a JavaScript calculator,and it (suppose to) converts binary numbers (2) into octal numbers (8). I have done a research on this for a while, and what I found was a bunch of libraries. I don

To keep it simple lets say I have 3 whole numbers (integers) I know I can find the highest by using something like: if(num1 > num2 && num1 > num3) cout << num1 << endl; if(nu