Crystal: GMP factorial

[peheje]

Hi,
I just stumpled upon Crystal, what a lovely project.

Is it possible to add GMP factorial binding to Crystal? I messed with it abit and the following seems to work, but probably more needs to be done:

I then tried

x = 370103.to_big_i.fac
y = (370103-4).to_big_i.fac
z = x // y
puts z

Prints 18762183581473422330600 which seems correct

Let me know if I can help with getting this implemented.

[straight-shoota]

A similar proposal has been made in #3504 before.

This could be considered a douplicate. But... I think it's a different thing because on BigInt this method could be considered more useful because it's not limited by int size. And the implementation is already done in libgmp, so it's cheap and we don't need to maintain it.

Factorial is a basic math operation. I'd support having it in stdlib.

[asterite]

I think this makes sense. The hardest part will be deciding the name.

[peheje]

The discussion in #3504 mentions rolling your own factorial algorithm. Which is true but non trivial for arbitrary precision numbers if you care about speed: https://gmplib.org/manual/Factorial-Algorithm.html

Factorials have many use cases, also of big numbers. In my case to calculate the number of permutations of k words given n symbols.

I tried to do this with just bigint multiplication but it was horribly slow. GMP factorial is fast just like Python and Julia which I believe also binds to the GMP version.

If you agree, how can I proceed with this?

[asterite]

https://github.com/crystal-lang/crystal/blob/master/CONTRIBUTING.md#the-standard-library

[asterite]

though apparently the instructions are outdated, *sigh*... I have no idea what make libcrystal is, there was never such a thing.

[straight-shoota]

@asterite There is. And you need to run it after checking out stdlib repo.

https://github.com/crystal-lang/crystal/blob/c5dffc002363048cea72af8f1d7efff1a2907a91/Makefile#L103

But it seems @peheje has already a working repo setup.
As soon as we're settled on the details, we'd greatly appreciate if you submit a PR. Besides the initial implementation it would also need some specs for general and edge cases to make sure it works as expected.

Next steps would to decide on where to place the method and what to name it.
It could be available only on BigInt, or on Int or in the Math namespace (the latter can be limited to receive BigInt or any Int).
I'd probably go with BigInt#factorial for now.

[asterite]

Sorry, my bad. I didn't know libcrystal was a thing. I never run it myself. I always run make deps, but I guess that compiles stuff for LLVM which is not needed for the stdlib.

[straight-shoota]

Haha, I was just really surprised that the guy with more commits on this repo than everyone else combined wasn't aware of such an essential tool 😆 But makes it sense that you always run make deps because you're hacking at the compiler.

[peheje]

Added PR here:

https://github.com/crystal-lang/crystal/pull/9132

Let me know what more is needed.