Как оптимизировать вычисление биномиального коэффициента?

Question

[Rufix]

Есть такая задача на codewars.
Грубо говоря необходимо написать формулу n! / (k! * (n - k)!).

На выходе я получил такой код:

function choose (n, k) {
  function factorial (i) {
    return (i > 0) ? i * factorial (i-1) : 1;
  }

  return factorial (n) / (factorial (k) * factorial(n-k));
  
}

Код рабочий. Но в конце этой каты написано следующее:

Будьте осторожны: ожидается определенная степень оптимизации, которая будет касаться как большей точности чисел (и их ошибок округления в таких языках, как JS), так и времени вычислений.

Я ничего не понял. О какой оптимизации идет речь и что вообще от меня хотят?

Comments

[Lynn «Кофеман»]

Факториал легко может вылезти за пределы максимального целого, в то время как всё выражение будет всё ещё меньше максимума.

Рекомендую разложить формулу и сократить всё что можно

[Роман]

Оооо народ тут любит задачки с подковыркой))))

которая будет касаться как большей точности чисел (и их ошибок округления в таких языках, как JS),

тут все просто, попробуйте выполнить следующий код:

var n = 0.1 * 0.2;
console.log( n)

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

так и времени вычислений

ну тут вообще просто, запустите ваш код со следующими n и k

let n = 1e9;
let k = 1e10;

Думаю вкладка браузера надолго уйдет в кулдаун)

[Lynn «Кофеман»]

Роман, вряд ли там такая жесть. Скорее n и k подобрано так, вычисление n! выходит за пределы, а всё выражение не

[Роман]

Алексей Тен, судя по комментам к ответу 0xD34F вы правы, там все проще, но я всего лишь для примера чуть сгустил краски)))

Answer 1

[0xD34F]

function mul(start, end) {
  let result = 1;

  for (let i = start; i <= end; i++) {
    result *= i;
  }

  return result;
}

function choose(n, k) {
  return n > k
    ? Math.round(mul(n - k + 1, n) / mul(2, k))
    : +(n === k);
}

Comments

[Rufix]

Впендолил этот код в кату и она прошла. Но не мог бы ты объяснить почему? И лучше ли этот способ использовать на практике или я могу использовать свой способ?

[0xD34F]

Rufix, нет рекурсии. Нет повторных вычислений (n! в числителе, (n - k)! в знаменателе - значит, можно сократить (n - k)! и посчитать только произведение чисел от n - k + 1 до n).

[Stalker_RED]

Rufix, почитай что-нибудь о сложности алгоритмов (О большое) и поймешь.

[Lynn «Кофеман»]

Кстати, тут можно (нужно) соптимизировать. Если k > n/2, то надо вместо k взять n-k

Answer 2

[Петр]

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

Comments

[Rufix]

И что делать?