Using Fold, create a function fac[n] that takes an integer n as argument and returns the factorial of n, that is, n(n – 1) (n – 2) 3·2·1.

The naive way to multiply x 22 would be to repeatedly multiply x by itself, performing 21 multiplications. But going as far back as about 200 BC in the Hindu classic Chandah-sutra, another method has been known that significantly reduces the total number of multiplications in performing such exponentiation. The idea is to first express the exponent in base 2.

Then starting with the second bit from the left, interpret a 1 to mean square the existing expression and multiply by x, and a 0 to mean multiply just by x. Implement this algorithm using FoldList.

In[1]: IntegerDigits[22, 2] Out [1] (1, 0, 1, 1, 0)