Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Сплош и рядом математика
Форум разработчиков электроники ELECTRONIX.ru > Микроконтроллеры (MCs) > AVR
UniBomb
Я наверно, как впрочем и все, наткнулся на вопрос реализации математических функций в мк. Так вот, в данный момент мне позарез нужно вычислять натуральный логарифм шестнадцатиразрядного числа. Если у кого есть наработки, то прошу поделиться...


ЗЫ:. кстати говоря, пусть эта тема будет несколоко универсальной - пусть здесь выкладываюстся алгоритмы математических операций и функций (желательно на асме... атмеловском)...
Yura_K
А может просто глянуть Кнута?
zltigo
Цитата(Yura_K @ Jul 8 2006, 21:11) *
А может просто глянуть Кнута?

Нет, если "просто", то это log() и все :-).
Atashi
если говорить о ЛЮБЫХ функциях, то проМММблематично...
а вообще-то обычно можно разложить в ряд, а ряд описать алгоритмически - и опять Кнут! Мафия какая-то.
LordN
неплохие примеры разных вычислений есть тут http://lord-n.narod.ru/walla.html#MudrovPEVM
trablik
Как вариант еще можно заранее составить массив со значениями функции в отдельных точках, а потом вычислять значение этой функци в произвольной точке с помощью интерполяции.
UniBomb
по повду кнута - чего то я часто вижу этого автора на страницах форума, но ни одной ссылки на него... если бы был кнут, то я обязательно его глянул бы... Yura_K, может кинеш линк на него?

zltigo - зачот, но к теме не относится...


Atashi, действительно...

LordN, я так понимаю, что сайт - это твоё детище... как говорится охайо, обязательно гляну...

trablik, эта мысль приходила и мне в голову, но есть несколько но - прибор у меня конечно же не прецизионный, но точность мне необходима большая, а следовательно и такихзначений будет свыше трёх тысяч.... что не то что в микрокотроллере сохранить, а вообще просчитать (бех автоматизиции есессно) сложновато...

всем спазибо за отклики... тема считается открытой для дальнейших обсуждений...
zltigo
Цитата(UniBomb @ Jul 9 2006, 21:28) *
zltigo - зачот, но к теме не относится...

Прилинковать библиотечную функцию что не позволяет? Хочется переплюнуть по размеру и скорости
не имея опыта в данном деле?
trablik
Цитата(UniBomb @ Jul 9 2006, 22:28) *
trablik, эта мысль приходила и мне в голову, но есть несколько но - прибор у меня конечно же не прецизионный, но точность мне необходима большая, а следовательно и такихзначений будет свыше трёх тысяч.... что не то что в микрокотроллере сохранить, а вообще просчитать (бех автоматизиции есессно) сложновато...

по поводу необходимости более трёх тысяч значений
- не обязательно всё делать в лоб. Если вспомнить из математики формулу ln( a*b )=ln( a )+ln( b ), то задачу можно существенно упростить, раскладывая аргумент логарифма на множители.
Поясню на примере. Пусть требуется вычислить ln(123456.789).
Решение: ln(123456)=ln(10*10*10*10*10*1.23456789)= ln(10)+ln(10)+ln(10)+ln(10)+ln(10) + ln(1.23456789)=5*ln(10)+ ln(1.23456789)
Константу ln(10) монжо вычислить заранее с высокой точностью. Таким образом, для вычисления логарифма любого числа потребуется знание константы ln(10) и вычисление логарифма числа на отрезке от 1 до 10, а это гораздо проще.
Примечание. В случае чисел меньших 1 для приведения их к диапазону 1..10 нужно не прибалять, а вычитать ln(10).
UniBomb
zltigo, опять зачот... но снова нето... нету библиотечной функции... я работаю в среде AVRStudio, использующий язык assembler... максиму что есть из готовых функций - это восьмиразрядное умножение...

trablik, мысль дельная.... обязательно её завтра обсосу... в плане обдумаю...

продолжаем обсуждение...
zltigo
Цитата(UniBomb @ Jul 9 2006, 23:27) *
zltigo, опять зачот... но снова нето... нету библиотечной функции... я работаю в среде AVRStudio, использующий язык assembler...

А что, объектные файлы студийный ассемблер исключительно собственного формата генерит и его линкер ничего кроме них не переваривает? Если не обе этих проблемы сразу, то можно и постороннюю прилинковать.

В общем слинковать через конвертер ELF можно:


Installing and using AVRGCC with AVRstudio
This is a comprehensive introduction on how to install AVRstudio and and the GNU AVR C
compiler “avr-gcc”, and making them work together. This introduction leads step by step to the
successful build of sample code, and programming of whichever AVR part you have chosen, on the
STK500 development board.
Used in this introduction:
• AVRstudio executable installer, “astudio.exe” release 3.53 of nov.8, 2001[5.9M] or later.
Downloadable from www.avrfreaks.net
• AVRGCC executable installer “avrgcc200112XXa_AVRfreaks.exe” [8.1M], AVRfreaks
distribution of dec.07, 2001 or later.
This package also contains:
• Flavio Gobber’s Elf2Coff converter. • The gcctest 1-9 files, by Volker Oth.
Downloadable from www.avrfreaks.net. It is important that you try to use our package, as it
contains all the correct additional files (.bat files, makefiles) that you need to complete this
guide).
UniBomb
zltigo, мои объяснения почему и это не подходит будут настолько нелепыми (и я думаю что ты догадался почему), что я их не буду озвучивать...

неужели никто не владеет алгоритмом высчитывания логаифма, если не атурального, то хоть бы десятичного?....
zltigo
Цитата(UniBomb @ Jul 10 2006, 15:39) *
и я думаю что ты догадался почему

Да и даже прямо написал это в одном из предыдущих постов.

Цитата
неужели никто не владеет алгоритмом высчитывания логаифма

А собственно _алгоритм_ можете посмотреть именно в исходниках (например GCC) той самой библиотечной log() функции.
KKN
Может стоит разложить логарифм в ряд. Задаться точностью и решить до какого члена ряда считать.
Разложение см. http://ru.wikipedia.org/wiki/%D0%9B%D0%BE%...%BD%D0%B8%D0%B5
Внизу в замечаниях.
UniBomb
zltigo, я напишу тебе в личку..

KKN, в принципе если посидеть над этим пару дней с учебником, то что-нибудь получится, но в этом случае получится довольно грамоздкая система и время на подсчёт функции будет довольно большим (при относительно малой производительности мк). поэтому в данной задаче выбор делается в пользу быстроты. я и так пытюсь "убыстрить" этот процесс отказавшись от вещественных чисел в пользу 16-ти разрядных целочисленных....
vladv
Если не жалко держать таблицу из 256 значений, то можно так.
Для определенности будем считать, что в вычислении ln(x), x это 16-бит целое число.
(если х - дробное с фиксированной точкой, то результат просто смещается на -N*ln(2),
где N - кол-во дробных бит)

1. Сдвигаем x влево до первой значащей единицы:
X = x << K //К - число старших нулей//
и вычисляем:
Y1 = -K*ln(2)

2. Представляем:
X = 256*A+B //т.е. A и B - старший и младший байты числа X//

3. Ищем по таблице:
Y2 = TAB(A)
где:
TAB(A) = 8*ln(2)*ln(A) - таблица из 256 заранее расчитанных значений (здесь же можно
учесть -N*ln(2) для дробного x: TAB(A) = 8*ln(2)*ln(A)-N*ln(2) )

4. Вычисляем:
Y3 = B/A

5. Собираем результат:
ln(x) = Y1 + Y2 + Y3/256


"Теория метода":
ln(x) = ln(X * 2**(-K)) = -K*ln(2) + ln(X) = Y1 + ln(X)
ln(X) = ln(256*A+cool.gif = ln(256*A) + ln(1+B/(256*A)) = 8*ln(2)*ln(A) + ln(1+B/(256*A)) =
= Y2 + ln(1+B/(256*A))
ln(1+B/(256*A)) ~ B/(256*A) = Y3/256 //с точностью не хуже 14 дробных бит!!!//

Тут есть относительно трудоемкая операция B/А, но (если не ошибаюсь) например для
вычисления 16-бит значения ln(x) при целом 16-бит x достаточно знать 4 старших бита B/A.
UniBomb
vladv, надо будет запомнить, спасибо.... правда памяти у меня всего 512 байт... а ведь где то надо ещё и конфигурациоонные настройки сохранить...
vladv
Цитата(UniBomb @ Jul 11 2006, 20:02) *
vladv, надо будет запомнить, спасибо.... правда памяти у меня всего 512 байт... а ведь где то надо ещё и конфигурациоонные настройки сохранить...


512 байт - это памяти команд?

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

Еще можно разменять размер таблицы на число допонительных делений. Например, для таблицы
в 8 значений, надо будет сделать 4 деления (а также несколько сложений/вычитаний и сдвигов).
Деления можно заменить еще одной таблицей такого-же размера и умножением. Если кому
интересно - дайте знать.
CD_Eater
Способ, который описал vladv, фактически оптимизирован по скорости вычисления. Если же нужно сэкономить память (в ущерб скорости), можно воспользоваться вычислением "в лоб".

Логарифм - функция, очень хорошая в том смысле, что при разложении в ряд нет необходимости заботиться о сходимости в широких пределах (как правило, для синуса необходима сходимость от 0 до pi/2). Можно выбрать малый интервал от 1 до (1+eps), в котором ряд для логарифма (по ссылке в википедии) сходится с достаточной точностью вычислением малого количества членов. А дальше - умножая исходное число на некоторую целую степень (1+eps), можно попасть в выбранный интервал.

То есть, потребуется числа (1+eps) и ln(1+eps) вычислить заранее и хранить как константы, а в процессе вычислений:
1) Вычисляя целые степени числа (1+eps), найти такую целую степень N, которая максимально приблизится к исходному числу X (например, выполнять поиск N методом деления отрезка пополам)
2) Разделить X на (1+eps)^N, получив число Y из диапазона 1..(1+eps)
3) Вычислить сумму ряда ln(Y)
Далее - вычисляем ln(X) = N*ln(1+eps) + ln(Y)

В памяти - никаких таблиц. Количество членов ряда и число eps выбираются исходя из требуемой точности и из соображений одинакового времени вычислений на первом и третьем шагах (чтобы минимизировать общее время вычислений), т.к. уменьшение eps увеличивает время выполнения первого шага и уменьшает время третьего.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.