Silnia - pierwsza cyfra

[Dexous]

Mam za zadanie napisac program w ktorym musze wyznaczyc pierwsza oraz ostatnia niezerowa cyfra silni.
Z druga czescia zadania sobie poradzilem ale z pierwsza dalej mam klopoty. Czy istnieje jakikolwiek sposob wyznaczyc dokladnie jaka jest pierwsza cyfra silni ?
Przykladowo uzytkownik wprowadza liczbe \(\displaystyle{ 56}\) , a program zwraca \(\displaystyle{ 7}\).

( \(\displaystyle{ 56! = 710998587804863451854045647463724949736497978881168458687447040000000000000}\) )

Czytalem troche o wzorze Strlinga, ale wyniki podobno nie sa dokladne.

[Zordon]

Ciężko to udowodnić, ale licząc na double'ach w taki sposób:

Kod: Zaznacz cały

int n=56;
double x=1;
for(int i=1;i<=n;i++)
{
		x*=i;
                while(x>10) x/=10;
}

printf("%d\n",(int)x);

uzyskasz poprawny wynik (przynajmniej dla sensownie wielkich n)

edit:
Stirling też powinien zadziałać, liczysz logarytm dziesietny ze stirlinga, potem z tego mantyse - to bedzie logarytm z pierwszej cyfry (mniej więcej).

[Althorion]

A jak się chce bardziej kombinować i nie używać double'i (jestem zdania, że jak się miało problem i użyło liczb zmiennoprzecinkowych, to teraz ma się 1,99999999999 problemów):
1. Użyć GMP dla liczb całkowitych dowolnej długości.
2. Użyć jakiegoś szybkiego algorytmu liczącego silnię ->

Kod: Zaznacz cały

http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

3. Pierwsza cyfra to \(\displaystyle{ a_n = \frac{n!}{10^{\lfloor \log n! \rfloor}}}\). Ew. można skonwertować do stringa i wziąć pierwszą cyfrę, sprawdź co zadziała szybciej.