Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Jul 23, 2014 11:22 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 23 posts ] 
Author Message
 Post subject: Basic math question
PostPosted: Thu Nov 15, 2012 10:00 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
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?

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 10:09 am 
Offline
User avatar

Joined: Fri Mar 06, 2009 9:23 pm
Could you just multiply all of the fractions by their least common multiple?

Here is the excell command

_________________
--Eric Vergo

My Shapeways shop


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 10:13 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I don't think so, as that can produce more fractions. :(

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

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Last edited by KelvinS on Thu Nov 15, 2012 10:32 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 10:14 am 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
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.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 10:35 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
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...

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 10:57 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
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.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 11:01 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
The problem with that approach is it doesn't work for recurring fractions like 0.3333333'.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 11:51 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
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.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 11:56 am 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
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.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 12:11 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I'm using Excel, which somehow manages to calculate 1/3 * 3 as an integer, even though it calculates via a decimal fraction.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 12:21 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
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.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 1:05 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I suspect it calculates to 17dp and then rounds the answer to 16dp, or something like that.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 1:11 pm 
Offline

Joined: Sun Mar 27, 2005 7:37 pm
Quote:
Basic math question

Since when were you American?

_________________
Image


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 1:16 pm 
Offline
User avatar

Joined: Wed Apr 01, 2009 2:59 pm
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.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 2:13 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Tony Fisher wrote:
Quote:
Basic math question

Since when were you American?

Just British with bad spelling. :lol:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 2:31 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Iranon wrote:
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.


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.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 2:57 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
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.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 3:24 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
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.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 4:18 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
bmenrigh wrote:
What does Excel say about something like (2 - (sqrt(2)^2)) * 10^20 ?

-44408.9209850062

Eek! [/high-pitch girly squeal] :shock:

Maybe that's where the budget deficit came from.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 4:38 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
KelvinS wrote:
bmenrigh wrote:
What does Excel say about something like (2 - (sqrt(2)^2)) * 10^20 ?

-44408.9209850062

Eek! :shock:

Maybe that's where the budget deficit came from.

Interesting. This means Excel is using 64-bit floating point math (doubles):
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {

  float f; double d; long double ld;

  f = (2.0 - powf(sqrtf(2), 2)) * powf(10,20);
  d = (2.0 - pow(sqrt(2), 2)) * pow(10,20);
  ld = (2.0 - powl(sqrtl(2), 2)) * powl(10,20);
  printf("float is %.30f\n", f);
  printf("double is %.30f\n", d);
  printf("long double is %.30Lf\n", ld);

  return 0;
}

Code:
brenrigh@lambda ~ $ gcc -o math math.c -lm
brenrigh@lambda ~ $ ./math
float is 11920929193984.000000000000000000000000000000
double is -44408.920985006261616945266723632812
long double is 10.842021724855044340074528008699


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!

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 4:42 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
bmenrigh wrote:
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]

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Thu Nov 15, 2012 5:35 pm 
Offline
User avatar

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
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. :D


Top
 Profile  
 
 Post subject: Re: Basic math question
PostPosted: Fri Nov 16, 2012 3:19 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
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. :D

Just in case you were interested... :wink:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 23 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 12 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group