Рассчитайте логарифм вручную - PullRequest
Новая
       30

Рассчитайте логарифм вручную

0 голосов
/ 14 мая 2018

Я бы хотел вычислить математический логарифм"от руки" ...

... где обозначает logarithmBase и обозначает значение.

Некоторые примеры (см. Журнал калькулятора ): 

The base 2 logarithm of 10 is 3.3219280949

The base 5 logarithm of 15 is 1.6826061945

...

Однако - я не хочу использовать уже реализованный вызов функции, такой как Math.ceil, Math.log, Math.abs, ..., потому что я хочу чистое нативное решение, которое работает только с +-*/ и некоторыми циклами.

Этоэто код, который я получил до сих пор: 

function myLog(base, x)  {
  let result = 0;
  do {
    x /= base;
    result ++;
  } while (x >= base)
  return result;
}

let x = 10,
    base = 2;

let result = myLog(base, x)
console.log(result)
* 1033.код был бы очень признателен.

Спасибо, миллион заранее авансом.

Ответы [ 2 ]

0 голосов
/ 15 мая 2018

Первый метод: с таблицей констант.

Сначала нормализуйте аргумент числом от 1 до 2 (это достигается путем умножения или деления на 2 столько раз, сколько необходимо- вести учет этих операций).Для эффективности, если значения могут охватывать много порядков, вместо равных факторов вы можете использовать квадрат в квадрате 2, 4, 16, 256 ... с последующим дихотомическим поиском, когда вы заключили в скобки значение.

Fi, если показатели 16 = 2 ^ 4 работают, но не 256 = 2 ^ 8, вы пытаетесь 2 ^ 6, затем один из 2 ^ 5 и 2 ^ 7 в зависимости от результата.Если конечный показатель равен 2 ^ d, линейный поиск требует O (d) операций, а геометрический / дихотомический поиск - только O (log d).Чтобы избежать делений, желательно вести таблицу отрицательных сил.

После нормализации вам необходимо уточнить мантиссу.Сравните значение с √2, а если больше, умножьте на 1 / √2.Это приносит значение между 1 и √2.Затем сравните с √√2 и так далее.По ходу дела вы добавляете веса 1/2, 1/4, ... к показателю степени, когда сравнение возвращает большее значение.

В конце, показателем степени является логарифм с основанием 2.

Пример: lg 27 

27 = 2^4 x 1.6875

1.6875 > √2 = 1.4142 ==> 27 = 2^4.5 x 1.1933

1.1933 > √√2 = 1.1892 ==> 27 = 2^4.75 x 1.0034

1.0034 < √√√2 = 1.0905 ==> 27 = 2^4.75 x 1.0034

...

Истинное значение 4,7549.

Обратите внимание, что вы можете работать с другими базами, в частности e.В некоторых контекстах база 2 позволяет использовать ярлыки, поэтому я и использовал ее.Конечно, квадратные корни должны быть сведены в таблицу.

Второй метод: с серией Тейлора.

После шага нормализации можно использовать стандартную серию 

log(1 + x) = x - x²/2 + x³/3 - ...

, который сходится для |x| < 1.(Предостережение: теперь у нас есть натуральные логарифмы.)

Поскольку сходимость слишком медленная для значений, близких к 1, рекомендуется использовать вышеуказанный метод для уменьшения до диапазона [1, √2).Затем каждый новый термин приносит новый бит точности.

Кроме того, вы можете использовать ряд для журнала ((1 + x) / (1 - x)), что дает хорошую скорость сходимости даже для аргумента2. См. https://fr.wikipedia.org/wiki/Logarithme_naturel#D%C3%A9veloppement_en_s%C3%A9rie

Пример: с x = 1,6875, y = 0,2558 и 

2 x (0.2558 + 0.2558³/3 + 0.2558^5/5) = 0.5232

lg 27 ~ 4 + 0.5232 / ln 2 = 4.7548
0 голосов
/ 14 мая 2018

Вы можете использовать рекурсивный подход: 

 const log = (base, n, depth = 20, curr = 64, precision = curr / 2) => 
   depth  <= 0 || base ** curr === n 
      ? curr
      : log(base, n, depth - 1, base ** curr > n ? curr - precision : curr + precision, precision / 2);

Используется как: 

log(2, 4) // 2
log(2, 10) // 3.32196044921875

Вы можете повлиять на точность, изменив depth, и вы можете изменить диапазон принятых значений (в настоящее время ~ 180) с помощью curr

Как это работает:

Если мы уже достигли желаемой глубины или если мы уже нашли точное значение: 

 depth  <= 0 || base ** curr === n

Тогда он просто возвращает curr и готово. В противном случае он проверяет, является ли логарифм, который мы хотим найти, ниже или выше текущего: 

         base ** curr > n

Затем он продолжит поиск значения рекурсивно 1) понижение depth на один 2) увеличение / уменьшение curr с текущей точностью 3) низкая точность

Если вы ненавидите функциональное программирование, вот императивная версия: 

  function log(base, n, depth = 20) {
   let curr = 64, precision = curr / 2;
   while(depth-- > 0 && base ** curr !== n) {
     if(base ** curr > n) {
       curr -= precision;
     } else {
       curr += precision;
     }
     precision /= 2;
    }
    return curr;
  }

Кстати, используемый мной алгоритм называется "логарифмический поиск" , широко известный как "бинарный поиск".

...