stdlib-js / stdlib-js/stdlib

update efficiency of calculating binomial coefficients

オープン
#2,442 コメント 4 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
JavaScript
スター
6k
フォーク
1.3k
平均マージ
1日 3時間
マージ済み PR(30日)
611

説明

I can make a formal PR/Issue, but just sitting on my phone talking with chatGPT trying to figure out how to efficiently calculate binomial coefficients,I was looking at how you solve binomial coefficients in this package; @stdlib/math-base-special-binomcoef, and was wondering if a solution such as this would be better?

```ts
function binomialCoefficientLog(n, k) {
if (k > n) return 0;
if (k === 0 || k === n) return 1;

let logSum = 0;
for (let i = 0; i < k; i++) {
logSum += Math.log(n - i) - Math.log(i + 1);
}

return Math.exp(logSum);
}
```

This basically breaks it down to it's most simplest form (with log for maintaining precision) by stopping the loop once we reach k, so only calculating necessary values. Basically O(k) time complexity and O(1) space complexity.

Obviously error handling would need to be added but in a nutshell this is what I was thinking.

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

Start with @stdlib/math-base-special-binomcoef and inspect how it currently calculates binomial coefficients. Compare the proposed O(k) time and O(1) space approach, including precision and error handling, then determine whether a change is warranted. Done means the implementation is improved without losing correctness, with relevant validation for the supported inputs.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
javascript
領域
performance
issue の種類
リファクタリング
難易度
4/5
見積もり時間
3〜5日
活発さ
停滞
明瞭さ
説明が足りない
初心者へのやさしさ
35/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。