Если не жалко держать таблицу из 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.

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

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

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

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

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

Способ, который описал 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