Factorial project

[bodrato at mail.dm.unipi.it]

Dear Stéphane,

> Is someone working on decomposition of factorial into power of prime? The
> latest copyright in fac_ui.c is 2003.I may be interested in working on it.
> Maybe only for factor of 3 at first.

Sorry for the delay.

At last I was able to (somehow) clean the code, extract some graphs and
publish it.

You can find my new implementation of fac_ui.c on my web pages at:
http://bodrato.it/software/combinatorics.html#fac_ui

For the factorial I implemented three different algorithms, two are naive
and used for smaller sizes, the third one is based on the "Divide, Swing,
and Conquer" technique suggested by Peter Luschny.
You can simply plug my implementation in mpz/fac_ui.c, recompile, and see
what happen :-)

To really use the new code, the two thresholds (FAC_DSC_THRESHOLD, and
FAC_ODD_THRESHOLD) should be tuned. The code is almost ready for the
library... But I'll be happy if anyone want to read/comment/modify it, or
simply suggest.


Meanwhile re-implemented also the binomial the code is in the SAME FILE
with factorial. They are not "mixed", but they share a lot of code. There
are sections (marked by comments) in the file, and it will be necessary to
split them in single files...
By the way, also the binomial code is asymptotically fast, for couples
like (n,n/3). It is NOT fast for couples (n,k) with a small k. There are
many algorithms ready in the file, but unused.

Two implementations for the binomial are based on a Divide&Conquer
technique, following the observation
binomial(n,a+b)=binomial(n,a)*binomial(n-a,b)/binomial(a+b,a) .
Both implementations are _VERY_ naive, but a range is shown where they are
the fastest algorithm among the implemented ones. Further effort should be
spent in a general function using D&C.

All informations about the new binomial implementation can be found here:
http://bodrato.it/software/combinatorics.html#bin_uiui

To experiment also the new binomial code, you can replace the file
mpz/bin_uiui.c with the two lines:
#define OPERATION_bin_uiui
#include "fac_ui.c"

Many informations are already available on the web page, I simply show
timings measured on my laptop, before and after insertion of the new code.

            CURRENT IMPLEMENTATION   |       MY IMPLEMENTATION
           mpz_fac_ui  mpz_bin_uiui  |    mpz_fac_ui  mpz_bin_uiui
1         0.000000015  #0.000000014  |  #0.000000010   0.000000016
3        #0.000000015   0.000000077  |  #0.000000010   0.000000016
9        #0.000000016   0.000000096  |  #0.000000010   0.000000258
27        0.000000297  #0.000000230  |  #0.000000194   0.000000836
81        0.000001838  #0.000000966  |  #0.000000826   0.000001691
243       0.000007195  #0.000004460  |   0.000005391  #0.000004627
729       0.000047999  #0.000030608  |   0.000040048  #0.000013118
2187      0.000333120  #0.000229881  |   0.000263925  #0.000042094
6561     #0.002040726   0.002549343  |   0.001588065  #0.000151584
19683    #0.011657843   0.022333856  |   0.008881944  #0.000609732
59049    #0.080858608   0.198782997  |   0.044500135  #0.002539522
177147   #0.288538411   3.637505847  |   0.197642792  #0.011212615
531441   #1.381138015  33.224500000  |   0.961643126  #0.049363970

As you can see, bin_uiui was very slow for large operands, slower than
factorial! My implementation is slower for small operands, because it is
NOT tuned and does NOT switch between the many implementations.

Any comment will be very appreciated!

Regards,
Marco

-- 
http://bodrato.it/