Naprawdę duże liczby

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. 10⁸⁰, 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:

,

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

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

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:

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 g_n:

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 . 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… g₆₄ :-)

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•