Thread overview
[Issue 13371] std.math.factorial
Aug 29, 2014
Don
Aug 29, 2014
safety0ff.bugz
Aug 30, 2014
yebblies
Dec 23, 2016
Eduard Staniloiu
August 27, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

hsteoh@quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hsteoh@quickfur.ath.cx

--- Comment #1 from hsteoh@quickfur.ath.cx ---
auto factorial(T)(in T n) {
    import std.mathspecial : gamma;
    return gamma(n+1);
}

--
August 29, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

--- Comment #2 from Don <clugdbug@yahoo.com.au> ---
(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,

--
August 29, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

--- Comment #3 from bearophile_hugs@eml.cc ---
(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.

--
August 29, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

--- Comment #4 from bearophile_hugs@eml.cc ---
(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.

--
August 29, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

safety0ff.bugz <safety0ff.bugz@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |safety0ff.bugz@gmail.com

--- Comment #5 from safety0ff.bugz <safety0ff.bugz@gmail.com> ---
(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.

--
August 29, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

--- Comment #6 from bearophile_hugs@eml.cc ---
(In reply to safety0ff.bugz from comment #5)

> I think that any BigInt functions worth providing in phobos should be implemented within BigInt.

OK.

--
August 30, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

yebblies <yebblies@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yebblies@gmail.com

--- Comment #7 from yebblies <yebblies@gmail.com> ---
(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.

--
August 30, 2014
https://issues.dlang.org/show_bug.cgi?id=13371

--- Comment #8 from hsteoh@quickfur.ath.cx ---
auto factorial(T)(T t) {
        import std.range : drop, recurrence;
        return recurrence!"a[n-1] * n"(1).drop(t).front;
}


Happy now?

--
December 23, 2016
https://issues.dlang.org/show_bug.cgi?id=13371

Eduard Staniloiu <edi33416@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |trivial
                 CC|                            |edi33416@gmail.com

--
December 24, 2016
https://issues.dlang.org/show_bug.cgi?id=13371

Andrei Alexandrescu <andrei@erdani.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |andrei@erdani.com
         Resolution|---                         |WONTFIX

--- Comment #9 from Andrei Alexandrescu <andrei@erdani.com> ---
We needn't provide this, it's too niche.

--