Табулирование пары сотен-другой простых чисел и перебор по ним?

http://e-maxx.ru/algo/factorization

Долговато будет. Скажем, если получили на входе простое число, то нужно будет сначала проверить его, потом одно ближайшее четное, потом другое (если первое не позволяет получить множители меньше 65536)...

Похоже, ничего надежного и шустрого нет ☹

Я не совсем понял конечную цель, но может оказаться полезным знаменитое дерево:

The Stern–Brocot tree was discovered independently by Moritz Stern (1858) and Achille Brocot (1861). Stern was a German number theorist; Brocot was a French clockmaker who used the Stern–Brocot tree to design systems of gears with a gear ratio close to some desired value by finding a ratio of smooth numbers near that value.

И соответсвующие методы аппроксимации.

P.S. Было бы неплохо расшифровать, что такое предмножитель. Ну можно ещё ссылкой кинуть.

Было бы неплохо расшифровать, что такое предмножитель. Ну можно ещё ссылкой кинуть

http://samou4ka.net/page/tajmer-schetchik-mikrokontrollerov-avr

там где про выбор тактирования - это и есть предмножитель, т.е. частота понижается - счет замедляется

У тебя хардварный контроллер шаговика или ты GPIO дёргаешь по прерываниям? Если второе, что мешает на лету реконфигурировать таймер, чтобы он 99 раз переполнялся на 655, а в 100-й на 666 (или сколько тебе там надо до конца периода)?

У меня аппаратный контроллер, который имеет входы "направление" и "такт". В прерываниях таймера я считаю шаги, а для тактирования тупо ШИМ генерируется.

что мешает на лету реконфигурировать таймер

Будет неравномерность хода.

Очень просто:

Пусть надо получить интервал A. Если A < 65536, берем A. Иначе берем N = ]A div 65536[ + 1, где ][ - целая часть сверху. В окрестности размера ]N/2[ от A существует хотя бы одно число B, делящееся на N. Берем предмножитель N и таймаут B/N.

Это, конечно, если я правильно понял, как работает «предмножитель».

Тоже сложноватый для мелкоконтроллера алгоритм. А предмножитель — это 16-битный регистр, тактирующий вход таймера. Т.е. схема такая: 72МГц системной шины мелкоконтроллера идет на вход частотозадающей цепочки (просто каждый такт вычитается единица из регистра предмножителя, а как только он обнуляется, пинается вход таймера, в регистр опять загружается значение из регистра PSC). Импульсы, поступающие на вход таймера, аналогично декрементируют регистр счетчика (тоже 16 бит). Как только счетчик обнуляется, генерируется прерывание переполнения, а в счетчик заносится содержимое регистра ARR.

Т.е. по сути период таймера (естественно, с точностью до погрешности кварца) в микросекундах определяется как

(PSC+1)*(ARR+1)/72

Вот я и думал как бы попроще для любого заданного периода вычислить PSC и ARR, чтобы уменьшить погрешность результирующего периода.

Будет неравномерность хода.

Я имел в виду сделать программный делитель частоты. То есть вместо аппаратного деления частоты на 100 завести переменную, которая во время прерывания декрементируется, проходя от 100 до 0. При нулевом значении подстраивается счётчик на один период, учитывается шаг, дёргается GPIO для тактирования шаговика (вместо ШИМ), а переменная-делитель снова устанавливается на 100 и опять тикает до 0 (не забыть где-нибудь в это время вернуть GPIO обратно).

Числа в каких пределах надо раскладывать на простые множители?

Вот кстати интересно, верно ли утверждение, что любое составное число N представимо в виде произведения двух натуральных чисел, меньших чем N? Если верно(очевидно что верно), на основе этого можно достаточно эффективную таблицу поиска сделать. Число или ссылается на два других числа, или само является простым.

Например для чисел меньших 255 делаем структурку вида {unsigned char a, unsigned char b}. И если надо факторизовать число 176 (оно раскладывается на 2 2 2 2 11) то делаем структурку {8, 22} (т.е. 2*2*2 и 2*11). Ну и потом разкладываем 8 и 22 на простые множители, и так рекурсивно, пока не дойдем до одних простых чисел. Если само наше число само является простым, в структуру вписываем {0, 0}

так как все таймеры 16-битные с 16-битным предмножителем, любые периоды задать, понятное дело, не выйдет.

с чего бы? хранить сотни тысяч в отдельной переменной, не?

Думаю, что проблема ещё в том, что он может задать лишь тот период, который получится целочисленным делением. Объясню на пальцах: допустим, у нас тактовая частота 1 кГц. Мы можем легко получить на выходе 10, 20, 50 и т. п. Гц, потому что существует целое число, на которое можно поделить тактовую частоту. А вот, скажем 40 Гц получить проблематично, потому что 1000 на 40 не делится нацело.

Насколько я помню схему тактирования UART в MSP430, там применялась следующая аппаратная фишка, чтобы получить точную частоту UART при некратных частотах кварца - применялся некий паттерн тактирования. Вроде того, что все такты используют предделитель 100, а каждый 3-ий - 99. В даташите даже была куча таблиц и схем, показывающих как это работает.

Я думаю это вполне допустимо и в этой ситуации, с учётом того, что у шаговика самого есть погрешность шага порядка 5% (разве что у ТС какие-то очень дорогие и прецезионные шаговики), так что неравномерность будет в любом случае, но если менять предделитель, то можно избежать накопления рассогласования.

Понял, значит задача — разложить число на два более-менее близких множителя. Полно готовых решений для обычного разложения на множители, но для приблизительного не знаю, к сожалению.

Есть наколеночный вариант примерно следующего содержания. Мы хотим приближённо разложить N на два множителя, но эту задачу можно решить, решив N = a^2 - b^2. То заменяем задачу разложения на два множителя задачей представления разностью квадратов. Одна к другой сводится элементарно: N = a^2 - b^2 = (a - b) (a + b).

В качестве пробного a можно взять что-нибудь а-ля a = ceil(sqrt(N)), при этом наилучшее b = round(sqrt(a^2 - N)). Я прогнал такой вариант на N = 2^16 .. 2^20, максимальная погрешность при этом 0.03%. Хреново. Даже если пробовать искать среди a = ceil(sqrt(N)) .. ceil(sqrt(N)) + p (где p — какое-то число типа 10-20), всё равно относительная погрешность даже ниже 0.02% не опускается.

Глядя на эти потуги, рекомендую для всех N >= 2^16 просто делить N на наименьшую степень двойки, которая в результате даст число меньшее 2^16, то есть ceil(log(N / 65536)). Тогда относительная погрешность будет максимум 2^(-16), что есть 0.0015%.

Такие дела.

Понял, значит задача — разложить число на два более-менее близких множителя

А почему «более-менее близких» именно?

Кстати, я выше предложил алгоритм, похожий на последний способ, только у меня там не обязательно степень двойки, а просто целое число. Чем он хуже/лучше?

А почему «более-менее близких» именно?

Я тупо сформулировал. Это требование совершенно лишнее.

Кстати, я выше предложил алгоритм, похожий на последний способ, только у меня там не обязательно степень двойки, а просто целое число. Чем он хуже/лучше?

Я его не понимаю :) Пусть N — исходное число (больше 65536), возьмём: a = ceil(N / 65536), b = round(N / a), в качестве разложения получается a * b. Если твой вариант делает это же, то это, похоже, лучшее, что можно предложить. Я совершенно зря выше в дебри полез.

Ну так да, то же самое и есть, только я привык к математическим обозначениям, а не к сишным функциям :)

Будь здесь ТеХ'овские формулы — ОК, но их нет.

Берем предмножитель = 1. (Начало цикла) Смотрим период, если он >65535 то делим его на 2(сдвигаем вправо), а предмножитель умножаем на 2 (сдвигаем влево). Повторяем, пока период не будет <=65535. (Конец цикла) Погрешность будет всегда меньше 1/65535.

Все гениальное просто

Спасибо!

Ну я и осел!

Хоть этот способ и не даст точного разложения (скажем, если взять 1234321 == 1111², то получим A=38572 и B=32, A*B=1234304), погрешность все равно получается намного меньше моего способа (в данном примере всего-то 0.0014%!)