Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Optimization Problem -- Can a number always be expressed as the ratio of two other numbers?

  1. Mar 16, 2016 #1
    Take a number r that is n-digits long where n is finite.
    so if r =2385813...
    $$r_1r_2r_3...r_n$$
    $$r_1 = 2$$
    $$r_2 = 3$$
    $$r_3 = 8$$
    etc..

    I postulate (since I don't know this is true): Every such number can be expressed as a division between two other numbers, say a and b.

    $$r = \frac{a}{b}$$

    How would you go about finding a and b optimized by minimizing the number of digits in a and b?

    In other words, there are an infinite number of combinations of a and b. but of that set of combinations, I want the one that requires the least number of digits in a and b combined.
     
  2. jcsd
  3. Mar 16, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    r=a, b=1? Increasing both a and b by the same factor won't reduce the number of digits, and adding decimal points does not help either.
     
  4. Mar 21, 2016 #3

    NascentOxygen

    User Avatar

    Staff: Mentor

    I expect you'll just have to factorize each then throw out common factors. There are utilities that will find the prime factors for you.
     
  5. Mar 21, 2016 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    points:
    Every number is ultimately divisible by one or more prime numbers or is prime.

    Division operations (as machine instructions) are slower than most other integer opcodes. Using division to create and multiplication to restore them is not going to be an optimal approach necessarily.

    If what you stated was viable it would be something that people who build math libraries would use, don't you think? I do not know of any libraries using this approach, do you? I used to work on 8 bit and 16 bit machines. We would have committed nasty crimes back then to get some way to represent numbers with fewer digits of precision reliably and efficiently. Have look at this:

    https://publib.boulder.ibm.com/iseries/v5r1/ic2924/books/c0925083170.htm

    This was an attempt to do sort of what you are looking at.
     
  6. Mar 22, 2016 #5

    NascentOxygen

    User Avatar

    Staff: Mentor

    I see that I completely misunderstood what was being asked. I read it as there being an n-digit fraction and the goal is to reduce that exact ratio to its lowest terms, e.g., given 0.94645 how to reduce the proper fraction 94645/100000 to its simplest/shortest equivalent proper fraction.

    On review, I see the OP is concerned with integers, in which case it leaves nothing more to be done: as mfb indicates, b=1 is always optimal.

    So I'm left to conclude that member @iScience has not correctly posed the question he/she originally set out to ask. :oldgrumpy:
     
  7. Mar 22, 2016 #6
    Well, this might not be exactly what you are doing, but since you didn't specify any restrictions you could express a complicated fraction as a sum of smaller fractions, eg:

    1/3+1/5+1/9+1/16 +1/23 = (16560+9936+5520+3105+2160)/49680 = 37281/49680 = .750422705314...
     
  8. Mar 23, 2016 #7

    Baluncore

    User Avatar
    Science Advisor

    As a general rule the number of digits needed to represent a real number will be the same as the number of digits in the integers a and b combined, when r = a / b.

    I think you should study the approximation of real numbers by the ratio of integers. Convert a real number to a continued fraction by repeated removal of the integer part, then inversion of the fractional part. Then evaluate the continued fraction back to a ratio a/b. Depending on how many terms you consider, you will get less digits or more accuracy.
    https://en.wikipedia.org/wiki/Continued_fraction#Motivation_and_notation
     
  9. Mar 23, 2016 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Could we please, please, please not just say "numbers" without distinguishing between "integers", "rational numbers", and "real numbers". The iscience just said "write a number as a ratio of two numbers" and mfb pointed out that "a" can always be written as "a/1". I suspect that iscience was asking if a number can always be written as a ratio of integers. The answer to that is "yes" for rational numbers (in fact that is a way "rational numbers" are commonly defined) but no for general real numbers.
     
  10. Mar 23, 2016 #9

    NascentOxygen

    User Avatar

    Staff: Mentor

    But iScience provides an example of what he is talking about: an n-digit integer.
     
  11. Mar 23, 2016 #10

    Baluncore

    User Avatar
    Science Advisor

    Any representation of an n-digit integer r, as an integer fraction, r = a / b will need at least one more digit than r, since b must take a value of at least 1.

    But if r is a real number, then the integer ratio a / b takes it into the world of continued fraction approximations.

    All the square roots of integers that are irrational can be represented by recurring continued fractions.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Optimization Problem -- Can a number always be expressed as the ratio of two other numbers?
Loading...