Cvičení — vytvoření funkce pro výpočet mocniny

V průběhu výkladu jsme se podívali, jak se programují funkce. Chtěli jsme naprogramovat funkci pro výpočet mocniny celého čísla na přirozený exponent. Naivní implementace se nepovedla, protože máme omezení ve velikosti čísla, které můžeme v počítači uložit. Navíc jsme zjistili, že neumíme udělat funkci tak, aby nám hlásila chyby.

Máme spočítat mocninu \(m = z^e\), kde z je celé číslo a e je přirozené číslo.

Naivní implementace

mocnina1.c

/* Výpočet mocniny v celých číslech
 * mocnina1.c
 * Naivní implementace funkce
 */
    

#include <stdio.h>
#include <limits.h>

// naivní implementace mocniny
// základ musi být celé číslo
// exponent musí být přirozené číslo
long long int mocnina( int zaklad, int exponent )
{
long long int vysledek = zaklad;

    if( exponent < 0 )  return 0; // exponent musí být kladný
    if( exponent == 0 ) return 1; // cokoliv na 0 je 1 podle definice
    if( exponent == 1 ) return vysledek; // zaklad na první je zaklad
    
    for( int i = 2; i <= exponent; i++ ) {
        vysledek *= zaklad;
    }

    return vysledek;
}

int main( int argc, char* argv[] )
{
int z = 2;
int e = 8;
long long int vysledek = 0;

    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    z = -3;
    e = 15;
    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    z = -3;
    e = 16;
    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    
return 0;
}

Sestavení programu mocnina1

gcc -Werror -o mocnina1 mocnina1.c

Tady to vypadá na první pohled, že počítáme dobře.

Výstup z programu mocnina1

jirka@pt3610:~/vyuka_sspvc/c_programming/mocniny$ ./mocnina1
Mocnina 2 na 8 je: 256
Mocnina -3 na 15 je: -14348907
Mocnina -3 na 16 je: 43046721

Zkusíme jiný test.

mocnina2.c

/* Výpočet mocniny v celých číslech
 * mocnina2.c
 * Naivní implementace funkce
 */
    

#include <stdio.h>
#include <limits.h>

// naivní implementace mocniny
// základ musi být cele číslo
// exponent musí být přirozené číslo
long long int mocnina( int zaklad, int exponent )
{
long long int vysledek = zaklad;

    if( exponent < 0 )  return 0; // exponent musí být kladný
    if( exponent == 0 ) return 1; // cokoliv na 0 je 1 podle definice
    if( exponent == 1 ) return vysledek; // zaklad na první je zaklad
    
    for( int i = 2; i <= exponent; i++ ) {
        vysledek *= zaklad;
    }

    return vysledek;
}

int main( int argc, char* argv[] )
{
int z = 2;
int e = 64;
long long int vysledek = 0;

    // dostaneme špatný výsledek, protože nám přeteče long long int
    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    z = -3;
    e = 55;
    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    z = -3;
    e = 66;
    vysledek = mocnina(z, e);
    printf("Mocnina %d na %d je: %lld\n", z, e, vysledek );
    
return 0;
}

Sestavení programu mocnina2

gcc -Werror -o mocnina2 mocnina2.c

Výstup z programu mocnina2

jirka@pt3610:~/vyuka_sspvc/c_programming/mocniny$ ./mocnina2
Mocnina 2 na 64 je: 0
Mocnina -3 na 55 je: 5935728490411247669
Mocnina -3 na 66 je: 4810798710570394889

Toto je evidentně špatně.

Lepší implementace funkce

Musíme vracet z funkce případnou chybu. To se dá udělat pomocí složeného typu struct, kde budeme moci vracet jak vypočtenou hodnotu, tak i informaci o tom, zda je tato hodnota správná nebo ne.

mocnina3.c

/* Výpočet mocniny v celých číslech
 * mocnina3.c
 * Implementace funkce s ošetřením přetečení.
 */
    

#include <stdio.h>
// v hlavičkovém souboru limits.h se nacházejí velikosti 
// maximální a minimální možné hodnoty čísel
#include <limits.h>
// v hlavičkovém souboru stdbool.h je definice typu bool
#include <stdbool.h>


// struktura pro mocninu
// v členu vysledek bude samontý výsledek 
// a v členu spravne bude true (správná hodnota) nebo false (chybná hodnota)
typedef struct {
    long long int   vysledek;
    bool            spravne;
} MOCNINA;

// lepší implementace mocniny
// zaklad musi být cele číslo
// exponent musí být přirozené číslo
// umíme hlásit chybu, je-li MOCNINA.spravne false, přetekl nám long long

MOCNINA mocnina( int zaklad, int exponent )
{
MOCNINA  m = { zaklad, false };

    if( exponent < 0 )  return m; // exponent musí být kladný
    if( exponent == 0 ) { // cokoliv na 0 je 1 podle definice
        m.vysledek = 1ll;
        m.spravne  = true;
        return m;
    }
    if( exponent == 1 ) { // zaklad na první je zaklad
        m.spravne = true;
        return m;
    }
    long long max = LLONG_MAX / (zaklad>0 ? zaklad: -zaklad) ;
    long long min = LLONG_MIN / (zaklad>0 ? zaklad: -zaklad) ;
    for( int i = 2; i <= exponent; i++ ) {
        // printf("Debug: v=%lld max=%lld min=%lld\n",m.vysledek, max,min);
        if( m.vysledek > min && m.vysledek < max ) {
            m.vysledek *= zaklad;
            m.spravne = true;
        } else {
            m.spravne = false;
            break;
        }
    }

    return m;
}

int main( int argc, char* argv[] )
{
int z = 2;
MOCNINA m = {0, false} ;

    // test funkce mocnina
    for( int e=0; e<128; e++) {
        m = mocnina(z, e);
        printf("Mocnina %d na %4d je: %20lld výsledek je %s\n", z, e, m.vysledek, 
               (m.spravne==true ? "dobře." : "špatně, přetekl nám long long.") );
        if( m.spravne == false ) {
            printf("Pro větší exponent než %d už neumím spočítat mocninu ze základu %d.\n",
                   e-1,z);
            break;
        }
    }
    
    z = -6;
    // test funkce mocnina
    for( int e=0; e<128; e++) {
        m = mocnina(z, e);
        printf("Mocnina %d na %4d je: %20lld výsledek je %s\n", z, e, m.vysledek, 
               (m.spravne==true ? "dobře." : "špatně, přetekl nám long long.") );
        if( m.spravne == false ) {
            printf("Pro větší exponent než %d už neumím spočítat mocninu ze základu %d.\n",
                   e-1,z);
            break;
        }
    }
return 0;
}

Sestavení programu mocnina3

gcc -Werror -o mocnina2 mocnina2.c

Výstup z programu mocnina3

jirka@pt3610:~/vyuka_sspvc/c_programming/mocniny$ ./mocnina3
Mocnina 2 na    0 je:                    1 výsledek je dobře.
Mocnina 2 na    1 je:                    2 výsledek je dobře.
Mocnina 2 na    2 je:                    4 výsledek je dobře.
Mocnina 2 na    3 je:                    8 výsledek je dobře.
Mocnina 2 na    4 je:                   16 výsledek je dobře.
Mocnina 2 na    5 je:                   32 výsledek je dobře.
Mocnina 2 na    6 je:                   64 výsledek je dobře.
Mocnina 2 na    7 je:                  128 výsledek je dobře.
Mocnina 2 na    8 je:                  256 výsledek je dobře.
Mocnina 2 na    9 je:                  512 výsledek je dobře.
Mocnina 2 na   10 je:                 1024 výsledek je dobře.
Mocnina 2 na   11 je:                 2048 výsledek je dobře.
Mocnina 2 na   12 je:                 4096 výsledek je dobře.
Mocnina 2 na   13 je:                 8192 výsledek je dobře.
Mocnina 2 na   14 je:                16384 výsledek je dobře.
Mocnina 2 na   15 je:                32768 výsledek je dobře.
Mocnina 2 na   16 je:                65536 výsledek je dobře.
Mocnina 2 na   17 je:               131072 výsledek je dobře.
Mocnina 2 na   18 je:               262144 výsledek je dobře.
Mocnina 2 na   19 je:               524288 výsledek je dobře.
Mocnina 2 na   20 je:              1048576 výsledek je dobře.
Mocnina 2 na   21 je:              2097152 výsledek je dobře.
Mocnina 2 na   22 je:              4194304 výsledek je dobře.
Mocnina 2 na   23 je:              8388608 výsledek je dobře.
Mocnina 2 na   24 je:             16777216 výsledek je dobře.
Mocnina 2 na   25 je:             33554432 výsledek je dobře.
Mocnina 2 na   26 je:             67108864 výsledek je dobře.
Mocnina 2 na   27 je:            134217728 výsledek je dobře.
Mocnina 2 na   28 je:            268435456 výsledek je dobře.
Mocnina 2 na   29 je:            536870912 výsledek je dobře.
Mocnina 2 na   30 je:           1073741824 výsledek je dobře.
Mocnina 2 na   31 je:           2147483648 výsledek je dobře.
Mocnina 2 na   32 je:           4294967296 výsledek je dobře.
Mocnina 2 na   33 je:           8589934592 výsledek je dobře.
Mocnina 2 na   34 je:          17179869184 výsledek je dobře.
Mocnina 2 na   35 je:          34359738368 výsledek je dobře.
Mocnina 2 na   36 je:          68719476736 výsledek je dobře.
Mocnina 2 na   37 je:         137438953472 výsledek je dobře.
Mocnina 2 na   38 je:         274877906944 výsledek je dobře.
Mocnina 2 na   39 je:         549755813888 výsledek je dobře.
Mocnina 2 na   40 je:        1099511627776 výsledek je dobře.
Mocnina 2 na   41 je:        2199023255552 výsledek je dobře.
Mocnina 2 na   42 je:        4398046511104 výsledek je dobře.
Mocnina 2 na   43 je:        8796093022208 výsledek je dobře.
Mocnina 2 na   44 je:       17592186044416 výsledek je dobře.
Mocnina 2 na   45 je:       35184372088832 výsledek je dobře.
Mocnina 2 na   46 je:       70368744177664 výsledek je dobře.
Mocnina 2 na   47 je:      140737488355328 výsledek je dobře.
Mocnina 2 na   48 je:      281474976710656 výsledek je dobře.
Mocnina 2 na   49 je:      562949953421312 výsledek je dobře.
Mocnina 2 na   50 je:     1125899906842624 výsledek je dobře.
Mocnina 2 na   51 je:     2251799813685248 výsledek je dobře.
Mocnina 2 na   52 je:     4503599627370496 výsledek je dobře.
Mocnina 2 na   53 je:     9007199254740992 výsledek je dobře.
Mocnina 2 na   54 je:    18014398509481984 výsledek je dobře.
Mocnina 2 na   55 je:    36028797018963968 výsledek je dobře.
Mocnina 2 na   56 je:    72057594037927936 výsledek je dobře.
Mocnina 2 na   57 je:   144115188075855872 výsledek je dobře.
Mocnina 2 na   58 je:   288230376151711744 výsledek je dobře.
Mocnina 2 na   59 je:   576460752303423488 výsledek je dobře.
Mocnina 2 na   60 je:  1152921504606846976 výsledek je dobře.
Mocnina 2 na   61 je:  2305843009213693952 výsledek je dobře.
Mocnina 2 na   62 je:  4611686018427387904 výsledek je dobře.
Mocnina 2 na   63 je:  4611686018427387904 výsledek je špatně, přetekl nám long long.
Pro větší exponent než 62 už neumím spočítat mocninu ze základu 2.
Mocnina -6 na    0 je:                    1 výsledek je dobře.
Mocnina -6 na    1 je:                   -6 výsledek je dobře.
Mocnina -6 na    2 je:                   36 výsledek je dobře.
Mocnina -6 na    3 je:                 -216 výsledek je dobře.
Mocnina -6 na    4 je:                 1296 výsledek je dobře.
Mocnina -6 na    5 je:                -7776 výsledek je dobře.
Mocnina -6 na    6 je:                46656 výsledek je dobře.
Mocnina -6 na    7 je:              -279936 výsledek je dobře.
Mocnina -6 na    8 je:              1679616 výsledek je dobře.
Mocnina -6 na    9 je:            -10077696 výsledek je dobře.
Mocnina -6 na   10 je:             60466176 výsledek je dobře.
Mocnina -6 na   11 je:           -362797056 výsledek je dobře.
Mocnina -6 na   12 je:           2176782336 výsledek je dobře.
Mocnina -6 na   13 je:         -13060694016 výsledek je dobře.
Mocnina -6 na   14 je:          78364164096 výsledek je dobře.
Mocnina -6 na   15 je:        -470184984576 výsledek je dobře.
Mocnina -6 na   16 je:        2821109907456 výsledek je dobře.
Mocnina -6 na   17 je:      -16926659444736 výsledek je dobře.
Mocnina -6 na   18 je:      101559956668416 výsledek je dobře.
Mocnina -6 na   19 je:     -609359740010496 výsledek je dobře.
Mocnina -6 na   20 je:     3656158440062976 výsledek je dobře.
Mocnina -6 na   21 je:   -21936950640377856 výsledek je dobře.
Mocnina -6 na   22 je:   131621703842267136 výsledek je dobře.
Mocnina -6 na   23 je:  -789730223053602816 výsledek je dobře.
Mocnina -6 na   24 je:  4738381338321616896 výsledek je dobře.
Mocnina -6 na   25 je:  4738381338321616896 výsledek je špatně, přetekl nám long long.
Pro větší exponent než 24 už neumím spočítat mocninu ze základu -6.

Pokud máme správně programovat v C, musíme pečlivě testovat naše programy.