Podľa starej indickej legendy, Sísa ben Dáhír, vezír kráľa Šírhama, vynašiel doskovú hru podobnú šachu. Naradostený kráľ sa rozhodol ho bohato odmeniť a spýtal sa ho, čo by si prial. Sísa riekol prosto: „chcem, aby si mi dal toľkoto ryže: na prvé políčko šachovnice jedno zrnko, na druhé dve zrnká, na tretie štyri, na štvrtá osem atď tak, aby na každom políčku bol dvojnásobok zrniek predošlého políčka.” Kráľ sa udivil tejto požiadavke: zdala sa mu príliš smiešna… keby však ovládal binárnu sústavu, veľmi rýchlo by zistil, že trvalo by veľmi veľmi dlho, kým by krajina vyprodukovala toľko obilia, koľko si vezír žiadal.

Len na poslednom políčku by bolo 2⁶³, teda 9 223 372 036 854 775 808, teda 9 triliónov zrniek (plus nejaké drobné). Celkový súčet je 2⁰ + 2¹ + … + 2⁶³, čo je 18 446 744 073 709 551 616, čiže 18 triliónov zrniek.

Poďme si to naprogramovať najprv v Jave a potom v C.

Prvý nástrel je:

public class SachoveZrnka {
    public static void main(String[] args) {
        int pocetPoliNaSachovnici = 8 * 8;

        int pocetZrn = 1;
        for (int i = 1; i <= pocetPoliNaSachovnici; i++) {          
            System.out.printf("%d. políčko: %d zŕn\n", i, pocetZrn);
            pocetZrn = pocetZrn * 2 ;
        }
    }
}

Akého typu má byť premenná pocetZrn? Aby sme sa nevyfailovali tak, ako úbohý vladár, nahliadnime to tabuľky dátových typov v Jave: tuto máme int, ktorý má rozsah -2^-31..2³¹ – 1, čo sa určite nezmestí. Správanie je inak komické:

30. políčko: 536870912 zŕn
31. políčko: 1073741824 zŕn
32. políčko: -2147483648 zŕn
33. políčko: 0 zŕn

Všimnime si na 32. políčku pretečenie čísla do záporných čísíel. Na 33. políčku je správanie už veľmi divné, číslo sa zrazilo na nulu.

Potrebujeme väčší rozsah!

Najbližší rozsiahlejší dátový typ v Jave je long, ale beda: ten má tiež len rozsah -2^-63..2⁶³ – 1, čo je stále málo.

Potrebujeme ešte väčší rozsah! Všetky ostatné rozsahy možno napchať do triedy java.lang.BigDecimal:

    int pocetPoliNaSachovnici = 8 * 8;

    BigDecimal sucet = BigDecimal.ONE;
    BigDecimal two = new BigDecimal(2);
    for (int i = 1; i <= pocetPoliNaSachovnici; i++) {          
        System.out.printf("%d. políčko: %s zŕn\n", i, sucet);
        sucet = sucet.multiply(two);
    }

API je pomerne nešťastné (ach, tá absencia preťažených operátorov…). Nezabudnime tiež zmeniť druhý parameter v printf() na %s, keďže vypisovať môžeme len stringovú reprezentáciu.

Teraz už to bude fungovať.

Ako na to v C?

Pozrime sa na rozsahy dátových typov v C. Tie sú zadefinované pomerne vágne: šírka pre long nie je menšia než šírka pre int a tá nie je menšia než šírka pre short. Ďalšie obmedzenia sú: short má aspoň 16 bitov, čo platí aj pre int a long má aspoň 32 bitov. (Štandard C99 definuje ešte long long: aspoň 64 bitový). Napodiv, na typickom linuxovskom systéme má long rovnakú veľkosť ako int (32 bitov).

Za behu môžete zistíť veľkosť dátového typu pomocou operátora sizeof:

printf("%d", sizeof(long));

Výsledkom na Windowse 7 pri kompilátore gcc je 4, čo zodpovedá 4 bajtom, teda 32 bitom, čo znamená, že sa doňho zmestí číslo od -2 147 483 647 .. 2 147 483 647, teda od -2³¹ do 2³¹ – 1.

Na rozdiel od Javy môžeme použiť bezznamienkové typy, kde sa rozsah posunie na interval 0..plus veľa. Ak použijeme

unsigned long pocetZrn = 1;

máme rozsah od 0..2³¹ – 1, čiže od 0..4 294 967 295.

Čo z toho vyplýva? So šachovnicou máme problémy: jednoducho sa nezmestíme :-)

Ale urobme nástrel implementácie:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int pocetPoliNaSachovnici = 8 * 8;
    unsigned long pocetZrn = 1;

    int i;
    for (i = 1; i <= pocetPoliNaSachovnici; i++) {
        printf("%d. políčko: %lu zŕn\n", i, pocetZrn);
        pocetZrn = pocetZrn * 2 ;
    }

    return EXIT_SUCCESS;
}

Výstup bude vyzerať:

31. políčko: 1073741824 zŕn
32. políčko: 2147483648 zŕn
33. políčko: 0 zŕn
34. políčko: 0 zŕn

Všimnime si parametre pre printf(): premenná typu unsigned long má byť vypisovaná cez %lu (l = long, u = unsigned).

Tak či onak, pri 32. políčku to pretečie. Je však možné, že na nejakej inej platforme, s magickými rozsahmi, to fungovať bude.

Smutný záver

Čo z toho vyplýva? Buď zmigrujte na štandard C99, kde je k dispozícii long long alebo… si naimplementujte či nájdite vlastnú knižnicu pre správu veľkých čisiel.