How to make a program that finds the smallest number that can be multiplied by some float to make an integer

Question

I am trying to create a program that will find the smallest integer greater than one that I can multiply a float by and obtain a non-integer. It should output the multiplied by value as well as what it is multiplied to. For instance, if the user enters 2.8 should return 5 and 14. Here is my code but it executes for a long time and then outputs 2 and 5.6. What did I do wrong?

#include <iostream>
#include <string>


int main()
{
    float a;
    int m = 2;
    float c = 0.00;
   
    std::cin >> a;

    for (int i = 0; i < 999999999; i++) {

        c = a * m;

        if (c == (int)c) {
            break;
        }

        else {
            m + 1;
        }
    }
        std::cout << "The lowest number to multiply by is " + std::to_string(m) + " and it equals " + std::to_string(c);

}

Answer 1

I had the same question as you and I searched on the Internet. Most answers are complicated, if not inefficient, like counting from denominator = 1 to infinity.

The algorithm below is written in java, yet it can be easily transplanted onto c++.

The algorithm is as belows:

public static String toFrac(double value){
        long num = 1, den = 1, tem; ArrayList<Long> gamma = new ArrayList<Long>();
        double temp = value;
        while(Math.abs(1.*num/den - value) > 1e-13){
/*1e-13 is the error allowance, 
as double format has a precision to around 1e-15 for integral values, 
and this value should be changed where appropriate, 
especially that float values only has a precision to 1e-6 to 1e-7
for integral values.*/
            gamma.add((long)temp);
            temp = 1/(temp - (long) temp);
            
            den = 1; 
            num = gamma.get(gamma.size()-1);
            for(int i = gamma.size()-2; i >= 0; i--){
                tem = num;
                num = gamma.get(i)*tem+den;
                den = tem;
            }
        }
        return num+"/"+den;
    }

Basically, within the loop, we compute the continued fraction of the float. This can be done by:

*in above code, double means double precision, a format more accurate than float. The algorithm can be applied to float easily. Similarly, long is the equivalent of int but with larger range.

Algorithm

1.temp = your_float

2.Find floor(temp), store it into a list gamma[]. (In java, ArrayList<Long> is used for its convenience to add new elements, you may use int[] instead.)

3.Subtract off this integral part, then store the reciprocal 1/(decimalPart(temp)) back into temp

4.Repeat step 2 - 3 to generate a list of gamma.

Sample Output

The intermediate results are as follows (debugging statement not shown in code):

input: 891/3178

 = 0.2803650094398993

input: toFrac 0.2803650094398993

 = 
0,
val: 0.0
exp: 0/1

0,3,
val: 0.3333333333333333
exp: 1/3

0,3,1,
val: 0.25
exp: 1/4

0,3,1,1,
val: 0.2857142857142857
exp: 2/7

0,3,1,1,3,
val: 0.28
exp: 7/25

0,3,1,1,3,4,
val: 0.2803738317757009
exp: 30/107

0,3,1,1,3,4,9,
val: 0.28036437246963564
exp: 277/988

0,3,1,1,3,4,9,1,
val: 0.28036529680365296
exp: 307/1095

0,3,1,1,3,4,9,1,1,
val: 0.2803648583773404
exp: 584/2083

0,3,1,1,3,4,9,1,1,1,
val: 0.2803650094398993
exp: 891/3178

output "891/3178"

Indeed, this algorithm doesn't take many iterations. This should be an efficient yet clean algorithm.

Working Principle

<b>EXAMPLE: </b> your_float = 0.2803650094398993
Iteration 1: = 0 + 1/ 3.566778900112234
Iteration 2: = 0 + 1/ (3 + 1/ 1.7643564356435628)
Iteration 3: = 0 + 1/ (3 + 1/ (1 + 1/ 1.3082901554404172))
Iteration 4: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ 3.2436974789915682)))
Iteration 5: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (1 + 1/ 4.103448275862547)))
Iteration 6: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ 9.666666666621998))))
Iteration 7: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 1/ 1.5000000001005045)))))
Iteration 8: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 1/ (1 + 1/ 1.999999999597982))))))
Iteration 9: = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 1/ (1 + 1/ (1 + 1.000000000402018)))))))

Answer = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 1/ (1 + 1/ (1 + 1))))))))
 = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 1/ (1 + 1/ 2)))))))
 = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 1/ (9 + 2/ 3))))))
 = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 1/ (4 + 3/ 29)))))
 = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 1/ (3 + 29/ 119))))
 = 0 + 1/ (3 + 1/ (1 + 1/ (1 + 119/ 386)))
 = 0 + 1/ (3 + 1/ (1 + 386/ 505))
 = 0 + 1/ (3 + 505/ 891)
 = 0 + 891/ 3178

Although this algorithm might not be the most efficient, it is at least way faster than bruteforcing.

Here is what you are looking for: Your Example:

input: toFrac 2.8

output: = 14/5

Back onto the root problem, you asked that I am trying to create a program that will find the smallest integer greater than one that I can multiply a float by and obtain an integer., so the algorithm above outputs: 14/5, which are the two values that you are seeking: 2.8*5 = 14.

Generally, when the algorithm above outputs num = NUM_OUT and den = DEN_OUT, then your_float*DEN_OUT = NUM_OUT with an maximum error allowance chosen by you.

Hope this is what you're looking for. :)

Answer 2

The brute force approach you're taking will take a long time, even after you've corrected the bugs. And because of floating point inaccuracies it might not deliver correct results anyway. Here's a better algorithm.

Read the number as a string instead of as a float.

Start a denominator at 1. Count the number of digits to the right of the decimal point, and for each digit multiply the denominator by 10.

Remove the decimal point from the string and convert it to an integer; this is your numerator. Your example of 2.8 is equal to 28/10.

Take the GCD of the numerator and denominator and divide both by that number. For your example, the GCD of 28 and 10 is 2, so your fraction is now 14/5.

The simplified denominator is your answer, and the numerator is the result when you multiply.