Calculating greatest common divisor [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

I have written the following function to calculate GCD of floating point numbers, but when I run this for the input (111.6, 46.5), the calculation of fmod(a,b) in the funciton starts giving the wrong result after 2 recursive calls. I am unable to find the error here. Can anyone find what is going wrong here?

float gcd(float a, float b){
if (a>b) {
    if(b==0){
        return a;
    }
    else {
        return gcd(b, fmod(a,b));
    }
}
else {
    if (a==0) {
        return b;
    }
    else {
        return gcd(fmod(b,a), a);
    }
}

}

Answer 1

Because of the way that floating-point values are represented, the source text “111.6” is converted to 111.599999999999994315658113919198513031005859375, and the source text “46.5” is converted to 46.5. Then your gcd function returns 7.62939453125e-06. That is the correct GCD of the two input values.

Note that the first value is 14627635/131072. All floating-point numbers are some integer (within a certain range) multiplied or divided by a power of two. It is impossible to represent 111.6 exactly with binary floating-point. Since you cannot represent 111.6 exactly, you cannot do exact arithmetic with it. Floating-point is largely designed for approximate arithmetic. Doing exact arithmetic requires a great deal of care.

---

What does it mean to talk about the GCD of real numbers (as opposed to integers)?

The GCD of a and b is the largest number c such that a/c and b/c are integers.

Answer 2

float gcd(float a, float b){
    printf("a=%f b=%f\n",a,b);
if (a>b) {
    if(b==0){
        return a;
    }
    else {
        return gcd(b, fmod(a,b));
    }
}
else {
    if (a==0) {
        return b;
    }
    else {
        return gcd(fmod(b,a), a);
    }
}
}
main(){
    printf("%f\ndddeellliiimmiitteerr\n",gcd(1116,465));
    printf("%f\n",gcd(111.6,46.5));
}

so as u can see float not so accurate .
you can try double (but it too :) ) or ... read about how float stored