Find greatest common denominator of two values to get integer
13 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
Charlotte A Navntoft
il 16 Apr 2020
Commentato: Charlotte A Navntoft
il 17 Apr 2020
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.
11 Commenti
Stephen23
il 16 Apr 2020
Modificato: Stephen23
il 16 Apr 2020
"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
Risposta accettata
John D'Errico
il 16 Apr 2020
Modificato: John D'Errico
il 16 Apr 2020
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.
Più risposte (1)
David Goodmanson
il 17 Apr 2020
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.
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!