Find the leading digit(s) of a factorial

Question

What are the better methods (algorithms) to computing the first number (or few leading numbers) of a large factorial.

Wolfram alpha seems pretty fast and handles large numbers. Is it accurate? Does it follow Find the first digit of a number approach?

Answer 1

I am not sure with the method Wolfram Alpha is using. But if you want to approximate big factorials, you might use the method you linked. It works fairly well if you use a sufficient amount of bits to represent floating point numbers (which I think, Wolframalpha has fair accuracy. Also not sure exact numbers on this).

Instead of just multiplication of lots of numbers, for factorials, you have Stirling approximation. (The logic behind this is same with what you linked) This can approximate value of $n!$ with quite nice accuracy. However, the usual "Stirling approximation formula" is not convergent (it means, it can have some big error for evaluating very big numbers), hence I suggest using it's variation which is proved to be convergent. You can see the formula here. https://en.wikipedia.org/wiki/Stirling%27s_approximation, under section "A convergent version of Stirling's Formula". It also lists some versions better for computations.

Answer 2

A first idea I think you can have is use modulus computation. For instance the "fast exponentiation" method uses a modulus in a certains base to speed up computation.

Here, if the factorial is divisible by 10, then you can take the modulus 10 of the factorial which won't change the first digit.

Then you would simply need to divise the result while there is more than 2 digits to get the first one. If you want to get more digits you can try to change the value in the second while to 100 but I don't think it will word all the time.

So we have this naive python algorithm :

import math 
def firstDigit(n) : 
    fact = 1

    for i in range(2, n + 1) : 
        fact = fact * i 

    while (fact % 10 == 0) :  
        fact = int(fact / 10) 

    while (fact >= 10) : 
        fact = int(fact / 10) 
  
    return math.floor(fact)