How do I calculate the smallest integer required to multiply a set of decimal fractions into a set of integers?

Is there a simple formula, algorithm or Excel function to do this?

Could you just multiply all of the fractions by their least common multiple?

Here is the excell command

I don't think so, as that can produce more fractions.

Also, Excel's LCM function only works with integer input values, not fractions.

I think you can do it in the following way: if your fractions are x1/y1, x2/y2, ..., xy/yn, with gcd(xi, yi) = 1, then the smallest such integer is the lcm of y1, y2,..,yn.

Hi Tom, sounds good but I only have decimal fractions, not the numerators and denominators. Perhaps there is a way to multiply the fractions and figure out the answer from the decimal portion?

For example, given the set of simple decimal fractions:

0.3333333', 0.6, 0.5, 0.75, 1.25, 1.5, 1.666666'

The smallest integer required to multiply all these fractions into integers is:

2x2x3x5 = 60

But I need a functuon that will calculate this for a bigger set of more complex and less recognisable fractions...

Turn 1.234 into 1234/1000 as 4.5678 into 45678/10000, etc.

Then reduce each fraction (cancel common prime factors) and then compute the LCM of the denominators. If you've already found the prime factors for the denominators the LCM is trivial.

The problem with that approach is it doesn't work for recurring fractions like 0.3333333'.

Do you ever actually have repeating decimals? That is, is your input "0.333333333333"? Or does it actually have the notation saying the 3 is repeating?

The input "0.333333333333" is 333333333333/1000000000000

The input "0.(3-bar)" is 3/9
The input 0.(03-bar) is 3/99
The input 0.(abcd...-bar) is abcd.../9999...

The same is true if the repeating portion doesn't rest against the decimal. Just pad with zeros.
So if the input is 1.23(4-bar) the fraction is 123/100 + 4/900 which is 1111 / 900

If somebody doesn't explicitly tell you what decimal is repeating then not decimal is repeating and you don't have to worry about it. If it does have a repeating decimal, the conversion of that to a fraction is trivial.

If your number has a periodic decimal expansion then you can do the following:
x = 0.abcdabcdabcd...
abcd = 1000x - x
x = abcd/9999
Now you have expressed x as a fraction and you can use the aforementioned trick to find that integer.

If your fraction is of the form y.abcdabcabcd... then of course you can represent it as (abcd + 9999y)/9999.
A case like y.xabcdabcd is a little bit trickier, but the general approach is the same.

If the decimal expansion does not eventually turn periodic then the number is not rational so such an integer does not exist.

I'm using Excel, which somehow manages to calculate 1/3 * 3 as an integer, even though it calculates via a decimal fraction.

I'm not familiar with Excel however I see a few possibilities:

1) Excel calculated 1/3 to many more decimal places than it will actually display to you. Then when you multiply that by 3 it gets 1.000000000000000000.... and because it will only show you the first N significant digits it just shows you 1.

2) If you have a cell with 1 and a cell with 3 and you make another cell13 = cell1 / cell3 and then another cell = cell13 * 3, Excel may trace cell13 back to the original data sources that were used to create the value and re-evaluate from the sources. Then Excel would be doing (1/3) * 3 and it could use a CAS to determine the result is 1 without computing the intermediate step.

3) It may be that Excel stores numbers as rationals wherever possible so 1/3 is stored as 1/3 rather than 0.33333333333333. Only when it displays the values to the user does it perform an expansion. Rationals are a very common data type for programs that handle money.


EDIT: I realized you can check for display roundoff (possibility 1) by using irrational numbers. Just compute sqrt(sqrt(sqrt(...sqrt(2)))) over and over. If no mater how many times you do it you get 1.000000000000000000000000 rather than 1 then there is no display roundoff. If you eventually do get 1 then try squaring the 1. If you square it several times and it turns back into 1.000000000000000000 then excel has more internal precision than display precision. This test assumes Excel isn't doing possibility 2 which would defeat the test.

I suspect it calculates to 17dp and then rounds the answer to 16dp, or something like that.

Since when were you American?

Re: excel rounding:

If you put 1.00000000000001 into a cell, it will correctly store "1.00000000000001", and display as much of that decimal as the cell is formatted to display. However, add more more zero in the formula bar, and as soon as you leave the cell, changes the value of the cell to "1", regardless of formatting. I guess I could have just googled the fact that Excel has a 15 digit working precision, but experimenting was more fun.

Just British with bad spelling.

Any idea how Excel handles numbers like 0.1 ? .1 can not be represented exactly in base-2 floating point. Since Excel works with money it needs to be able to do exact comparisons and not worry about these things.

So what does Excel say about the equality of 0.1 and 1/10 and 2/20 and (0.2 / 2) and (0.05 * 2), etc.? If it can compare these values as equal either there is a fudge-factor on equality or it has a reciprocal data type internally.

Exel considers all those numbers exactly equal, but I don't believe there is any reciprocal data type, it just seems to calculate and round numbers to a limited number of significant figures.

This is pretty scary. Floating-point numbers have horrible quirks that you'd never want to expose to the user. Adding a fudge-factor hides most of those problems but makes other things subtly wrong (which could be even worse).

I would have expected Microsoft to build a CAS into Excel and use reciprocal data types so that almost all calculations are exact.

What does Excel say about something like (2 - (sqrt(2)^2)) * 10^20 ? A CAS knows the exact value of this (zero) and floating point will probably result in a number near zero but not zero.

-44408.9209850062

Eek! [/high-pitch girly squeal]

Maybe that's where the budget deficit came from.

Interesting. This means Excel is using 64-bit floating point math (doubles):



The "long double" type uses the native precision of the CPU's floating point registers and operations which in the case of x86 and x86_64 are 80-bit.

I'm glad I don't have to use Excel. doubles are treacherous!

Luckily Excel 2010 gives a choice between old 32-bit and new 64-bit floating point. [/sarcasm]

So I've got a friend that's on the Excel team at Microsoft. He said if I find any bugs/have any requests to send 'em his way.

By the way, I figured out how to do this in Excel (despite floating point discrepancies). The following formula will convert any decimal fraction into the closest ratio of integers in the form numerator/denominator as a text string:

Fraction = TEXT(decimal,"?/???")

Just add more ?s to get a more accurate fraction with larger integers.

Then you can extract the denominator of each fraction as a substring to the right of the "/", convert this to a value, and then calculate the lowest common multiple of all the denominators (as Tom suggested) with the LCM function (as Gingervergo suggested). Works like a charm.

Just in case you were interested...