Ну в инете ничего не могу конкретного по этому поводу найти. Нужны конкретные алгоритмы вычисления десятичного логарифма. Пожалуйста помогите!!! Дайте какие нибудь может ссылки в инете или не поленитесь напишите здесь. Вообще я не прогу буду писать, а это надо реализовать ПЛИС который будет вычислять т.е. разработать чип. Реализовывать буду на AlteraHDL. Но алгоритм можете давать и на С, паскале или еще чего нить... Вообще если нет конкретного алгоритма, то может математику этого подскажите... Вычисляемое число будет с фиксированной запятой.

Здравствуйте, vmaxx, Вы писали:

V>Ну в инете ничего не могу конкретного по этому поводу найти. Нужны конкретные алгоритмы вычисления десятичного логарифма. Пожалуйста помогите!!! Дайте какие нибудь может ссылки в инете или не поленитесь напишите здесь. Вообще я не прогу буду писать, а это надо реализовать ПЛИС который будет вычислять т.е. разработать чип. Реализовывать буду на AlteraHDL. Но алгоритм можете давать и на С, паскале или еще чего нить... Вообще если нет конкретного алгоритма, то может математику этого подскажите... Вычисляемое число будет с фиксированной запятой.

Хорошо, что с фиксированной.

Что деление — это, в сущности, вычитание — ты знаешь? Убедиться в этом можно, помедитировав над каким-нибудь примером деления столбиком. Так и извлечение корня, в сущности — деление. Это была лирика, ща расскажу алгоритм.

1. Берем число. Сравниваем его с 10.
2. Если больше 10, то
3.   делим его на 10.
4.   переходим к 1.
5. если меньше 10 (но больше 1!), то
6. запоминаем число делений на 10 (это будет целая часть логарифма) и идем дальше

7. Берем делитель (начать с 10**0.1), и сравниваем с ним число.
8. Если больше делителя, то
9.   делим его на делитель.
10.  переходим к 7.
11. если меньше делителя (но больше 1!), то
12. запоминаем число делений на делитель (это будет знак в мантиссе логарифма, соответсвующий делителю) и переходим к делителю, являющемуся корнем 10-й степени из предыдущещего.
13. преходим к 7.

Корень десятой степени вычисляется методом Ньютона. Я, впрочем, считал бы двоичный логарифм (двойка вместо 10-ки и корень второй степени) и потом множил на то, на что нужно множить.

Я мог ошибиться в конкретном виде алгоритма, но, надеюсь, не ошибся в идее. Это нужно проверить (алгоритм нужно отладить), сравнив с табличной функцией. Если есть вопросы по алгоритму — готов обсужлать.

Здравствуйте, vmaxx, Вы писали:

V>Ну в инете ничего не могу конкретного по этому поводу найти. Нужны конкретные алгоритмы вычисления десятичного логарифма. Пожалуйста помогите!!! Дайте какие нибудь может ссылки в инете или не поленитесь напишите здесь. Вообще я не прогу буду писать, а это надо реализовать ПЛИС который будет вычислять т.е. разработать чип. Реализовывать буду на AlteraHDL. Но алгоритм можете давать и на С, паскале или еще чего нить... Вообще если нет конкретного алгоритма, то может математику этого подскажите... Вычисляемое число будет с фиксированной запятой.

1. lg(x) = lg(e)*ln(x) В дальнейшем будем вычистлять натуральный логарифм.
2. Пусть число записано в нормализованной форме с плавающей точкой (как ее получить из фиксированной надеюсь объяснять не надо) x = m*2^n (m — мантисса, n — порядок). Тогда ln(x) = n*ln(2) + ln(m). Теперь найдем ln(m)
3. Пусть y = 1-m. ln(m) = ln(1-y) = -(y+y^2/2+y^3/3+...). Т.к. число было записано в нормализованной форме, то y <= 1/2. Т.е. ряд будет сходиться достаточно быстро.

Здравствуйте, vmaxx, Вы писали:

V>Ну в инете ничего не могу конкретного по этому поводу найти. Нужны конкретные алгоритмы вычисления десятичного логарифма. Пожалуйста помогите!!! Дайте какие нибудь может ссылки в инете или не поленитесь напишите здесь. Вообще я не прогу буду писать, а это надо реализовать ПЛИС который будет вычислять т.е. разработать чип. Реализовывать буду на AlteraHDL. Но алгоритм можете давать и на С, паскале или еще чего нить... Вообще если нет конкретного алгоритма, то может математику этого подскажите... Вычисляемое число будет с фиксированной запятой.

/**
   * Returns the natural logarithm (base <i>e</i>) of a <code>float</code>
   * value.
   *
   * @param   a   a number greater than <code>0.0</code>.
   * @return  the value ln&nbsp;<code>a</code>, the natural logarithm of
   *          <code>a</code>.
   */
  public static float ln(float x)
  {
    // compute offset

    int radix = 0;

    if (x == 0f)
    {
      return 0f; //NaN;
    }
    else if (x < .1f)
    {
      while(x < .1f)
      {
        radix--;
        x *= 10f;
      }
    }
    else
    {
      while (x > 10f)
      {
        radix++;
        x /= 10f;
      }
    }
    float r = (x - 3.1622776f)/(x + 3.1622776f);
    float r2=r*r;
    float mantissa = (((.21139497f*r2 +.15361371f)*r2+.29115068f)*r2+.86855434f)*r+.5f;
    return (float)((radix + mantissa) / 0.43429448190f);
  }

  public static final float E = 2.7182818284590452354f;
  public static final float LG_E = 0.43429448190325182f; 

  public static float lg(float x)
  {
    return LG_E * ln(x);
  }

Успехов.

Здравствуйте, vmaxx, Вы писали:

V>Ну в инете ничего не могу конкретного по этому поводу найти.
А здесь ?
Интересные соотношения + куча ключевых фамилий и всего такого.
Для быстроты можно посмотреть (если не изменяет память) интерполяция,полиномы Чебышева (?).По предварительно вычисленным табличным значениям интерполируем промежуточные точки.Должно быть очень быстро.

Здравствуйте, MichaelP, Вы писали:


Спасиб за ответ.
Тогда поидеи можно получить более быстрою скорость сходимости используя следующие:
ln((1+y)/(1-y)) = 2*(y + y^3/3 + y^5/5 + ...)
(1+y)/(1-y) = m => y = (m-1)/(m+1)
если: 0,5<=m<=1
тогда: -0,33..<=y<=0

Я правильно сделал?

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

Здравствуйте, Аноним, Вы писали:

А>ln((1+y)/(1-y)) = 2*(y + y^3/3 + y^5/5 + ...)
А>(1+y)/(1-y) = m => y = (m-1)/(m+1)
А>если: 0,5<=m<=1
А>тогда: -0,33..<=y<=0

А>Я правильно сделал?

А>Но я чего то не пойму как вычислять до определенной точности, т.е. сколько слагаемых взять чтобы получить точность до определенново знака?

Точность можно оценивать по (первому) отброшенному члену.

Практически же рекомендую использовать код с-smile-а. Это аппроксимация полиномом, причем, видимо, дающая нужную точность. Можно провериь соотношением log(a*b) = log(a) + log(b).

Думал я над этим алгоритмом, но не совсем понял. Во первых получается, что натуральный логарифм вычисляется фактически в этой части:

float r = (x - 3.1622776f)/(x + 3.1622776f);
float r2=r*r;
float mantissa = (((.21139497f*r2 +.15361371f)*r2+.29115068f)*r2+.86855434f)*r+.5f;
return (float)((radix + mantissa) / 0.43429448190f);

Здесь видно, что просто вычисляется несколько членов определенного ряда. Что это за разложения я не очень понял. Неподскажите какое разложение здесь используется? Также ну никак непойму откуда все эти числа взялись, как вычислялись? Почему взято именно столько знаков в этих числах?
Вообще хотелось бы алгоритм который мог вычилять с точностью до заданного знака. Как это можно сделать?

Здравствуйте, vmaxx, Вы писали:

V>

V>float r = (x - 3.1622776f)/(x + 3.1622776f);
V>float r2=r*r;
V>float mantissa = (((.21139497f*r2 +.15361371f)*r2+.29115068f)*r2+.86855434f)*r+.5f;
V>return (float)((radix + mantissa) / 0.43429448190f);
V>

V>Здесь видно, что просто вычисляется несколько членов определенного ряда. Что это за разложения я не очень понял. Неподскажите какое разложение здесь используется? Также ну никак непойму откуда все эти числа взялись, как вычислялись?

Аппроксимация полиномом. Методом наименьших квадратов.

V>Почему взято именно столько знаков в этих числах?

Не знаю. Работает? Проверь, что log(a*b) = log(a)*log(b)

V>Вообще хотелось бы алгоритм который мог вычилять с точностью до заданного знака. Как это можно сделать?

Тебе уже дали два.

Спасиб за ссылочку. На это чего то мой поиск не привел.
Я посмотрел вкратце чего там, вроде вычисляется ln2, и алгоритмы специально рассчитанные именно на это, может конечно и можно из них получить и для произвольного числа. Но математику совсем забыл...

Здравствуйте, vmaxx, Вы писали:

V>Думал я над этим алгоритмом, но не совсем понял. Во первых получается, что натуральный логарифм вычисляется фактически в этой части:

V>

V>float r = (x - 3.1622776f)/(x + 3.1622776f);
V>float r2=r*r;
V>float mantissa = (((.21139497f*r2 +.15361371f)*r2+.29115068f)*r2+.86855434f)*r+.5f;
V>return (float)((radix + mantissa) / 0.43429448190f);
V>

V>Здесь видно, что просто вычисляется несколько членов определенного ряда. Что это за разложения я не очень понял. Неподскажите какое разложение здесь используется? Также ну никак непойму откуда все эти числа взялись, как вычислялись? Почему взято именно столько знаков в этих числах?
V>Вообще хотелось бы алгоритм который мог вычилять с точностью до заданного знака. Как это можно сделать?

Вроде бы разобрался откуда в этой программе ноги растут.

Сначала немного математики:

log(k*(1-y)/(1+y)) = log(k) + log((1-y)/(1+y)).

Теперь если положить y=(m-k)/(m+k), то получим log(k) + log((1-y)/(1+y)) = log(m).

Зачем же нужен множитель k?

Заметим, что ф-ция log((1-y)/(1+y)) — антисимметрична. Т.е если мы имеем хорошее приближение этой функции в интервале [0, y0], то точно такую же точность мы обеспечим в интервале [-y0,0]

Теперь предположим, что m распределена в интервале [1,a]. Из вышесказанного очевидно, что нам выгодно, чтобы результирующий диапозон y был симметричен относитлено 0. Этого мы можем добиться положив k = sqrt(a).

Например: Если интервал для m [1/2,1], то интервал для хорошего приближения сужается до [0, 0.17...], в то время как прямое применнение log((1-y)/(1+y)) приводит к интервалу [0, 0.33...]

Я сознательно не обращал внимания на оснвание логарифма, т.к. логарифмы по разным основаниям отличаются друг от друга умножением на константу и, следовательно, неважно какой из логарифмов мы будем приближать. Измениться может только точность, с которой нам надо приближать log((1-y)/(1+y)), но для разумных оснований логарифмов (e, 2, 10) это не очень существенно.

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

3.1622776 = sqrt(10), 0.5 = lg(sqrt(10)) Все остальное это коэф-ты аппроксимирующего многочлена.

Последний вопрос:
Как найти приближение ф-ции log((1-y)/(1+y)) на интервале [0, 0.17...] с заданной точностью?

Тут советую применить аппроксимацию Чебышева, которая много где описана.

Спасиб за алгоритм. Идея вроде ясна, и вроде это работает. На сях понятно как сделать, но как мне это реализовывать на микросхеме программируемой логики пока не очень ясно... Но собственно это вопрос уже я думою не к тебе