improving speed of factorial function

[honeybar]

Hi, I modified factorial functions in gamma.js, permutation.js and combination.js for regular number to speed up the run time by modifying how product is calculated. (see: productrange.js for more info on how it is done). I tried to implement the same algorithm for big number but it ends up slower compared to the original, which is a bit of a surprise since, on regular number, the trend is that it will outperform the original method. I am still rather new to open source contribution so feedback is appreciated.

Thank you.

here is the log of performance for permutation function original vs new:

ans for original algorithm for 50P25: 1.9607814681608194e+39
2.525ms
ans for newer algorithm for 50P25: 1.9607814681608194e+39
0.187ms

here is one for combination function:

ans for original algorithm for 50C25: 126410606437752
11.590ms
ans for new algorithm for 50C25: 126410606437752
0.686ms

here is one for factorial:

ans for original algorithm for 50! : 3.0414093201713376e+64
2.647ms
ans for new algorithm for 50! : 3.0414093201713376e+64
0.703ms

[josdejong]

wow, that's impressive!!! Thanks a lot @honeybar .

I think your work is ready to be merged as is, though I have a few remarks:

1. How about renaming the function productrange.js to product.js since that is the only function that is in there?
2. Can you write some (minimal) comments on top of the function product to explain what it does and what goes in and out?
3. It would be great if you could improve the performance of the BigNumber implementations too, would that be doable?

[josdejong]

I tried to implement the same algorithm for big number but it ends up slower compared to the original,

ah sorry, now I see. Forget about my point 3.

[harrysarson]

Looks good, just a quick question 👍

[harrysarson]

Does | 0 round towards zero here? Maybe Math.trunc would be clearer if so?

[honeybar]

Hi, math.trunc is slower compared to operators that convert to integers. I decided to use the >> operator instead since I am gonna dividing by 2 and truncate anyways. I did leave a comment in product.js to clarify what it does.

[harrysarson]

👍

[josdejong]

Thanks for the updates @honeybar .

Just curious: have you also tried a plain old for loop to calculate the product, instead of the recursive solution that you have now?

[honeybar]

@josdejong I haven't tried converting the divide and conquer solution to for-loop. I think it might be possible, but it would be rather complex to do so, since divide and conquer is inherently recursive process.

[josdejong]

Thanks for your latest updates @honeybar!

[josdejong]

The improved function factorial is now available in v5.0.4, thanks again!