F
R = ---
D
When transmitting data in a certain rate ( R ), clock rate ( F ) has to be divided ( D ). And sometimes, it is desirable to have the rate as integer. Usually, F is given from the transmitting device. And we want to know every possible R.
This asks R to be integer and asks D to divide F without fraction. Then F has to be integer multiple of D. First F has to be factored into prime numbers. Then all the permutation of prime numbers has to be generated. Then each permuation can be D ( or R in here).
Prime numbers of clock can be calculated on the fly but not the point in this article. Assume prime numbers are already known like { 2, 3, 5, 7, 11, ... }. Then factors of R can be enumerated by continuously divide with each primes like below function.
IEnumerable< int> Factors(int n, IEnumerable< int> primes)
{
foreach (int p in primes) {
if (p * p > n) break;
while (n % p == 0) {
yield return p;
n /= p;
}
}
if (n > 1) yield return n;
}
Then each factors can be permuted and enumerated so that each dividible product can be calculated.
IEnumerable< int[]> Combination(Tuple< int, int>[] groups )
{
var product = new int[groups.Count()];
foreach (var p in RecursivelyCombine(product, groups, 0)) {
yield return p;
}
}
IEnumerable< int[]> RecursivelyCombine(int[] products, Tuple< int, int>[] factors, int index)
{
var factor = factors[index];
for (int i = 0; i <= factor.Item2; ++i) {
products[index] = i;
if (index == factors.Length - 1) {
yield return products;
}
else {
foreach (var p in EnumerateProduct(products, factors, index + 1)) {
yield return p;
}
}
}
yield break;
}
Then here is function that enumerate all possible rates with a given clock F.
IEnumerable< int> Rates(int F) // F = 50
{
auto factors = Factors( 500, new int [] { 2, 3, 5, 7 } );
// factors = { 2, 2, 5, 5, 5 }
var groups = factors.GroupBy(f => f).Select(g => new Tuple(g.Key, g.Count())).ToArray();
// groups = { {2,2}, {5,3} } <- 2^2 x 5^3
foreach (int[] pm in Combination(groups)) { // {0,0}, {0,1}, {0,2}, {0,3}, {1,0}, .... , {2,3}
// pm can be { 1, 2 } which means D = 2^1 x 5^2
int D = 1;
for (int i = 0; i < groups.Length; ++i) {
D *= (int)Math.Pow(groups[i].Item1, pm[i]);
}
yield return D;
}
}
