CODEWITHSUNDEEP
algorithmgreatest-common-divisor
Philip Badilla
Philip Badilla

Reputation: 1058

How to get the (Greatest Common Divisor)GCD of Doubles

This is a simple task but i can't seem to figure out how to do it

Here is a sample function structure

private double GetGCD(double num1, double num2)
{
    //should return the GCD of the two double
}

test data 

   num1 = 6;
   num2 = 3;
   *return value must be 3*

   num1 = 8.8;
   num2 = 6.6;
   *return value must be 2.2*

   num1 = 5.1;
   num2 = 8.5;
   *return value must be 1.7*

note: maximum decimal places is 1. programming language is not important. i just need the algorthm

please help.. thank you!

Upvotes: 1

Views: 9379

Answers (5)

Adam Matan
Adam Matan

Reputation: 136351

If you have only one decimal place, multiply the numbers by 10, convert them to integers and run an integer GCD function.

This will also save you floating point precision errors.

Quoting this answer, the base Euclidean algorithm in Python (for integers!) is:

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

So, your code should be something like:

 def gcd_floats(x,y):
     return gcd( int(x*10), int(y*10) )/10

Upvotes: 4

bucko
bucko

Reputation: 1188

There is no such thing as the GCD of a number which is not discrete. However, your case is more specific. If your input is not a Double, but a Decimal, then you can convert it to a Fraction, multiply the denominators, find the GCD of the numerators and divide back down. That is:

8.800 = 8800/1000 = 44/5 (by GCD)
6.600 = 6600/1000 = 33/5 (by GCD)

5.100 = 5100/1000 = 51/10
8.500 = 8500/1000 = 17/2

It's useful to simplify the fractions in this step in order to avoid our numbers getting too large.

Move to a common denominator:

44*5/5*5 = 220/25
33*5/5*5 = 165/25

51*2/2*10 = 102/20
17*10/2*10 = 170/20

GCD of numerator:

gcd(165,220) = 55

gcd(102,170) = 34

So answers are 55/25 and 34/20.

Upvotes: 1

John Eipe
John Eipe

Reputation: 11226

Using 2 methods

  1. The traditional division method
  2. Euclid's method

    class GCD
    {
        public static void main(String[] args)
        {
            int a = (int)(1.2*10);
            int b = (int)(3.4*10);

            System.out.println((float)gcd(a, b)/10);
        }
    // 1

        public static int gcd(int a, int b)
        {
            if(b==0)
                return a;
            else
                return gcd(b, (int)a%b);
        }

    // 2
        public static int gcd(int a, int b)
        {
            int k,i;

            if(a>b)
                k = b;
            else
                k = a;

            for(i=k; i>=2; i--)
            {
                if( (a%i==0)&&(b%i==0) )
                {
                    break;
                }
            }
            return i;
        }
    }

Upvotes: 0

Avi Cohen
Avi Cohen

Reputation: 3414

When it's 8.8 and 6.6 then you can find the GCD of 88 and 66 and then divide it by 10.

Upvotes: 3

High Performance Mark
High Performance Mark

Reputation: 78344

There are zillions of places on the web to find code for the GCD function. Since, strictly speaking, it is only defined on integers, I suggest you multiply your doubles by 10, work out the GCD and divide the result by 10. This will save you a world of pain arising from using the wrong datatype.

Upvotes: 1

Related Questions