Comment #0 by bearophile_hugs — 2014-08-24T16:29:05Z
I suggest to add to Phobos a commonly useful function similar to this (also present in the Python standard library):
import std.traits: isAssignable;
T factorial(T)(in T n)
if (__traits(compiles, T(1) < T(1)) &&
__traits(compiles, T(1) + 1) &&
__traits(compiles, T(1) * T(1)) &&
isAssignable!T)
in {
assert(n >= 0);
} body {
auto result = T(1);
for (auto i = T(1); i <= n; i = i + 1)
result = result + result * i;
return result;
}
Aternatively the index 'i' can be of type integer or uint. In this case the template constraints needs to be modified.
Comment #1 by hsteoh — 2014-08-27T05:24:01Z
auto factorial(T)(in T n) {
import std.mathspecial : gamma;
return gamma(n+1);
}
Comment #2 by clugdbug — 2014-08-27T08:04:40Z
(In reply to hsteoh from comment #1)
> auto factorial(T)(in T n) {
> import std.mathspecial : gamma;
> return gamma(n+1);
> }
Exactly! And I seriously doubt that factorial is commonly used. It's a widely used _example_, but it's hard to come up with applications for it. Eg even for calculating permutations and combinations, using factorial is not a good method.
And for BigInt, iterated multiplication isn't a good way of caclulating factorials. You need to group multiple factors together, so that the multiplies are of similar length.
And finally, your code reports factorial(2) == 3, which isn't a good start,
Comment #3 by bearophile_hugs — 2014-08-27T08:53:05Z
(In reply to hsteoh from comment #1)
> auto factorial(T)(in T n) {
> import std.mathspecial : gamma;
> return gamma(n+1);
> }
I need exact integral values, so no thanks.
Comment #4 by bearophile_hugs — 2014-08-27T09:04:58Z
(In reply to Don from comment #2)
> Exactly! And I seriously doubt that factorial is commonly used.
I don't agree. I am using it. It's a basic common algorithm. Asking people to rewrite it in every little script of project is unwise. Python standard library shows it's a good idea to put it in. Other languages like Julia have it in the std lib.
> Eg even for calculating permutations and combinations, using factorial is
> not a good method.
This is not important.
> And for BigInt, iterated multiplication isn't a good way of caclulating
> factorials.
Right, for BigInt you can add a different specialization later for bigints.
> You need to group multiple factors together, so that the
> multiplies are of similar length.
There are good algorithms to compute large factorials quickly. But having a basic common algorithm is right.
> And finally, your code reports factorial(2) == 3, which isn't a good start,
I haven't tested it, it's just example code to show what I meant.
Comment #5 by safety0ff.bugz — 2014-08-27T13:35:33Z
(In reply to bearophile_hugs from comment #4)
> (In reply to Don from comment #2)
>
> > And for BigInt, iterated multiplication isn't a good way of caclulating
> > factorials.
>
> Right, for BigInt you can add a different specialization later for bigints.
>
Generic functions for computing BigInt results often end up hitting one limitation or another.
I think that any BigInt functions worth providing in phobos should be implemented within BigInt.
With factorial for example, there will be garbage creation for intermediate results that could be eliminated if implemented in BigInt.
Comment #6 by bearophile_hugs — 2014-08-29T07:03:52Z
(In reply to safety0ff.bugz from comment #5)
> I think that any BigInt functions worth providing in phobos should be
> implemented within BigInt.
OK.
Comment #7 by yebblies — 2014-08-30T14:03:22Z
(In reply to bearophile_hugs from comment #4)
>
> I don't agree. I am using it. It's a basic common algorithm. Asking people
> to rewrite it in every little script of project is unwise.
If it was used in every little script this would be a valid argument. I don't think I've ever used it outside of project euler puzzles.
On the other hand, it costs us very little to provide it. A function that only takes a dozen lines doesn't have a high usefulness barrier to overcome.