Сплош и рядом математика, помогите кто чем может Опции

[UniBomb]

Я наверно, как впрочем и все, наткнулся на вопрос реализации математических функций в мк. Так вот, в данный момент мне позарез нужно вычислять натуральный логарифм шестнадцатиразрядного числа. Если у кого есть наработки, то прошу поделиться...


ЗЫ:. кстати говоря, пусть эта тема будет несколоко универсальной - пусть здесь выкладываюстся алгоритмы математических операций и функций (желательно на асме... атмеловском)...

[Yura_K]

А может просто глянуть Кнута?

[zltigo]

А может просто глянуть Кнута?

Нет, если "просто", то это log() и все :-).

[Atashi]

если говорить о ЛЮБЫХ функциях, то проМММблематично...
а вообще-то обычно можно разложить в ряд, а ряд описать алгоритмически - и опять Кнут! Мафия какая-то.

[LordN]

неплохие примеры разных вычислений есть тут http://lord-n.narod.ru/walla.html#MudrovPEVM

[trablik]

Как вариант еще можно заранее составить массив со значениями функции в отдельных точках, а потом вычислять значение этой функци в произвольной точке с помощью интерполяции.

[UniBomb]

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

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


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

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

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

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

[zltigo]

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

Прилинковать библиотечную функцию что не позволяет? Хочется переплюнуть по размеру и скорости
не имея опыта в данном деле?

[trablik]

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]

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]

и я думаю что ты догадался почему

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

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

А собственно _алгоритм_ можете посмотреть именно в исходниках (например 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+ = 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]

vladv, надо будет запомнить, спасибо.... правда памяти у меня всего 512 байт... а ведь где то надо ещё и конфигурациоонные настройки сохранить...

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

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

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

[Yura_K]

Насчет ссылок по Д. Кнуту:
Том 1. Основные алгоритмы.
Том 2. Получисленные алгоритмы
Том 3. Сортировка и поиск

[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 увеличивает время выполнения первого шага и уменьшает время третьего.

Сообщение отредактировал CD_Eater - Jul 15 2006, 11:58