stm32 - генерация точной частоты таймера, задачка школьной программы Опции

[Sprite]

Здравствуйте, уважаемые форумчане!

Задача в следующем: есть таймер, например, 5-й, питается от 72 мГц шины. Требуется генерировать ШИМ частотой в пределах от 10 до 2000 Гц с минимально возможной погрешностью (разницы нет - в большую или меньшую сторону). Когда частота кратна 72 - все прекрасно, но если требуется вывести частоту, например, 13 Гц, то возникает погрешность. Настройка соответственно происходит регистрами PSC и ARR, комбинаций их может быть достаточно много. Самое первое, что приходит в голову - это тупой перебор всех возможных комбинаций с вычислением ошибки и выбором пары PSC и ARR с наименьшей их них, но это не наш метод
Может существует формула для расчета? Или на крайний случай таблица значений регистров для каждой частоты с минимальной погрешностью?

[_Pasha]

В общем-то решается не только цепными дробями.
Я тут тоже посидел, по случаю, накрапал вот:

CODE

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

static unsigned int fast_sqrt(unsigned int arg)
{
unsigned int one,res = 0;
for(one = 1UL << (sizeof(one)*8 - 2); one > arg; one >>=2);

while(one)
{
unsigned int k= res+one;
if(arg >= k)
{
arg -= k;
res += 2*one;
}
res >>= 1;
one >>= 2;
}
return res;
}

unsigned int factorize(unsigned int arg, unsigned int initial)
{
unsigned int j, limit = fast_sqrt(arg);
if(initial == 1) initial += 1;
for(j=initial; (j<=limit)&&(arg%j);++j);
return (j<=limit)?j:0;
}

void get_mpys(uint16_t *a, uint16_t *b, unsigned int num)
{
unsigned int koeff=1;
*a = *b = 1;
while(koeff)
{
unsigned int k = factorize(num,koeff);
if(k)
{
koeff = k;
num /= k;
}
else
{
k = num;
koeff = 0;
}

if(*a * k < 65536)
*a *= k;
else
{
if(*b * k < 65536)
*b *= k;
else
{
*a=*b=0;
return;
}
}
}
}

/*test*/
int main()
{
uint16_t xa,xb;
unsigned int nnn= 7200000/7;
get_mpys(&xa,&xb, nnn);
printf("numb %d a= %d b= %d a*b = %d\n",nnn,xa,xb,xa*xb);
return 0;
}

Вкратце. Имеем static unsigned int fast_sqrt(unsigned int arg) - быстрый целочисленный квадратный корень . Он нам нужен для оценки верхнего предела факторизации, то бишь разложения на множители.
Далее, сам факторизатор - unsigned int factorize(unsigned int arg, unsigned int initial)
Работает тупым перебором, находит множитель начиная с числа initial для параметра arg
Наконец, void get_mpys(uint16_t *a, uint16_t *b, unsigned int num) - тут уже идет последовательное нахождение коэффициентов и домножение их к a или b
То есть a*b=num
Если число не помещается в 16 разрядов - пардон, пользуемся ARR 32 бита.
Можно сравнить погрешности если кто цепные дроби подымет здесь для тестинга.

Сообщение отредактировал _Pasha - May 17 2015, 16:37

[jcxz]

Я тут тоже посидел, по случаю, накрапал вот:
...
unsigned int factorize(unsigned int arg, unsigned int initial)
{
unsigned int j, limit = fast_sqrt(arg);
if(initial == 1) initial += 1;
for(j=initial; (j<=limit)&&(arg%j);++j);
return (j<=limit)?j:0;
}

Это у Вас разложение на простые множители?
При разложении большого arg будет много лишних операций деления.
Возможно лучше после оценки предела (посредством sqrt()), найти все простые числа до него с помощью "решета Сундарама" и пытаться делить только на них.

PS: Кстати - в какую сторону даёт погрешность fast_sqrt()? Если в меньшую - надо быть осторожным при разложении arg == n * n, где n - простое число.
Увеличить бы предел на неск. процентов: limit = fast_sqrt(arg) * 11 / 10 или использовать: limit = 1 << (32 - __CLZ(arg) + 1) / 2

[_Pasha]

PS: Кстати - в какую сторону даёт погрешность fast_sqrt()? Если в меньшую - надо быть осторожным при разложении arg == n * n, где n - простое число.

кстати да. нужна финальная проверка.


По первому вопросу не вникал. Яснопонятно, что это все дороговатые операции, однако, таких приложений сферических , чтобы генерить произвольную частоту - еще поискать нужно.
Проще таблицу простых чисел заиметь во флеше, например
http://integraloff.net/simple/table_simpl_ch.php
до 10**4 это всего-то 2460 байт

Код

unsigned int factorize(unsigned int arg, unsigned int initial)
{
unsigned int j, limit = fast_sqrt(arg);
if(initial == 1) initial += 1;
if(limit*limit < arg) limit +=1;
for(j=initial; (j<=limit)&&(arg%j);++j);
return (j<=limit)?j:0;
}

[jcxz]

Проще таблицу простых чисел заиметь во флеше, например
http://integraloff.net/simple/table_simpl_ch.php
до 10**4 это всего-то 2460 байт

Для решета Сундарама нужно всего 4килобайта ОЗУ для поиска всех простых чисел в диапазоне до 65536. А этого достаточно для разложения на множители любого 32-битного числа.
И алгоритм использует только умножения-сложения.

[_Pasha]

Для решета Сундарама нужно всего 4килобайта ОЗУ для поиска всех простых чисел в диапазоне до 65536. А этого достаточно для разложения на множители любого 32-битного числа.
И алгоритм использует только умножения-сложения.

Интересно. А у нас же ж факторизуемое число уменьшается и нижний предел поиска натуральных чисел растет.
Получается, что и столько озу ему может быть не нужно.

[jcxz]

Интересно. А у нас же ж факторизуемое число уменьшается и нижний предел поиска натуральных чисел растет.
Получается, что и столько озу ему может быть не нужно.

Нет. Для этого алгоритма надо сначала его полностью выполнить чтобы найти все простые не превышающие некоторого.
Нельзя им найти одно простое, его использовать, а потом искать следующее. Только сразу все.

Если это число не будет простым.

Любого - означает что даже если оно само будет простым.

Вчера мы не сообразили, что есть же еще компромисс, а именно:
если таблицу всех простых чисел представить битовым полем, то до 65536 нужно 8к флеша. и это без RLE.

Вы на шаг приблизились к господину Сундараму.
Там именно карта флагов и используется (можно битовую)..
А если-бы Вы хотя-бы набрали в гугле "решето Сундарама", то узнали-бы, что для представления всех простых до 65536 нужно не 8К, а только 4К, о чём я и писал выше.
Можно и так конечно - посчитать эту таблицу решетом на компе, а прошить как есть во флешь.

[adnega]

Любого - означает что даже если оно само будет простым.

А какой толк от такого разложения?
В результате ведь нужно получить два числа так, чтобы их произведение равнялось некому числу,
а каждое было не более 16-бит, причем, если вариантов много, то нужен какой-то дополнительный критерий выбора?

Почему не подходит аппаратно-программный способ генерации частоты с точным делителем? Вопрос к ТС.