[Перевод] Устали от глупых шуток о JS? Напишите свою библиотеку26.12.2020 17:33

В JavaScript есть немало моментов, вызывающих вопрос «Чего???». Несмотря на то что у большинства из них есть логическое объяснение, если вы вникнете, они всё равно могут удивлять. Но JavaScript точно не заслуживает возмутительных шуток типа этой смеха. Например, иногда мы видим такие шутки:

buzygp2yrzz9bfh4y_4dl6w77-i.jpeg


В этом случае критика абсолютно не заслужена. Давайте разбираться почему.

JavaScript, как и какой-либо другой популярный язык программирования, представляет числа, использующие единый стандарт. Если быть точным, это стандарт IEEE 754 для чисел в 64-битном двоичном формате. Давайте попробуем проверить эту же шутку на других языках:

Как насчёт Ruby? На каком языке 0.1 + 0.2 не равно 0.3? 

$ irb
irb(main):001:0> 0.1 + 0.2 == 0.3
=> false
irb(main):002:0> 0.1 + 0.2
=> 0.30000000000000004


Ruby! Какой глупый язык.

Или Clojure? На каком языке 0.1 + 0.2 не равно 0.3? 

$ clj
Clojure 1.10.1
user=> (== (+ 0.1 0.2) 0.3)
false
user=> (+ 0.1 0.2)
0.30000000000000004


Clojure! Какой глупый язык.

Или как насчёт могучего Haskell? На каком языке 0.1 + 0.2 не равно 0.3? 

$ ghci
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
Prelude> 0.1 + 0.2 == 0.3
False
Prelude> 0.1 + 0.2
0.30000000000000004


Haskell! Хахаха. Какой глупый язык…

Вы поняли мысль. Проблема здесь не в JavaScript. Это большая проблема представления чисел с плавающей точкой в двоичном виде. Но я не хочу пока вдаваться в подробности IEEE 754. Потому что, если нам нужны произвольные точные числа, JavaScript делает их возможными. С октября 2019 года BigInt официально входит в стандарт TC39 ECMAScript.

Зачем беспокоиться об этом?


Мы продержались с IEEE 754 целую вечность. Большую часть времени это не кажется проблемой. Правда. Почти всегда это не проблема. Но иногда это всё-таки проблема. И в такие моменты хорошо иметь варианты.

Например, в начале этого года я работал над библиотекой диаграмм. Хотел нарисовать свечные графики на SVG. А в SVG есть такая аккуратная функция, называемая transform. Вы можете применить её к группе элементов, и она изменит систему координат для этих элементов. Так что с небольшой осторожностью вы можете упростить генерацию области диаграммы. Вместо того чтобы вычислять координаты графика для каждой свечи, вы указываете одно преобразование. А затем определяете каждую свечу, используя значения сырых данных. Очень аккуратно. По крайней мере в теории.

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

Класс дроби


Проблема с числами с плавающей точкой — их двоичное представление. Компьютеры выполняют все свои вычисления в двоичном виде. И для целых чисел эта двоичность подходит. Проблема приходит, когда мы хотим представить десятичные числа. Например, в англоязычных странах, таких как Австралия, мы пишем десятичные числа следующим образом:

$3.1415926$


Часть слева от точек (…) — это целая часть, а справа от точки — дробная часть. Но проблема в том, что некоторые числа имеют дробные части, которые нелегко разделить на две. Так что их трудно представить в двоичном виде. Но та же проблема возникает при основании 10. Например дробь 10/9. Можно попробовать написать что-нибудь вроде этого:

$1.111111111111111111111111111111111111.11111111111111111111111111111111111$


Однако это приближение. Чтобы представить 10/9 точно, единицы должны быть бесконечными. Поэтому мы должны использовать какую-то другую нотацию для представления повторяющихся. Например такую:

$1.\dot{1}$

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

Заметьте, что 10/9 имеет идеальную точность. И всё, что нужно для точности, — это два кусочка информации. Это числитель и знаменатель. С помощью одного значения BigInt мы можем представлять произвольно большие целые числа. Но если мы создадим пару из целых чисел, то сможем представлять произвольно большие или маленькие числа.

В JavaScript это может выглядеть так: 

// file: ratio.js
export default class Ratio {
  // We expect n and d to be BigInt values.
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }
}


Итак, мы проделали самую хитрую часть. «Изобрели» способ представления чисел с почти бесконечной точностью. (Мы все еще ограничены объемом памяти наших устройств.) Осталось только применить математику. Так что давайте добавим функциональности.

Равенство


Первое, что хочется сделать, — это сравнить две дроби. Зачем? Потому, что мне нравится сначала писать тесты. Если я могу сравнить две дроби на равенство, то писать тесты намного проще.

В простом случае написать метод равенства довольно легко: 

// file: ratio.js
export default class Ratio {
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }

  equals(other) {
    return (
      this.numerator === other.numerator &&
      this.denominator === other.denominator
    );
  }
}


Вот и хорошо. Но было бы неплохо, если бы наша библиотека могла сообщить, что ½ равна 2/4. Для этого нужно упростить дробь. То есть, прежде чем проверять равенство, мы хотим уменьшить числители и знаменатели обеих дробей до как можно более маленьких чисел. Итак, как мы сделаем это?

Наивный подход заключается в прогоне всех чисел от 1 до min (n, d) (где nn и dd — числитель и знаменатель соответственно). И это то, что я попробовал вначале. Код выглядел как-то так: 

function simplify(numerator, denominator) {
    const maxfac = Math.min(numerator, denominator);
    for (let i=2; i<=maxfac; i++) {
      if ((numerator % i === 0) && (denominator % i === 0)) {
        return simplify(numerator / i, denominator / i);
      }
    }
    return Ratio(numerator, denominator);
}


И, как и следовало ожидать, он невероятно медленный. Мои тесты заняли вечность. Так что нам нужен более эффективный подход. К счастью, греческий математик нашел его пару тысячелетий назад. Решение — применение алгоритма Евклида. Это способ найти наибольший общий делитель двух целых чисел.

Рекурсивная версия алгоритма Евклида красива и элегантна: 

function gcd(a, b) {
    return (b === 0) ? a : gcd(b, a % b);
}


Применима мемоизация, что делает алгоритм довольно привлекательным. Но, увы, у нас еще нет хвостовой рекурсии в V8 или SpiderMonkey. (По крайней мере не на момент написания статьи.) Это означает, что если мы запустим его с достаточно большими целыми числами, то получим переполнение стека. А большие целые числа — это что-то вроде точки отсчёта.

Так что вместо этого воспользуемся итерационной версией: 

// file: ratio.js
function gcd(a, b) {
    let t;
    while (b !== 0) {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}


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

// file: ratio.js

function sign(x) {
  return x === BigInt(0) ? BigInt(0)
       : x > BigInt(0)   ? BigInt(1) 
       /* otherwise */   : BigInt(-1);
}

function abs(x) {
  return x < BigInt(0) ? x * BigInt(-1) : x;
}

function simplify(numerator, denominator) {
  const sgn = sign(numerator) * sign(denominator);
  const n = abs(numerator);
  const d = abs(denominator);
  const f = gcd(n, d);
  return new Ratio((sgn * n) / f, d / f);
}


И теперь мы можем написать наш метод равенства: 

// file: ratio.js -- inside the class declaration
  equals(other) {
    const a = simplify(this);
    const b = simplify(other);
    return (
      a.numerator === b.numerator &&
      a.denominator === b.denominator
    );
  }


Теперь можно сравнить две дроби на равенство. Может показаться, что это не так уж и много, но это значит, что мы можем написать юнит-тесты и убедиться, что наша библиотека работает, как ожидается.

Преобразование в другие типы


Не буду утомлять, выписывая все юнит-тесты моей библиотеки. Но было бы неплохо конвертировать дроби в другие форматы. Например, мы можем захотеть представить их как строку в отладочных сообщениях. Или, возможно, мы захотим преобразовать их в числа. Итак, давайте переопределим методы .toString () и .toValue () для нашего класса.

Метод .toString () проще всего, так что давайте начнём с него.

// file: ratio.js -- inside the class declaration
  toString() {
    return `${this.numerator}/${this.denominator}`;
  }


Достаточно просто. Но как насчёт преобразования обратно в число? Один из способов сделать это — просто разделить числитель на знаменатель: 

// file: ratio.js -- inside the class declaration
  toValue() {
    return  Number(this.numerator) / Number(this.denominator);
  }


Зачастую это работает. Но, возможно, мы захотим немного подправить код. Весь смысл нашей библиотеки заключается в том, что мы используем большие целые числа для получения необходимой точности. И иногда эти целые числа будут слишком большими, чтобы их можно было преобразовать обратно к типу Number. Но мы хотим получить Number как можно ближе к истине, где это возможно. Так что мы выполняем немного арифметических действий, пока конвертируем BigInt в Number: 

// file: ratio.js -- inside the class declaration
  toValue() {
    const intPart = this.numerator / this.denominator;
    return (
      Number(this.numerator - intPart * this.denominator) /
        Number(this.denominator) + Number(intPart)
    );
  }


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

Умножение и деление


Сделаем что-нибудь с числами. Как насчёт умножения и деления? Это несложно для дробей. Умножаем числители на числители, а знаменатели на знаменатели.

// file: ratio.js -- inside the class declaration
  times(x) {
    return simplify(
      x.numerator * this.numerator,
      x.denominator * this.denominator
    );
  }


Деление похоже на код выше. Переворачиваем вторую дробь, затем умножаем.

// file: ratio.js -- inside the class declaration
  divideBy(x) {
    return simplify(
      this.numerator * x.denominator,
      this.denominator * x.numerator
    );
  }


Сложение и вычитание


Теперь у нас есть умножение и деление. Логически следующая вещь, которую нужно написать, — это сложение и вычитание. Это немного сложнее, чем умножение и деление. Но не слишком.
Чтобы сложить две дроби, сначала нужно привести их к одному знаменателю, затем сложить числители. В коде это может выглядеть примерно так: 

// file: ratio.js -- inside the class declaration
  add(x) {
    return simplify(
      this.numerator * x.denominator + x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }


Всё умножается на знаменатели. И мы используем simplify (), чтобы сохранялась дробь как можно меньше в смысле чисел числителя и знаменателя.
Вычитание похоже на сложение. Мы манипулируем двумя дробями так, чтобы одинаковые знаменатели выстраивались в ряд, как раньше. Затем не складываем, а вычитаем.

// file: ratio.js -- inside the class declaration
  subtract(x) {
    return simplify(
      this.numerator * x.denominator - x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }


Итак, у нас есть основные операторы. Можно складывать, вычитать, умножать и делить. Но нам всё ещё нужно несколько других методов. В частности, цифры имеют важное свойство: мы можем сравнивать их друг с другом.

Сравнения


Мы уже обсуждали .equals (). Но нам нужно нечто большее, чем просто равенство. Мы также хотели бы иметь возможность определить отношения дробей «больше, меньше». Поэтому создадим метод .lte (), который расскажет нам, является ли одна дробь меньшей или равной другой дроби. Как и в случае .equals (), не очевидно, какая из двух дробей меньше. Чтобы сравнить их, нам нужно преобразовать обе к одному знаменателю, затем сравнить числители. С небольшим упрощением это может выглядеть так: 

// file: ratio.js -- inside the class declaration
  lte(other) {
    const { numerator: thisN, denominator: thisD } = simplify(
      this.numerator,
      this.denominator
    );
    const { numerator: otherN, denominator: otherD } = simplify(
      other.numerator,
      other.denominator
    );
    return thisN * otherD <= otherN * thisD;
  }


Как только мы получим .lte () и .equals (), то сможем вывести остальные сравнения. Можно выбрать любой оператор сравнения. Но если у нас есть equals () и >, стандарт FantasyLand. Вот как могут выглядеть другие операторы: 

// file: ratio.js -- inside the class declaration
  lt(other) {
    return this.lte(other) && !this.equals(other);
  }

  gt(other) {
    return !this.lte(other);
  }

  gte(other) {
    return this.gt(other) || this.equals(other);
  }


Округление


Теперь мы можем сравнить дроби. А ещё можем умножать и делить, складывать и вычитать. Но если мы собираемся делать больше интересного с нашей библиотекой, нам нужно больше инструментов. Удобные объекты JavaScript Math содержат методы .floor () и .ceil ().
Начнём с .floor (). Floor принимает значение и округляет его вниз. При положительных числах это означает, что мы просто сохраняем целую часть и отбрасываем оставшуюся часть. Но для отрицательных чисел мы округляем вверх от нуля, так что отрицательным числам нужно уделить немного больше внимания.

// file: ratio.js -- inside the class declaration
  floor() {
    const one = new Ratio(BigInt(1), BigInt(0));
    const trunc = simplify(this.numerator / this.denominator, BigInt(1));
    if (this.gte(one) || trunc.equals(this)) {
      return trunc;
    }
    return trunc.minus(one);
  }


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

// file: ratio.js -- inside the class declaration
  ceil() {
    const one = new Ratio(BigInt(1), BigInt(0));
    return this.equals(this.floor()) ? this : this.floor().add(one);
  }


Сейчас у нас есть большая часть необходимого для многих математических операций. А с помощью .toValue () мы можем легко преобразовать вычисления обратно в десятичные числа. Но что, если мы хотим преобразовать число с плавающей точкой в дробь?

Число в дробь


Преобразование чисел в дроби сложнее, чем может показаться на первый взгляд. И есть много разных способов проделать это преобразование. Мой способ реализации не самый точный, но он достаточно хорош. Чтобы он сработал, сначала конвертируем число в строку, которая, как мы знаем, приобретёт формат последовательности. Для этого JavaScript предоставляет нам метод .toExponential (). Метод возвращает число в экспоненциальной нотации. Вот несколько примеров для понимания идеи: 

let x = 12.345;
console.log(x.toExponential(5));
// ⦘ '1.23450e+1''

x = 0.000000000042;
console.log(x.toExponential(3));
// ⦘ '4.200e-11'

x = 123456789;
console.log(x.toExponential(4));
// ⦘ '1.2346e+8'


Код работает, представляя число в виде нормализованного десятичного значения и множителя. Нормализованный десятичный бит называется мантиссой, а множитель — экспонентой. Здесь «нормализованный» означает, что абсолютное значение мантиссы всегда меньше 10. А экспонента всегда теперь 10. Мы указываем начало множителя с буквой 'e' (сокращение от 'exponent').

Преимущество этой нотации в том, что она последовательна. Всегда есть ровно одна цифра слева от десятичной точки. А .toExponential () позволяет указать, сколько значащих цифр мы хотим. Затем идет 'e' и экспонента — всегда целое число. Поскольку значение последовательно, мы можем использовать наглое регулярное выражение, чтобы разобрать его.

Процесс идёт примерно так. Как уже упоминалось, .toExponential () принимает параметр для указания количества значащих цифр. Нам нужен максимум цифр. Итак, мы установили точность на 100 (столько позволит большинство JavaScript-движков). В этом примере, однако, мы будем придерживаться точности 10. Теперь представьте, что у нас есть число 0.987654321e0. Мы хотим перенести десятичную точку на 10 цифр вправо. Это дало бы нам 9876543210. Затем делим на 10^10, и получаем 9876543210/100000000. Это, в свою очередь, упрощает до 987654321/100000000.

Но мы должны обратить внимание на эту экспоненту. Если у нас есть число вроде 0.987654321e9, то мы всё равно сдвинем десятичную точку на 10 цифр вправо. Но мы делим на десять, к степени 10–9=1.

$0.987654321×10^9 = 9876543210/ 10^1=$

$987654321/1$


Чтобы всё было именно так, мы определили пару вспомогательных функций: 

// Transform a ‘+’ or ‘-‘ character to +1 or -1
function pm(c) {
  return parseFloat(c + "1");
}

// Create a new bigint of 10^n. This turns out to be a bit
// faster than multiplying.
function exp10(n) {
  return BigInt(`1${[...new Array(n)].map(() => 0).join("")}`);
}


С их помощью мы можем собрать всю функцию fromNumber () воедино.

// file: ratio.js -- inside the class declaration
  static fromNumber(x) {
    const expParse = /(-?\d)\.(\d+)e([-+])(\d+)/;
    const [, n, decimals, sgn, pow] =
      x.toExponential(PRECISION).match(expParse) || [];
    const exp = PRECISION - pm(sgn) * +pow;
    return exp < 0
      ? simplify(BigInt(`${n}${decimals}`) * exp10(-1 * exp), BigInt(1))
      : simplify(BigInt(`${n}${decimals}`), exp10(exp));
  }


Охвачено большинство основных функций. Мы можем перейти от чисел к дробям и обратно. Но для моего конкретного приложения мне нужно было большее. В частности нужно было найти возведение в степень и логарифмы.

Возведение в степень


Возведение в степень — это когда число многократно умножается само на себя. Например, 2^3=2×2×2=8. Для простых случаев, когда степень — целое число, есть встроенный оператор BigInt: **. Так что, если мы возводим в степень дробь, это хороший вариант. Вот так дробь возводится в степень:

$\left(\frac{x}{y}\right)^{n} = \frac{x^n}{y^n}$


Следовательно, первый отрезок нашего метода возведения в степень может выглядеть примерно так: 

// file: ratio.js -- inside the class declaration
  pow(exponent) {
    if (exponent.denominator === BigInt(1)) {
        return simplify(
            this.numerator ** exponent.numerator,
            this.denominator ** exponent.numerator
        );
    }
  }


Прекрасно работает. Ну… в основном хорошо. Теперь всё становится сложнее. Из-за пределов ограничений обеспечения и математики мы должны пойти на некоторые компромиссы. Возможно, нам придётся пожертвовать точностью ради получения ответа в разумные сроки.

Возведение в степень легко порождает большие числа. И когда числа становятся большими, всё замедляется. Пока я писал эту статью, я также написал вычисления, которые, не завершаясь, выполнялись в течение дней. Так что нужно соблюдать осторожность. Но ничего страшного. Все поставляется для BigInt.

Но есть и другая проблема. Что делать, если знаменатель степени — не единица? Например, что, если бы мы хотели рассчитать 8^(2/3)?

К счастью, мы можем разделить эту проблему на две проблемы поменьше. Мы хотим привести одну дробь к степени другой. Например, мы можем отнести x/y к a/b. Законы возведения в степень гласят, что следующее эквивалентно:

$\left(\frac{x}{y}\right)^\frac{a}{b} = \left(\left(\frac{x}{y}\right)^\frac{1}{b}\right)^a = \left(\frac{x^\frac{1}{b}}{y^\frac{1}{b}}\right)^a$


Мы уже знаем, как привести одно число BigInt к степени другого числа BigInt. Но как насчёт дробной степени? Ну, есть ещё один эквивалент:

$x^\frac{1}{n} = \sqrt[n]{x}$


То есть приведение xx к степени 1n1n эквивалентно нахождению n-го корня из xx. Это означает, что если мы найдем способ вычислить n-й корень BigInt, то мы сможем вычислить любую степень.

При хорошо продуманном поиске в вебе, нахождение алгоритма оценки n-го корня не займёт много времени. Наиболее распространённый метод — метод Ньютона. Он работает начиная с оценки, rr. Затем делается такой расчёт, чтобы получить лучшую оценку:

$\begin{align} r &\approx x^{\frac{1}{n}} \\ r^{\prime} &= \frac{1}{n}\left((n-1)r + \left(\frac{x}{r^{n-1}}\right)\right) \end{align}$


Мы продолжаем повторять эти расчёты до тех пор, пока не достигнем желаемой точности. К сожалению, есть некоторые корни, которые не могут быть представлены в виде конечной дроби. Другими словами, чтобы получить идеальную точность, нам понадобятся бесконечно длинные значения BigInt. На практике это означает, что мы должны выбрать произвольное ограничение итераций.

Мы вернемся к этому моменту. А пока давайте разберёмся, как вычислить достаточно точный корень n-й степени. Так как оценка rr будет дробью, мы можем записать её как:

$r = \frac{a}{b}.$


И это позволяет нам переписать расчёты так:

$\frac{a^{\prime}}{b^{\prime}} = \frac{(n - 1)a^{n} + x b^{n}}{n b a^{n - 1}}$


Теперь всё в терминах целочисленных вычислений, подходящих для использования с BigInt. Не стесняйтесь вставлять abab в уравнение для r′r′ выше и проверьте мои выводы. В JavaScript это выглядит вот так: 

const estimate = [...new Array(NUM_ITERATIONS)].reduce(r => {
  return simplify(
    (n - BigInt(1)) * r.numerator ** n + x * r.denominator ** n,
    n * r.denominator * r.numerator ** (n - BigInt(1))
  );
}, INITIAL_ESTIMATE);


Мы просто повторяем это вычисление до тех пор, пока не достигнем подходящей точности для нашей оценки корня n-й степени. Проблема в том, что нам нужно придумать подходящие значения для наших констант. То есть NUM_ITERATIONS и INITIAL_ESTIMATE.
Многие алгоритмы начинаются с INITIAL_ESTIMATE в единицу. Это разумный выбор. Зачастую у нас нет хорошего способа предположить, каким может быть корень n-й степени. Но напишем «обманку». Предположим (пока), что наш числитель и знаменатель находятся в диапазоне Number. Затем мы можем использовать Math.pow () для получения начальной оценки. Это может выглядеть так: 

// Get an initial estimate using floating point math
// Recall that x is a bigint value and n is the desired root.
const initialEstimate = Ratio.fromNumber(
    Math.pow(Number(x), 1 / Number(n))
);


Итак, у нас есть значение для нашей первоначальной оценки. А как же NUM_ITERATION? Ну, на практике, то, что я делал, начиналось с предположения в 10. А потом я проводил тесты свойств. Я продолжал наращивать число до тех пор, пока вычисления укладывались в разумные сроки. И цифра, которая, наконец, сработала… 1. Одна итерация. Это меня немного огорчает, но мы немного более точны, чем при вычислениях с плавающей точкой. На практике вы можете увеличивать это число, если не вычисляете много дробных степеней.

Для простоты мы извлечём вычисление n-го корня в отдельную функцию. Если сложить всё вместе, код может выглядеть так: 

// file: ratio.js -- inside the class declaration
  static nthRoot(x, n) {
    // Handle special cases
    if (x === BigInt(1)) return new Ratio(BigInt(1), BigInt(1));
    if (x === BigInt(0)) return new Ratio(BigInt(0), BigInt(1));
    if (x < 0) return new Ratio(BigInt(1), BigInt(0)); // Infinity

    // Get an initial estimate using floating point math
    const initialEstimate = Ratio.fromNumber(
      Math.pow(Number(x), 1 / Number(n))
    );

    const NUM_ITERATIONS = 1;
    return [...new Array(NUM_ITERATIONS)].reduce((r) => {
      return simplify(
        n -
          BigInt(1) * (r.numerator ** n) +
          x * (r.denominator ** n),
        n * r.denominator * r.numerator ** (n - BigInt(1))
      );
    }, initialEstimate);
  }

  pow(n) {
    const { numerator: nNumerator, denominator: nDenominator } = n.simplify();
    const { numerator, denominator } = this.simplify();
    if (nNumerator < 0) return this.invert().pow(n.abs());
    if (nNumerator === BigInt(0)) return Ratio.one;
    if (nDenominator === BigInt(1)) {
      return new Ratio(numerator ** nNumerator, denominator ** nNumerator);
    }
    if (numerator < 0 && nDenominator !== BigInt(1)) {
      return Ratio.infinity;
    }

    const { numerator: newN, denominator: newD } = Ratio.nthRoot(
      numerator,
      nDenominator
    ).divideBy(Ratio.nthRoot(denominator, nDenominator));
    return new Ratio(newN ** nNumerator, newD ** nNumerator);
  }


Неидеально и медленно. Но задача стала в основном выполнимой. Остаётся вопрос, как получить оценку, если у нас целые числа больше Number.MAX_VALUE. Однако я оставлю это как упражнение для читателя; эта статья и так уже слишком длинная.

Логарифмы


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

Почему это так сложно? Моей целью было вычислить логарифмы ради точности большей, чем точность чисел с плавающей точкой. Иначе зачем всё это? Функция вычисления логарифма с типом числа с плавающей точкой, Math.log10(), быстрая и встроенная. Итак, я посмотрел на алгоритмы, которые дают способы итеративного вычисления логарифмов. И они работают. Но они медленны в получении точности выше точности числа с плавающей точкой. Не просто немного медленнее. Намного медленнее.

По мере того как мы проходим через итерации, дробь, которую мы строим, становится всё точнее. Но за эту точность приходится платить. Значения BigInt в дроби становятся всё больше и больше. И по мере того как они становятся больше, их умножение начинает занимать много времени. В какой-то момент я оставил вычисление на три дня. Но пока шли расчёты, я кое-что вспомнил.

Я вспомнил, что мне нужен метод log10() для того, чтобы можно было вычислять красивые масштабированные значения для графиков. И для этих вычислений каждый раз, когда я вызывал .log10(), я сразу же вызывал .floor (). Это означает, что мне нужна только целочисленная часть логарифма. Расчёт логарифма до 100 знаков после запятой был просто пустой тратой времени и мощностей.

Более того, есть простой способ вычислить целую часть логарифма по основанию 10. Всё, что нам нужно, — это посчитать цифры. Наивная попытка может выглядеть так: 

// file: ratio.js -- inside the class declaration
  floorLog10() {
    return simplify(BigInt((this.numerator / this.denominator).toString().length - 1), BigInt(1));
  }


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

$\begin{align} \log_{10}\left(\frac{a}{b}\right) &= \log_{10}(a) - \log_{10}(b) \\ \log_{10}\left(\frac{1}{x}\right) &= \log_{10}(1) - \log_{10}(x) \\ &= -\log_{10}(x) \end{align}$


Поэтому:

$\log_{10}\left(\frac{b}{a}\right) = -\log_{10}\left(\frac{a}{b}\right)$


Собрав всё воедино, мы получаем более надежный метод floorLog10(): 

// file: ratio.js -- inside the class declaration

  invert() {
    return simplify(this.denominator, this.numerator);
  }

  floorLog10() {
    if (this.equals(simplify(BigInt(0), BigInt(1)))) {
      return new Ratio(BigInt(-1), BigInt(0));
    }
    return this.numerator >= this.denominator
      ? simplify((this.numerator / this.denominator).toString().length - 1, 1)
      : simplify(BigInt(-1), BigInt(1)).subtract(this.invert().floorLog10());
  }


Опять. Зачем мучиться?


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

Честно говоря, я бы использовал существующую библиотеку в большинстве случаев. Особенно, если я тороплюсь. Нет смысла делать всё это, если кто-то уже сделал превосходящую работу.

Ключевое слово здесь — «превосходящую». И именно здесь в игру вступают мои мотивы желания написать свою собственную библиотеку. Метод floorLog10() выше — идеальный пример. Он обеспечивает точный расчёт, который мне нужен для того, что хочу сделать я. Он делает это эффективно, примерно в шести строках кода.

Если бы я воспользовался чужой библиотекой, я бы столкнулся с одним из двух:

  1. Разработчики не реализовали log10() или любые другие логарифмические методы.


или

  1. Разработчики реализовали метод log10() (или его эквивалент).


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

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

Кроме всего этого, я многому научился, создавая свою собственную библиотеку. Теперь я на практике понимаю ограничения BigInt намного лучше, чем раньше. Я знаю, что могу настроить производительность метода корня n-й степени. Я могу настроить его в зависимости от того, сколько вычислений выполняю и какая точность мне нужна.

Иногда стоит написать свою собственную библиотеку общего назначения. Даже если ты не планируешь открывать код. Даже если никто больше ею не воспользуется. Ты можешь многому научиться, и, кроме того, это может принести радость.

Если вы хотите узнать больше о проблемах с числами с плавающей точкой, обратитесь к 0.30000000000000004.com. А если вы хотите посмотреть библиотеку целиком и сделать некоторые вычисления, то можете посмотреть эту песочницу с кодом.

image


Другие профессии и курсы
ПРОФЕССИИ

КУРСЫ

© Habrahabr.ru