Find greatest common denominator of two values to get integer

Hello,

I have two sampling rates:

fs_A = 24414;

fs_B = 92782;

And I want to find the greates value (x) that can be devided into both sampling rates to give integers. Thus, the two equations are:

24414 / x = an integer ; 92782 / x = another integer

Can anyone help me out?

I only get an integer for 'x' when I use the gcd function, but I would like to have non-integers solutions as well.

Thanks.

[Stephen23]

"I do not get integers when I use the gcd function."

>> A = 24414;
>> B = 92782;
>> G = gcd(A,B)
G =  2
>> A/G
ans =  12207
>> B/G
ans =  46391

[Charlotte A Navntoft]

Thank you for your answer!

I wasn't clear in my question: would it be possible to get 'G' as a non-integer to get a higher value?

[David Goodmanson]

Hello Charlotte,

no, it's not possible.

[Charlotte A Navntoft]

Hello David, thank you for your answer. Ok what a shame.

[Stephen23]

Because you are looking for integers it is easy to perform an exhaustive check for all possible x>=1:

>> Na = 24414;
>> Nb = 92782;
>> Xa = Na ./ (1:Na);
>> Xb = Nb ./ (1:Nb);
>> X = intersect(Xa,Xb)
X =
   1   2

[Charlotte A Navntoft]

Hello Stephen,

Just to be sure that I understand your answer: do you mean that the only two solutions with integers are 1 and 2?

This method will not give me non-interger results of 'X', e.g. such as for instance 4882.12

[Steven Lord]

Charlotte A Navntoft,

For the original problem, 4882.12 is not a solution.

>> 24414/4882.12
ans =
           5.0006964187689

>> 92782/4882.12
ans =
          19.0044488869589

Neither of those values are integers. If we were to round them to 5 and 19, the results are not IMO close enough to the original values.

>> 4882.12*[5, 19]
ans =
                   24410.6                  92760.28

To check non-integer values take advantage of the fact that both 24414 / x = an integer and 92782 / x = another integer.

Rewrite the first equation as 24414/an integer = x. Find all candidate x values.

candidateXValues = 24414./(1:24414);

Now check if any of the candidate X values satisfy the second equation.

check = 92782./candidateXValues;
[diffFromInteger, location] = min(abs(check-round(check)))

Candidate 12207 minimizes the difference between check and round(check). That candidate X value is x = 2.

Let's take a closer look at the results, shall we?

plot(check-round(check), 'o');
ylim([-1e-4, 1e-4])

There are six candidates that result in 92782./candidate being within 1e-4 of an integer value. The only two that are exactly integers are candidates 12207 (x = 2) and 24414 (x = 1.) But if 1e-4 is "close enough" four other possibilities are:

closeEnough = [4994, 7213, 17201, 19420];
xclose = candidateXValues(closeEnough).';
format longg
[xclose, 24414./xclose, 92782./xclose]

[Charlotte A Navntoft]

Hello Steve,

I meant 4882.12 as an example of that x could be a decimal number - not as the solution for x!

My apoligises for that confusion, but thank you for that second option.

I'll use x=2

[John D'Errico]

Sometimes the answer is easier than it looks.

[Stephen23]

"This method will not give me non-interger results of 'X', e.g. such as for instance 4882.12 "

If they exist it will. This is easy to demonstrate on an example where there actually are some non-integer x, e.g.:

>> Na = 15;
>> Nb = 10;
>> Xa = Na ./ (1:Na);
>> Xb = Nb ./ (1:Nb);
>> X = intersect(Xa,Xb)
X =
   1.0000   1.2500   1.6667   2.5000   5.0000

Checking that those x-values produce integers:

>> Na ./ X
ans =
   15   12    9    6    3
>> Nb ./ X
ans =
   10    8    6    4    2

[Charlotte A Navntoft]

Ah, thank you Stephen, that makes sense!

Answer 1

[John D'Errico]

Ugh. This is not a pretty thing to do, when working in floating point arithmetic. You need to work with tolerances. Yes, GCD is perfect, when the numbers are integers. So what can you do?

Is there a solution when no integers are assumed? Hmm, I wonder. At first, you might think of trying to use the Euclidean algorithm, just not using integer arithmetic. In fact, that might even have a good chance to work, IF you were careful with the tolerances. But first, let me create an example.

format long g
>> A = 137*3*pi/2
A =
          645.597290312703
          
>> B = 137*7*pi
B =
          3012.78735479261
                   
gcd(A,B)
Error using gcd (line 31)
Inputs must be real integers. 

A problem is that A and B are not known exactly as floating point numbers in MATLAB. In fact, I've constructed the example such that the largest value we can divide both A and B by, and get an integer result is simple: 137*pi/2. But suppose you just gave me those numbers, without telling me how they were created? Is there a simple trick? Well, yes. But you still need to use tolerances.

The idea is to use the function rat, with a tolerance.

[N,D] = rat(A/B,1e-13)
N =
     3
D =
    14

What does that tell us? What is the largest number we can divide both A and B by, and still get an integer? I'll put it in the variable div.

div = A/N
div =
          215.199096770901

I could have computed it equally well as

div = B/D
div =
          215.199096770901

As you can see, it is the same number. Is it the theoretically correct value? I said above that it should be...

137*pi/2
ans =
          215.199096770901

So rat actually returns the result, AFTER dividing A and B by the desired number div, and all I had to do was to extract it using N or D.

As you can see, this is indeed the largest real number you can divide into both A and B, and have them both yield an integer.

Can I try a more difficult case, where i don't know the answer in advance?

A = rand(1)*1e5
A =
          14188.6338627215
>> B = rand(1)*1e5
B =
          42176.1282626275
>> [N,D] = rat(A/B,1e-13)
N =
      218086
D =
      648267
>> div = A/N
div =
        0.0650598106376454
>> B/D
ans =
        0.0650598106376346

Here div is a pretty small number, but then what can you expect from two randomly chosen numbers? I might even be happy the divisor was that large given two entirely random numbers.

Ok, so how does this work, when applied to your problem? Remember, we need to use tolerances here. If you want a VERY accurate approximation, then you need to use a tiny tolerance.

fs_A = 24414;
fs_B = 92782;

>> [N,D] = rat(fs_A/fs_B,1e-13)
N =
       12207
D =
       46391
>> div = A/N
div =
          1.16233586161395

However, if I am willing to back down on the tolerance, then I can get a result that is less accurate, but perhaps closer to what you want.

>> [N,D] = rat(fs_A/fs_B,1e-4)
N =
     5
D =
    19
    
>> fs_A/N
ans =
                    4882.8
>> fs_B/D
ans =
          4883.26315789474
    

As you see here, there is aa difference between how we might compute div, based on which fraction we try. But that suggests what may perhaps be a simple compromise. Just take the average.

>> div = (fs_A/N + fs_B/D)/2
div =
          4883.03157894737

>> fs_A/div
ans =
          4.99976287379712
          
>> fs_B/div
ans =
          19.0009010795709          

So, to about 4 significant digits, that seems reasonable, and as good as we can get for that tolerance. A smaller tolerance yields a better solution:

>> [N,D] = rat(fs_A/fs_B,1e-6)
N =
   556
D =
        2113
>> div = (fs_A/N + fs_B/D)/2
div =
          43.9100761983882
>> fs_A/div
ans =
          555.999946110232
>> fs_B/div
ans =
           2113.0002048005

I'm afraid I can't do much better than a solution this simple. You will need to choose a tolerance, but then the rest is trivial.

How does this solution work when GCD would also have worked? In this next example, the GCD should be 12, and all are integers, so GCD will work, but so should RAT.

A = 144;
B = 60;
gcd(A,B)
ans =
    12

[N,D] = rat(A/B,1e-6);
div = (A/N + B/D)/2
div =
    12

RAT agrees with GCD.

[Charlotte A Navntoft]

Hello John, thank you very much for your throughout and pedagogical explanations, I appreciate that!

Answer 2

[David Goodmanson]

Hello Charlotte,

In terms of your original question, you have integers A and B and you want to divide them by a number x such that A/x and B/x are both integers and x is as large as possible. g = gcd(A,B) is the largest integer that does the job, and the question is if there is a number x, not an integer, that works, with x > g. The answer is no as I mentioned, and it is not hard to prove.

If A/x = y1, where y1 is an integer, then x = A/y1, so x must be a rational number. Say x = a/b. We can reduce a/b to lowest terms, meaning they have no prime factors in common, otherwise we could divide both a and b by that factor to get a new a and b. Now

A/(a/b) = y1
B/(a/b) = y2

and you are trying to make y1 and y2 as small as possible by making (a/b) a big as possible. Now

Ab/a = y1
Bb/a = y2

Since a and b have no prime factors in common, all the prime factors of a have to divide into A, with b as a bystander. So now

b (A/a) = y1
b (B/a) = y2

Since a is an integer and needs to be as large as possible, we are right back to the greatest common divisor problem for A and B, and a = g = gcd(A,B). Looking at the equations above, b is an integer so y1 and y2 are as small as possible when b = 1. The final result is the gcd result,

A/g = y1
B/g = y2

You can see this in Stephen's comment, where several rational numbers get the job done, but the largest one is 5, which is the gcd of 10 and 15.

[Charlotte A Navntoft]

Thank you very much David for that elaboration. Now I know a lot more about gcd's than before!