2

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);

}
Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
Zerender
  • 37
  • 1
  • 2
    At least `m + 1;` should be `m += 1;`. You will need another strategy (read input as string and parse that) to avoid errors in floating-point calculation. – MikeCAT May 14 '21 at 13:23
  • `m + 1;` You may need to turn the warning level up on your compiler. I would expect a message like code has no effect. Like this: [https://godbolt.org/z/xav4zEeqT](https://godbolt.org/z/xav4zEeqT) – drescherjm May 14 '21 at 13:24
  • 1
    What you did wrong is use floats, because [floating point math is broken](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). If you multiply `.3` by `3` you may not actually get 1. The result may look like 1, but it might not actually be 1. Therefore, this kind of a puzzle must be solved using string digit manipulation and integer math ***only***. – Sam Varshavchik May 14 '21 at 13:25
  • 2
    @SamVarshavchik: “If you multiply .3 by 3 you may not actually get 1”: That is good, because .3 times 3 is .9. – Eric Postpischil May 14 '21 at 13:25
  • Let's make that .25 times 4, then. – Sam Varshavchik May 14 '21 at 13:27
  • @SamVarshavchik: Re “Therefore, this kind of a puzzle must be solved using string digit manipulation and integer math only”: That is false. If `a` is an integer, there is no solution. If its fraction portion is ½, the solution is 3 (unless the OP **wants** rounding, see below). Otherwise, the solution is 2. These tests can be accomplished without “string digit manipulation.” If the OP wants rounding, so that ⅔•3 produces 2, then of course they simply use floating-point arithmetic directly. – Eric Postpischil May 14 '21 at 13:27
  • The way `float`s are represented (`s * 2^x`) you only ever need to check powers of 2, since any number other than 0 can be expressed as `o* 2^y` where `o` is odd and this value is integral if and only if `y` is positive. However this also means that the integer you have to multiply with to get an integral value may exceed the range of a 64 bit int. – fabian May 14 '21 at 13:32
  • The question title and the text contradict each other. The title says that we should find `m` such that `m * a` is integer, where the question states that we want to find `m` such that `m * a` is not an integer. From the code, I think @Zerender actually wants to achieve what was written in the title. – He3lixxx May 14 '21 at 13:33
  • 3
    @SamVarshavchik another bad example, because .25 is one of a small set of numbers that *can* be represented exactly by a float. .1 by 10 would be better. – Mark Ransom May 14 '21 at 13:39
  • So, to be clear, is your goal to transform human readable decimal numbers (inputted by an user or read from a file, but in a *decimal* representation) into integer or are you trying to transform a generic value stored in variable of type `float`? – Bob__ May 14 '21 at 13:45
  • This question sounds like a really confusing way to describe approximation of floating-point numbers as a ratio of integers, which already has many answers such as https://stackoverflow.com/q/51142275/103167 and https://stackoverflow.com/q/4385580/103167 – Ben Voigt May 14 '21 at 15:44

2 Answers2

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.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
0

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

K. H. Tam
  • 41
  • 7
  • . . . Just to add a point, the reason why I'd prefer this method over the answer provided by Mark is that some repeating decimals (stored in double-precision floating point format) can also be converted into simple fractions (e.g. 0.33333 33333 33333 -> 1/3 with an error allowance 1e-12). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . With the original method, c == (int) c isn't good enough for checking floating-point equivalence. Error allowance should be used if you have to check that, since it is common knowledge that 0.1 + 0.2 = 0.30000000000000004 and is NOT 0.3. – K. H. Tam Jan 25 '23 at 14:47