Naprawdę duże liczby

2009-11-18 16:38

Programując, rzadko mamy do czynienia z bardzo dużymi wartościami. Dowodem na to jest choćby fakt, że 32-bitowe systemy dopiero teraz zaczynają być w zauważalny sposób zastępowane 64-bitowymi. Jedynie w przypadku rozmiarów bardzo dużych plików operowanie zmiennymi mogącymi zmieścić wartości większe niż 4 miliardy jest konieczne.
Inne dziedziny życia i nauki przynoszą nam nieco większe wartości. Ekonomia czasami mówi o dziesiątkach bilionów (PKB dużych krajów), a fizyka często posługuje się wielkościami zapisywanymi przy pomocy notacji potęgowej – aż do ok. 1080, czyli szacowanej liczby wszystkich atomów we Wszechświecie.

Wydawać by się mogło, że wielkość ta jest bliska górnej granicy wartości, jakich kiedykolwiek moglibyśmy używać w sensownych zastosowaniach. Okazuje się jednak, że tak nie jest; co więcej, jakakolwiek liczba zapisana za pomocą co najwyżej potęgowania jest tak naprawdę bardzo, bardzo mała.
Do zapisywania naprawdę dużych liczb potrzebne są bowiem inne notacje. Jednym z takich sposobów zapisu jest notacja strzałkowa Knutha, która jest “naturalnym” rozszerzeniem operacji algebraicznych. Tak jak dodawanie jest iterowaną inkrementacją, mnożenie jest iterowanym dodawaniem, a potęgowanie – iterowanym mnożeniem:

a+b = a + \underbrace{1+1+\cdots+1}_{b}
a \times b = \underbrace{a+a+\cdots+b}_{b}
a^b = \underbrace{a \times a \times \cdots \times a}_{b},

tak każdy następny operator strzałkowy jest iterowaną wersją poprzedniego. I tak pierwszy z nich, a \uparrow b to zwykłe potęgowanie a^b, ale już drugi:

a \uparrow\uparrow b = \underbrace{a \uparrow a \uparrow \cdots \uparrow a}_{b} = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}

jest odpowiednikiem wielokrotnego podnoszenia danej liczby do jej potęgi. W ogólności, skracając ciąg n strzałek do \uparrow^{n}, otrzymujemy definicję:

a \uparrow^{n} b = \underbrace{a \uparrow^{n-1} \cdots \uparrow^{n-1} a}_{b}

Na pierwszy rzut oka może wydawać się to nieoczywiste, jednak już dla n = 3 i jednocyfrowych argumentów, wielkość liczb otrzymywanych przy użyciu notacji strzałkowej znacznie przekracza te, które można w wygodny sposób zapisać przy pomocy samego potęgowania. Chcąc je mimo wszystko przedstawić w tej postaci, trzeba się uciekać do sztuczek z klamerkami:

2 \uparrow\uparrow\uparrow 4 = \underbrace{2^{2^{.^{.^{.^2}}}}}_{2^{16}}

Oczywiście wraz ze wzrostem liczby strzałek nawet takie triki przestają wystarczać.

W tej chwili pewnie nasuwa się proste pytanie: czy z takiego systemu zapisu jest w ogóle jakiś pożytek, jeśli nikt nie posługuje się na poważnie tak wielkimi liczbami?… Odpowiedź jest jak najbardziej twierdząca, mimo że założenie w pytaniu jest nieprawdziwe. Otóż niektóre dziedziny matematyki używają nie tylko takich, ale i znacznie większych wartości – i nie chodzi tu nawet o teorię liczb, którą to jako pierwszą podejrzewalibyśmy o rzucanie liczbami “z kosmosu”.
Według Księgi Rekordów Guinnessa największą skończoną liczbą kiedykolwiek użytą w poważnym dowodzie matematycznym jest bowiem tzw. liczba Grahama, będącą górnym ograniczeniem pewnej wielkości występującej w problemie luźno związanym z grafami. Żeby ją zdefiniować, można użyć notacji strzałkowej – trzeba to jednak zrobić… iteracyjnie, wprowadzając pomocniczy ciąg gn:

\begin{cases} g_1 = 3 \uparrow\uparrow\uparrow\uparrow 4 \\ g_n = 3 \uparrow^{g_{n-1}} 3 \end{cases}

Już pierwszy jego wyraz nie daje się zapisać w postaci potęgowej, ale gwoździem programu jest zauważenie, że kolejne jego elementy posługują się poprzednimi w celu określenia liczby strzałek w operatorze \uparrow^{n}. Innymi słowy, mamy tu wejście na kolejny poziom abstrakcji i stoimy już chyba tak wysoko, że aż strach spoglądać w dół ;)
Co jednak ze wspomnianą wcześniej liczbą Grahama? Teraz na szczęście jej określenie jest już bardzo proste. Jest ona równa ni mniej, ni więcej, jak tylko… g64 :-)

Tags: ,
Author: Xion, posted under Math »


8 comments for post “Naprawdę duże liczby”.
  1. Aithne:
    November 18th, 2009 o 18:58

    Karolu, “naprawdę duże liczby” powinno oznaczać duże liczby, a nie takie karły jak liczba Grahama…

  2. Alton:
    November 18th, 2009 o 19:44

    Czy taki tekst jak ten w komentarzu powyżej ma jakikolwiek sens, oprócz popisania się jaki to autor jest fajny, obcykany w matematyce i w ogóle wszedł na Nty poziom abstrakcji?
    Każdy moze sobie rzucić taki komentarz, bo to w sumie nic nie znaczy.
    A notka ciekawa, jak zwykle na tym blogu :)

  3. Anaksagoras:
    November 18th, 2009 o 23:40

    Daj spokój Alton…

    Dla Aithne dzień bez
    http://dzizas.blogspot.com/2009/09/pierd.html
    to dzień stracony…

    Jakby taki nasz gamedevowy … Palikot :P

    No i niech lepiej sama założy bloga i niech pisze na nim ciekawsze rzeczy

  4. Brimbirimbi:
    November 19th, 2009 o 11:41

    Jeśli takie liczby są jeszcze za małe.. zawsze można użyć czegoś, co, jeśli dobrze pamiętam, nazywa się “nadsilnią”:
    n\$ = \underbrace{ n!^{n!^{\cdots^{n!}}}}_{n! \text{ razy}}
    Taka ciekawostka zapamiętana z czasów studienckich.. ciekawe czy z tamtych czasów jeszcze składnię TeXa dobrze pamiętam :D
    Podglądu posta niestety nie ma więc nie ręczę za poprawność.. jakby co to: n$ = n!^n!^n!.. i tak n! razy. Koszmarne wartość już przy 3$.

  5. Xion:
    November 19th, 2009 o 16:46

    Niestety niespecjalnie pamiętasz, musiałem poprawić :) (Nawias dolny robi się przez \underbrace{wyr. na górze}_{wyr. na dole})

    A co do tej “nadsilni”, to rzeczywiście na pierwszy rzut oka robi wrażenie. Ale tylko na pierwszy :) Notacja strzałkowa daje bowiem większe liczby, co pokusiłem się nawet udowodnić :> Jak?
    Przede wszystkim wiemy, że:

    n! = 1 \times 2 \times \cdots \times n \le n\times \cdots \times n = n^n

    wobec czego:

    n\$ \le \underbrace{(n^n)^{(n^n)^{\cdots^{n^n}}}}_{n^n \text{ razy}}

    Jeśli teraz pozbędziemy się tych nawiasów, to otrzymamy nawet większą liczbę:
    \cdots \le \underbrace{n^{\cdots^{n}}}_{2 \times n^n \text{ razy}}

    (bo (x^x)^{x^x} < x^{x^{x^{x}}} już dla x = 2).

    Takie piętrowe potęgowanie tych samych liczb wygląda znajomo – i istotnie, to nic innego jak:

    \cdots = n \uparrow\uparrow (2 \times n^n)

    a jeśli nie chcemy w ogóle potęgowania, to po prostu:

    \cdots \le n \uparrow\uparrow\uparrow n

    Tak więc n$ można ograniczyć z łatwością przez proste wyrażenie używające notacji strzałkowej – c.b.d.o. :) Dodam jeszcze, że wszystkie nierówności występujące tutaj są bardzo zgrubnymi ograniczeniami :] W sumie więc relacja n$ do strzałek wygląda mniej więcej tak:

    n^n = n \uparrow n \le n \uparrow\uparrow n \le n\$ = n! \uparrow\uparrow n! \ll n \uparrow\uparrow\uparrow n

    Czyli n$ jest między dwiema a trzema strzałkami :)

  6. Aithne:
    November 19th, 2009 o 19:28

    Kiedyś po prostu na pewnym forum (bodajże forum FASMa to było) zrobili sobie zabawę polegającą na podaniu jak największej liczby w dziewięciu znakach, a że padały tam znacznie większe liczby, to G wydaje mi się małe… Tu jest sporo o dużych liczbach. Naprawdę dużych.

  7. Xion:
    November 20th, 2009 o 0:18

    Aithne: G rzeczywiście nie jest duże w porównaniu chociażby do wartości funkcji busy-beaver dla odpowiednio dużych argumentów. Jednak o ile po np. BB(100) tej wielkości w ogóle nie widać, tak zagnieżdżona rekurencyjna definicja G – w której kolejne elementy ciągu służą jako rząd i tak już dającego gigantyczne rezultaty operatora – jest pod tym względem o wiele bardziej sugestywna.

  8. Anonymous:
    September 4th, 2013 o 17:31

    To grahma
    .

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.