Side 1 av 1

fakultet

Lagt inn: 09/08-2019 00:46
av Gjest
hvordan kan jeg regne 100 fakultet uten kalkulator?

Re: fakultet

Lagt inn: 09/08-2019 08:06
av jos
En vanlig lommeregner (TI-84 Plus) vil gi deg følgende svar: ERR OVERFLOW, hvis du ber om 100!. 100! er et tall med 158 sifre. Strirlings formel gir en god tilnærming. Se f.eks. https://kconrad.math.uconn.edu/blurbs/a ... irling.pdf

Re: fakultet

Lagt inn: 09/08-2019 12:57
av Nebuchadnezzar
Om du skal regne ut 100! eksakt uten kalkulator er det bare en ting å gjøre nemmlig å gjøre 100 multiplikasjonsstykker. Du tar 100 * 99 også gange 98 osv. Dette er den eneste måten som vil gi deg det eksakte svaret.

Anta i stedet at du er fornøyd med en tilnærmet verdi. Anta at $x$ er positiv, og $n$ er ett eller annet stort tall der er

$ \hspace{1cm}
n-1=\log_{10}(10^{n-1}) \leq \log_{10}(x) < \log_{10}(10^n) = n.
$

Slik at for å beregne antall siffer i ett tall kan du runde ned $\log_{10}(100)$ og legge til $1$.

$ \hspace{1cm}

\begin{align*}
\log_{10}(100!)
&= \sum_{k=1}^{100} \log_{10}(k) \approx \int_{1}^{100}\log_{10}(t)dt \\
&= \left.\frac{t\ln(t)-t}{\ln(10)}\right|_1^{100} = \frac{100 \log(100) - 99}{\log(10)} \approx 157.005
\end{align*}

$

For å ta det siste steget helt nøyaktig. Så har vi at $\log(100) = 2 \log(10)$ slik at

$ \hspace{1cm}
\frac{100 \log(100) - 99}{\log(10)} = \frac{200 \log(10) - 99}{\log(10)} = 200 - \frac{99}{\log(10)}
$

så vi trenger bare å finne en nøyaktig nok verdi for

$\hspace{1cm}
\log(10) = \log(2) + \log(5) = \log(2) + \log(4+1) = \log(2) + \log(4) + \log(1+1/4) = 3 \log 2 + \log(1+1/4)
$.

Vi har $\log(1+x) \approx x - x^2/2+x^3/3 + \cdots$ for små $x$ slik at $\log(1+1/4) \approx 43/192$.
Se her for enormt mange måter å beregne $\log(2)$ på
for nå sier jeg bare at $\log(2) \approx 693/1000$ Slik at vi endelig får

$\hspace{1cm}
\log(10) = 3 \log 2 + \log(1+1/4) = 3 \frac{693}{1000} + \frac{43}{192} = \frac{55271}{24000} \approx 2.3 = \frac{23}{10}
$

Endelig så er

$\hspace{1cm}
\begin{align*}
\text{Antall siffer}
& = \lfloor \log_{10}(100!) \rfloor + 1 \\
& = \left \lfloor 200 - \frac{99}{\log(10)} \right \rfloor + 1 \\
& \approx \left \lfloor 200 - \frac{99}{23/10} \right \rfloor + 1
\approx 157 + 1 = 158
\end{align*}
$

Som var det vi ønsket å vise.

------------------------------------------------------------------------

Grunnen til at vi kan forvente at dette fungerer er selve definisjonen av integralet som en Riemann sum.
Eksempelvis

$ \hspace{1cm}
\sum_{i=1}^{n} \log_{10}(i) < \int_1^n \log_{10}(t)dt < \sum_{i=2}^n\log(10,i) = \sum_{i=1}^n\log(10,i),
$

som illustrert for $n=20$ i det påfølgende bilde:

Bilde

Slik at,

$ \hspace{1cm}
\sum_{i=1}^{n} \log_{10}(i) - \sum_{i=1}^n\log(10,i) <
\int_1^n \log_{10}(t)dt - \sum_{i=1}^n\log(10,i) < 0.
$

Men verdien til venstre er bare $\log_10(100) = 2$. Så, integralet er en nedre grense for summen og kan ikke være mer enn $2$ unna den faktiske verdien. Dersom vi tar i betraktning at integralet
er omtrentlig midt mellom summene, burde feilleddet vre midnre enn $1$ som er grunnen til at vi traff svaret eksakt.

Re: fakultet

Lagt inn: 09/08-2019 13:18
av DennisChristensen
Løsningsforslag i python:

Kode: Velg alt

>>> def factorial(n):
       if n == 0:
           return 1
       return n * factorial(n - 1)

>>> factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Re: fakultet

Lagt inn: 09/08-2019 13:25
av Nebuchadnezzar

Kode: Velg alt

import math
print(math.factorial(100))

Re: fakultet

Lagt inn: 09/08-2019 21:43
av Aleks855

Kode: Velg alt

print("93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000")