CODEWITHSUNDEEP
frequencylcm
rrrrrrrrrrrrrrrr
rrrrrrrrrrrrrrrr

Reputation: 342

Computing the approximate LCM of a set of numbers

I'm writing a tone generator program for a microcontroller.

I use an hardware timer to trigger an interrupt and check if I need to set the signal to high or low in a particular moment for a given note.

I'm using pretty limited hardware, so the slower I run the timer the more time I have to do other stuff (serial communication, loading the next notes to generate, etc.).

I need to find the frequency at which I should run the timer to have an optimal result, which is, generate a frequency that is accurate enough and still have time to compute the other stuff.

To achieve this, I need to find an approximate (within some percent value, as the higher are the frequencies the more they need to be imprecise in value for a human ear to notice the error) LCM of all the frequencies I need to play: this value will be the frequency at which to run the hardware timer.

Is there a simple enough algorithm to compute such number? (EDIT, I shall clarify "simple enough": fast enough to run in a time t << 1 sec. for less than 50 values on a 8 bit AVR microcontroller and implementable in a few dozens of lines at worst.)

Upvotes: 3

Views: 586

Answers (2)

John Coleman
John Coleman

Reputation: 51998

LCM(a,b,c) = LCM(LCM(a,b),c)

Thus you can compute LCMs in a loop, bringing in frequencies one at a time.

Furthermore,

LCM(a,b) = a*b/GCD(a,b)

and GCDs are easily computed without any factoring by using the Euclidean algorithm.

To make this an algorithm for approximate LCMs, do something like round lower frequencies to multiples of 10 Hz and higher frequencies to multiples of 50 Hz. Another idea that is a bit more principled would be to first convert the frequency to an octave (I think that the formula is f maps to log(f/16)/log(2)) This will give you a number between 0 and 10 (or slightly higher --but anything above 10 is almost beyond human hearing so you could perhaps round down). You could break 0-10 into say 50 intervals 0.0, 0.2, 0.4, ... and for each number compute ahead of time the frequency corresponding to that octave (which would be f = 16*2^o where o is the octave). For each of these -- go through by hand once and for all and find a nearby round number that has a number of smallish prime factors. For example, if o = 5.4 then f = 675.58 -- round to 675; if o = 5.8 then f = 891.44 -- round to 890. Assemble these 50 numbers into a sorted array, using binary search to replace each of your frequencies by the closest frequency in the array.

Upvotes: 1

Ilya
Ilya

Reputation: 5557

An idea:

  1. project the frequency range to a smaller interval

Let's say your frequency range is from 20 to 20000 and you aim for a 2% accurary, you'll calculate for a 1-50 range. It has to be a non-linear transformation to keep the accurary for lower frequencies. The goal is both to compute the result faster and to have a smaller LCM.

  1. Use a prime factors table to easily compute the LCM on that reduced range

Store the pre-calculated prime factors powers in an array (size about 50x7 for range 1-50), and then use it for the LCM: the LCM of a number is the product of multiplying the highest power of each prime factor of the number together. It's easy to code and blazingly fast to run.

  1. Do the first step in reverse to get the final number.

Upvotes: 0

Related Questions