[Gcl-devel] Re: [Maxima] faster factorial

[Camm Maguire]

Greetings!

Richard Fateman <address@hidden> writes:

> I have another program that is about twice as fast as k.
> The code is much longer, and also produces an array of bits
> with 1 at the position of prime numbers
> up to n/2, but it uses code from commercial Macsyma.
> The mpz_fac_ui code may be faster in GMP 4.2.  I am guessing
> your test used GMP 4.1.14 or so.

Good guess -- 4.1.4.  Do you have specific reason to suspect
improvements in 4.2?

> I'm using Allegro CL, and I've been using destructive operations
> to avoid making new bignum (GMP) boxes.  It adds to the code size
> but reduces garbage collection (on the Lisp side, anyway) to zero.

Well, that at least is an advantage of a single gmp call, one bignum
creation. 

At some point, I should make a gmp3 package in gcl and export the
functions directly in lisp.

Take care,

> RJF
> Camm Maguire wrote:
> 
>           Greetings!
> 
> Well, I thought I could do better by bringing forward mpz_fac_ui, but:
> 
> (time (progn (setq a (si::factorial 100000) c 2) (= a c))) ;just call
>                                                            ;to mpz_fac_ui in 
> gmp
> 
> real time       :      0.560 secs
> run-gbc time    :      0.570 secs
> child run time  :      0.000 secs
> gbc time        :      0.000 secs
> NIL
> 
>   
> 
>                     (time (progn (setq a (k 100000 1) c 2) (= a c)))
>     
> 
> 
>      real time       :      0.450 secs
> run-gbc time    :      0.450 secs
> child run time  :      0.000 secs
> gbc time        :      0.000 secs
> NIL
> 
>   
> 
>      So I guess there is no interest in including such a factorial function
> in GCL.
> 
> Take care,
> 
> 
> "Richard Fateman" <address@hidden> writes:
> 
>   
> 
>                     For GCL, this program is faster than the much longer one 
> used in Maxima
> (defined in ASUM.lisp.).
> 
> Almost  3X faster computing 20000!  .
> 
> 
> (defun k (n m) ;; (k n 1) is n!
>   (declare (fixnum n m))
>   (if (<= n m) n
>     (* (k n (* 2 m))
>        (k (- n m)(* 2 m)))))
> 
> There are even faster ways, but I'm not sure how to actually use the
> GMP arithmetic to best advantage in GCL.
> 
> see http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf
> for more thoughts.
> 
> RJF
> 
> _______________________________________________
> Maxima mailing list
> address@hidden
> http://www.math.utexas.edu/mailman/listinfo/maxima
> 
> 
> 
>     
> 
> 
>        
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah