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

1. Mar 16, 2016

iScience

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. Mar 16, 2016

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.

3. Mar 21, 2016

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.

4. Mar 21, 2016

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.

5. Mar 22, 2016

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.

6. Mar 22, 2016

OrangeDog

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

7. Mar 23, 2016

Baluncore

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

8. Mar 23, 2016

HallsofIvy

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.

9. Mar 23, 2016

Staff: Mentor

But iScience provides an example of what he is talking about: an n-digit integer.

10. Mar 23, 2016

Baluncore

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.