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.

Вчера мы не сообразили, что есть же еще компромисс, а именно:
если таблицу всех простых чисел представить битовым полем, то до 65536 нужно 8к флеша. и это без RLE.
А функция распределения простых числел https://ru.wikipedia.org/wiki/%D0%A4%D1%83%...%81%D0%B5%D0%BB
так и шепчет его применить.

upd

Код

def prime_nums(N):
    return reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
        if (x in r) else r), range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))
        
aList= prime_nums(256**2)
nprims=len(aList)
print "//found {0} prime numbers".format(nprims)
#create u32-bitmap
u32bmp=[]
u32bmp[:]= [0 for j in xrange(65536/32)]
#map to
for nn in aList:
    u32bmp[nn/32] |= 1 << (nn % 32)
print "static const uint32_t prime_set[]={"
col = 0
ss=''
for nn in u32bmp:
    print "0x%08X," % nn
print "};"

8кб
дальше я не соображаю, как его топтать.
Может кто напишет?
Или хотя бы проверит, правильно ли работает?
upd2 -поменял вывод, а то некрасиво

Сообщение отредактировал _Pasha - May 22 2015, 04:32