stdlib-js / stdlib-js/stdlib

update efficiency of calculating binomial coefficients

Đang mở
#2,442 4 bình luận 0 reaction 0 người được giao Xem trên GitHub
Ngôn ngữ chính
JavaScript
Star
6k
Fork
1.3k
Merge trung bình
1 ngày 3 giờ
Pull request đã merge (30 ngày)
611

Mô tả

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.

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Hướng nghiên cứu

Bắt đầu với @stdlib/math-base-special-binomcoef và kiểm tra cách hiện tại nó tính các hệ số nhị thức. So sánh cách tiếp cận được đề xuất có thời gian O(k) và không gian O(1), bao gồm độ chính xác và xử lý lỗi, sau đó xác định liệu có cần thay đổi hay không. Được xem là hoàn tất khi việc triển khai được cải thiện mà không làm mất tính đúng đắn, cùng với việc có xác thực phù hợp cho các đầu vào được hỗ trợ.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Đánh giá

Công nghệ
javascript
Lĩnh vực
performance
Loại issue
Tái cấu trúc
Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức độ hoạt động
Đình trệ
Độ rõ ràng
Cần làm rõ
Mức phù hợp với người mới
35/100

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.