How to quickly calculate this product: 1/36*1/35*1/34*1/33*...*1/(36-n)?

Question

How to quickly calculate this product: $$1/36*1/35*1/34*1/33*...*1/(36-n)$$

This is neither arithmetic, nor geometric progression, so I am puzzled.

Answer 1

If you're looking for a closed form, it's this:

$$1/36*1/35*1/34*1/33*...*1/(36-n) = \frac{1}{\prod_{i=0}^n 36-i} = \frac{(35-n)!}{36!} $$

However, if you're looking for a fast way to compute this, according to Wikipedia, the best efficiency you can achieve is $O(n\big(log (n) \cdot log( log( n))\big)^2)$:

The asymptotically best efficiency is obtained by computing n! from its prime factorization. As documented by Peter Borwein, prime factorization allows n! to be computed in time O(n(log n log log n)2), provided that a fast multiplication algorithm is used (for example, the Schönhage–Strassen algorithm). Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve. See Wikipedia