Calculating Task Periodic Rate

I'm having a complete brain seizure here with what should be a simple math problem. I need to set the periodic rate of an embedded task so that it performs certain things at a particular rate.

E.g if the task has to perform 4 things at, say,  6Hz, 3Hz, 2Hz and 4Hz how do I calculate taht the task must run at 12Hz?? (Accuracy is not super important here)

-- No, this is not homework. A student could probably figure this out in less time than it has taken me to type the question in...

Brain dead today
Friday, June 18, 2004

You have to find the lowest common multiple. Take multiples of each number until you find one that all share.

DJ
Friday, June 18, 2004

6Hz, 3Hz, 2Hz and 4Hz

Step 1
6 = 2x3
3 = 3
2 = 2
4 = 2^2

Step 2
n = 2^2 x 3

And a note: if a process has a highest frequency F in its spectrum, you need to sample it at 2xF in order to be able to capture all events and reconstruct the original signal (Nyquist criteria/Shannon sampling theorem)

Dino
Friday, June 18, 2004

Take multiples (starting with 1) of the highest resolution number (6):

6x1%4 = 4, so 6x1 doesn't work.
6x2%4 = 0, so 6x2 (=12) works.

Derek
Friday, June 18, 2004

Example:

24 and 90

24 = 2^3 x 3
90 = 2 x 3^2 x 5

N = 2^3 x 3^2 x 5 = 360

Dino
Friday, June 18, 2004

Oops, I forgot to try all the other numbers from the problem (4, 3, 2). Continuing:

6x1%4 = 4, so no need to keep trying 6x1

6x2%4 = 0
6x2%3 = 0
6x2%2 = 0

...so 6x2 works.

Derek
Friday, June 18, 2004

dorks.

muppet is now from madebymonkeys.net
Friday, June 18, 2004

The direct method for finding lowest common multiple is to use the prime factorization, i.e,

2, 3, 4, 6, have prime factorizations of:
2^1, 3^1, 2^2, 2^1*3^1.

Take the primes:
2 and 3

Take the highest exponents present:

2^2, 3^1

multiply = 12.

Ryan Anderson
Friday, June 18, 2004

But then you have the prime factorization first.

I think the best way is via the greatest common denominator, and the use the equation gcd(a, b) * lcm(a, b) = a * b to calculate the lcm.

I'd use Euler's method to calculate the gcd. In Python, but close enough to pseudocode for everyone to understand:

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a*b/gcd(a, b)

For more than two numbers,  note that

lcm(a, b, c) = lcm(lcm(a, b), c) (and the same for more numbers)

For four numbers, you could use:

lcm(a, b, c, d) = lcm(lcm(a, b), lcm(c, d))

In your example with the functions defined above, Python gives

lcm(lcm(6, 3), lcm(2, 4)) = 12

vrt3
Saturday, June 19, 2004

(errata: That's Euclidean algorithm, not Euler's method)

vrt3
Saturday, June 19, 2004

Thanks guys. vrt3 that's pretty much how I'm going to do it since GCD is simple to implement (I have to use c++)  and I need to be able to change the number of rates and the rate values on the fly.

Brain dead today
Saturday, June 19, 2004

  Recent Topics

  Fog Creek Home