Hlavní navigace

Algoritmus CORDIC v FX formátu a goniometrické funkce

Pavel Tišnovský 2. 8. 2006

V poslední části seriálu věnovaného matematickým výpočtům dokončíme popis implementace všestranného algoritmu CORDIC realizovaného nad čísly s pevnou řádovou čárkou. Zaměříme se na zbylé goniometrické funkce a přiblížíme si problematiku chyb vzniklých volbou malého počtu iterací při provádění rotací vektorů algoritmem CORDIC.

Obsah

1. Výpočet goniometrických funkcí sin() a cos()
2. Funkce pro výpočet sin() algoritmem CORDIC
3. Vliv počtu iterací na přesnost výpočtů funkce sin()
4. Funkce pro výpočet cos() algoritmem CORDIC
5. Vliv počtu iterací na přesnost výpočtů funkce cos()
6. Literatura
7. Odkazy na Internetu
8. Slovo závěrem

1. Výpočet goniometrických funkcí sin() a cos()

Jak je již z názvu první kapitoly patrné, dnes se budeme zabývat výpočty goniometrických funkcí pomocí algoritmu CORDIC, přičemž všechny výpočty budou prováděny ve formátu pevné řádové binární čárky. Konkrétně se bude jednat o formát čísel se znaménkem, kde počet bitů před binární řádovou čárkou i za binární řádovou čárkou je shodný a dosahuje hodnoty šestnácti bitů: A=B=16. Na začátku si pro zopakování řekněme, jakým způsobem se algoritmus CORDIC používá pro výpočet funkcí sinus a kosinus. Nejprve je vypočtena tabulka úhlů (tj. arkustangenty záporných druhých mocnin dvojky) naprosto stejným způsobem jako v demonstračním příkladu uvedeném minule. Po vytvoření této tabulky je již možné CORDIC spustit. Počáteční souřadnice vektoru r jsou nastaveny na hodnotu [1, 0] (samozřejmě až po převodu na formát pevné řádové binární čárky, což je ovšem pro hodnoty 1 a 0 triviální). Vektor je posléze v iterační smyčce rotován tak dlouho, dokud neproběhne daný počet iterací.

Úhel vektoru r se přitom z počáteční hodnoty 0 neustále přibližuje k zadanému úhlu δ, jelikož se v iterační smyčce zadaný úhel adaptivně buď zmenšuje či zvětšuje o hodnotu uloženou v tabulce atans[] (zde se jedná o posloupnost, ve které se čísla neustále zmenšují, proto je konvergence ke správnému výsledku zaručena). Výsledek, tj. hodnoty funkcí sinus a kosinus, je uložen v nových souřadnicích vektoru r (v našem případě vynásobený o konstantu K_fx, což je ve skutečnosti konstanta F_float převedená pro snazší výpočty do formátu FX), a to z toho důvodu, že vektor rotoval na jednotkové kružnici a souřadnice jakéhokoli bodu ležícího na jednotkové kružnici přímo odpovídají hodnotám sinu a kosinu úhlu tohoto bodu a počátku souřadné soustavy počítaného od kladné horizontální poloosy. Nejprve si ukažme funkci, která vypočte tabulku úhlů pro záporné druhé mocniny čísla dvě (i tuto funkci jsme si uváděli minule):

#define MAX_ITER dostatečně_velké_číslo

/*
 * Vytvoření tabulky pro výpočet goniometrických
 * funkcí pomocí algoritmu CORDIC
 */
void fx_create_tables(void)
{
    int i;
    for (i=0; i<MAX_ITER; i++) {
        double p=pow(2.0, -i);
        atans[i]=fp2fx(atan(p));
        pows[i]=fp2fx(p);
    }
} 

Obsah tabulky si můžeme pro jistotu vypsat na standardní výstup:

    /* kontrolní výpis tabulky atans[] */
    for (i=0; i<MAX_ITER; i++)
        printf("%d\t%f\n", i, fx2fp(rad2deg(atans[i]))); 

Dále si uveďme výpočet konstanty K uložené ve formátu pevné řádové binární čárky:

/* počet míst před a za binární řádovou čárkou */
#define A 16
#define B 16

/* "zesílení" při rotacích */
#define K_float 0.6073

/* převod K do formátu FX */
static fx K_fx=(fx)(K_float*(2<<(B-1))); 

2. Funkce pro výpočet sin() algoritmem CORDIC

Výpočet goniometrické funkce sin() pomocí algoritmu CORDIC je při použití formátu pevné řádové binární čárky velmi snadný a současně i přímočarý. Dokonce je možné říci, že výpočet je oproti verzi používající plovoucí řádovou čárku jednodušší, a to z toho důvodu, že se místo pomocné tabulky s druhými mocninami čísla dvě přímo používá operace pro aritmetický posuv doprava (ten je podporován přímo centrální procesorovou jednotkou, jedná se tedy o znatelné zrychlení celého výpočtu). Při implementaci algoritmu CORDIC v programovacím jazyku C může funkce pro výpočet sinu vypadat následovně (připomeňme si, že výsledek je uložen v y-ové složce orotovaného vektoru r):

/* výpočet funkce sin() pro zadaný úhel delta */
fx fx_sin_cordic_optim(fx delta)
{
    int i;
    static fx K_fx=(fx)(K_float*(2<<(B-1)));
    /* nastavení počátečních podmínek */
    fx x0=int2fx(1);
    fx y0=0;
    fx xn;
    for (i=0; i<MAX_ITER; i++) {            /* iterační smyčka */
        if (delta<0) {                      /* úhel je záporný => rotace doleva */
            xn=fx_add(x0, y0>>i);           /* místo násobení bitový posuv */
            y0=fx_sub(y0, x0>>i);
            delta=fx_add(delta, atans[i]);
        }
        else {                              /* úhel je kladný => rotace doprava */
            xn=fx_sub(x0, y0>>i);
            y0=fx_add(y0, x0>>i);
            delta=fx_sub(delta, atans[i]);
        }
        x0=xn;
    }
    return fx_mul(y0, K_fx);                /* opravit "zesílení" výsledku */
} 

Výše uvedenou Céčkovskou funkci fx_sin_cordic_op­tim() si můžeme otestovat na výpočtu úhlů ležících v prvním kvadrantu, tj. od 0° do 90°. Kromě vypočtených hodnot je u každého úhlu uvedena i hodnota vypočtená pomocí FPU, dále pak absolutní a relativní chyba. Tučně jsou zvýrazněny ty relativní chyby, které jsou menší než jedno procento:

Výpočet funkce sin() optimalizovanou metodou CORDIC

Úhel sin() dle CORDIC sin() dle FPU absolutní chyba relativní chyba
00 0.0000000000 0.0000000000 0.0000000000 0.000%
01 0.0165557861 0.0174524064 0.0008966203 5.138%
02 0.0331115723 0.0348994967 0.0017879244 5.123%
03 0.0520324707 0.0523359562 0.0003034855 0.580%
04 0.0685882568 0.0697564737 0.0011682169 1.675%
05 0.0851440430 0.0871557427 0.0020116998 2.308%
06 0.1040649414 0.1045284633 0.0004635219 0.443%
07 0.1206207275 0.1218693434 0.0012486159 1.025%
08 0.1371765137 0.1391731010 0.0019965873 1.435%
09 0.1537322998 0.1564344650 0.0027021652 1.727%
10 0.1726531982 0.1736481777 0.0009949794 0.573%
11 0.1892089844 0.1908089954 0.0016000110 0.839%
12 0.2057647705 0.2079116908 0.0021469203 1.033%
13 0.2223205566 0.2249510543 0.0026304977 1.169%
14 0.2388763428 0.2419218956 0.0030455528 1.259%
15 0.2577972412 0.2588190451 0.0010218039 0.395%
16 0.2743530273 0.2756373558 0.0012843285 0.466%
17 0.2909088135 0.2923717047 0.0014628912 0.500%
18 0.3074645996 0.3090169944 0.0015523948 0.502%
19 0.3240203857 0.3255681545 0.0015477687 0.475%
20 0.3405761719 0.3420201433 0.0014439715 0.422%
21 0.3571319580 0.3583679495 0.0012359915 0.345%
22 0.3713226318 0.3746065934 0.0032839616 0.877%
23 0.3878784180 0.3907311285 0.0028527105 0.730%
24 0.4044342041 0.4067366431 0.0023024390 0.566%
25 0.4209899902 0.4226182617 0.0016282715 0.385%
26 0.4351806641 0.4383711468 0.0031904827 0.728%
27 0.4517364502 0.4539904997 0.0022540495 0.496%
28 0.4659271240 0.4694715628 0.0035444388 0.755%
29 0.4824829102 0.4848096202 0.0023267101 0.480%
30 0.4966735840 0.5000000000 0.0033264160 0.665%
31 0.5132293701 0.5150380749 0.0018087048 0.351%
32 0.5274200439 0.5299192642 0.0024992203 0.472%
33 0.5416107178 0.5446390350 0.0030283172 0.556%
34 0.5558013916 0.5591929035 0.0033915119 0.607%
35 0.5699920654 0.5735764364 0.0035843709 0.625%
36 0.5841827393 0.5877852523 0.0036025130 0.613%
37 0.5983734131 0.6018150232 0.0034416101 0.572%
38 0.6125640869 0.6156614753 0.0030973884 0.503%
39 0.6267547607 0.6293203910 0.0025656303 0.408%
40 0.6385803223 0.6427876097 0.0042072874 0.655%
41 0.6527709961 0.6560590290 0.0032880329 0.501%
42 0.6669616699 0.6691306064 0.0021689364 0.324%
43 0.6787872314 0.6819983601 0.0032111286 0.471%
44 0.6906127930 0.6946583705 0.0040455775 0.582%
45 0.7048034668 0.7071067812 0.0023033144 0.326%
46 0.7166290283 0.7193398003 0.0027107720 0.377%
47 0.7284545898 0.7313537016 0.0028991118 0.396%
48 0.7402801514 0.7431448255 0.0028646741 0.385%
49 0.7521057129 0.7547095802 0.0026038673 0.345%
50 0.7615661621 0.7660444431 0.0044782810 0.585%
51 0.7733917236 0.7771459615 0.0037542378 0.483%
52 0.7852172852 0.7880107536 0.0027934685 0.354%
53 0.7946777344 0.7986355100 0.0039577757 0.496%
54 0.8065032959 0.8090169944 0.0025136985 0.311%
55 0.8159637451 0.8191520443 0.0031882992 0.389%
56 0.8254241943 0.8290375726 0.0036133782 0.436%
57 0.8348846436 0.8386705679 0.0037859244 0.451%
58 0.8443450928 0.8480480962 0.0037030034 0.437%
59 0.8538055420 0.8571673007 0.0033617587 0.392%
60 0.8632659912 0.8660254038 0.0027594126 0.319%
61 0.8703613281 0.8746197071 0.0042583790 0.487%
62 0.8798217773 0.8829475929 0.0031258155 0.354%
63 0.8869171143 0.8910065242 0.0040894099 0.459%
64 0.8940124512 0.8987940463 0.0047815951 0.532%
65 0.9034729004 0.9063077870 0.0028348866 0.313%
66 0.9105682373 0.9135454576 0.0029772203 0.326%
67 0.9176635742 0.9205048535 0.0028412792 0.309%
68 0.9223937988 0.9271838546 0.0047900557 0.517%
69 0.9294891357 0.9335804265 0.0040912908 0.438%
70 0.9365844727 0.9396926208 0.0031081481 0.331%
71 0.9413146973 0.9455185756 0.0042038783 0.445%
72 0.9460449219 0.9510565163 0.0050115944 0.527%
73 0.9531402588 0.9563047560 0.0031644972 0.331%
74 0.9578704834 0.9612616959 0.0033912125 0.353%
75 0.9626007080 0.9659258263 0.0033251183 0.344%
76 0.9673309326 0.9702957263 0.0029647937 0.306%
77 0.9696960449 0.9743700648 0.0046740199 0.480%
78 0.9744262695 0.9781476007 0.0037213312 0.380%
79 0.9767913818 0.9816271834 0.0048358016 0.493%
80 0.9815216064 0.9848077530 0.0032861466 0.334%
81 0.9838867188 0.9876883406 0.0038016218 0.385%
82 0.9862518311 0.9902680687 0.0040162377 0.406%
83 0.9886169434 0.9925461516 0.0039292083 0.396%
84 0.9909820557 0.9945218954 0.0035398397 0.356%
85 0.9909820557 0.9961946981 0.0052126424 0.523%
86 0.9933471680 0.9975640503 0.0042168823 0.423%
87 0.9933471680 0.9986295348 0.0052823668 0.529%
88 0.9957122803 0.9993908270 0.0036785467 0.368%
89 0.9957122803 0.9998476952 0.0041354149 0.414%
90 0.9957122803 1.0000000000 0.0042877197 0.429%

Statistické vlastnosti výpočtu

Počet iterací: 16
Součet absolutních chyb: 0.270
Součet relativních chyb: 59.119%
Průměrná absolutní chyba: 0.003
Průměrná relativní chyba: 0.650%

3. Vliv počtu iterací na přesnost výpočtů funkce sin()

V předchozí kapitole jsme si uvedli výsledky výpočtů funkce sinus pro šestnáct iterací. Proč jsem však zvolil zrovna tuto hodnotu? Stanovit optimální počet iterací je poněkud ošemetné. Malý počet iterací má za následek zvýšení chyb při výpočtu, výpočty však budou prováděny značně rychleji. Naopak příliš velký počet iterací může výpočet zpomalit, a to bez vlivu na přesnost výsledku, protože při použití FX aritmetiky je omezený pouze počet bitů za binární řádovou čárkou. Jako pravidlo je možné uvést, že počet iterací by měl být zhruba shodný s počtem významových bitů umístěných za binární řádovou čárkou. Dokonce se o tom můžeme přesvědčit při použití mírně upravené funkce pro výpočet sinu algoritmem CORDIC:

/* výpočet funkce sin() pro zadaný úhel delta */
/* a maximální počet iterací                  */
fx fx_sin_cordic_optim_iter(fx delta, int iter)
{
    int i;
    static fx K_fx=(fx)(K_float*(2<<(B-1)));
    /* nastavení počátečních podmínek */
    fx x0=int2fx(1);
    fx y0=0;
    fx xn;
    for (i=0; i<iter; i++) {                /* iterační smyčka */
        if (delta<0) {                      /* úhel je záporný => rotace doleva */
            xn=fx_add(x0, y0>>i);           /* místo násobení bitový posuv */
            y0=fx_sub(y0, x0>>i);
            delta=fx_add(delta, atans[i]);
        }
        else {                              /* úhel je kladný => rotace doprava */
            xn=fx_sub(x0, y0>>i);
            y0=fx_add(y0, x0>>i);
            delta=fx_sub(delta, atans[i]);
        }
        x0=xn;
    }
    return fx_mul(y0, K_fx);                /* opravit "zesílení" výsledku */
} 

Tuto funkci využijeme v následujícím testovacím programu, který vypočte statistické informace o chybách pro maximální počet iterací jdoucí od 1 do 32:

int main(void)
{
    int i;
    fx     sinfx;
    double delta;                           /* úhel, ze kterého se funkce počítá */
    double value;                           /* vypočtené hodnoty */
    double abs_err;                         /* absolutní chyby */
    double rel_err;                         /* relativní chyby */
    double sum_abs_err=0.0;                 /* součet chyb */
    double sum_rel_err=0.0;                 /* součet chyb */
    int iter;                               /* počitadlo iterací */

    fx_create_tables();

    /* výpočet sin() optimalizovanou metodou CORDIC */
    puts("\n<h2>Vliv počtu iterací na výpočet sin() optimalizovanou metodou CORDIC</h2>\n");
    puts("<table>");
    puts("<tr>"\
         "<th><strong>Počet iterací:</strong></th>"\
         "<th><strong>Součet absolutních chyb:</strong></th>"\
         "<th><strong>Součet relativních chyb:</strong></th>"\
         "<th><strong>Průměrná absolutní chyba:</strong></th>"\
         "<th><strong>Průměrná relativní chyba:</strong></th></tr>");
    for (iter=1; iter<=32; iter++) {
        sum_abs_err=0.0;
        sum_rel_err=0.0;
        for (i=0; i<=90; i++) {                 /* výpočetní smyčka */
            delta=deg2rad(i);                   /* převod úhlu na radiány */
            sinfx=fx_sin_cordic_optim_iter(fp2fx(delta), iter);  /* aplikace algoritmu CORDIC */
            value=fx2fp(sinfx);                 /* výpočet funkce sin */
            abs_err=fabs(value-sin(delta));     /* výpočet absolutních chyb */
            rel_err=sin(delta)==0 ? 0:100.0*abs_err/sin(delta);
            sum_abs_err+=abs_err;
            sum_rel_err+=rel_err;
        }
        printf("<tr><td>%d</td><td>%5.3f</td><td>%5.3f%%</td><td>%5.3f</td><td>%5.3f%%</td></tr>\n",
               iter, sum_abs_err, sum_rel_err, sum_abs_err/91.0, sum_rel_err/91.0);
    }
    puts("</table>");
    return 0;
} 

Výsledky běhu předešlého testovacího příkladu jsou velmi zajímavé, zejména při pohledu na zlom okolo hranice čtrnácti iterací:

Vliv počtu iterací na výpočet sin() optimalizovanou metodou CORDIC

Počet iterací: Součet absolutních chyb: Součet relativních chyb: Průměrná absolutní chyba: Průměrná relativní chyba:
1 25.036 12524.416% 0.275 137.631%
2 11.925 5697.160% 0.131 62.606%
3 6.387 2056.063% 0.070 22.594%
4 3.565 1876.936% 0.039 20.626%
5 1.741 673.899% 0.019 7.405%
6 0.939 461.678% 0.010 5.073%
7 0.547 231.200% 0.006 2.541%
8 0.362 113.516% 0.004 1.247%
9 0.294 68.732% 0.003 0.755%
10 0.272 60.653% 0.003 0.667%
11 0.268 59.101% 0.003 0.649%
12 0.265 57.142% 0.003 0.628%
13 0.275 63.638% 0.003 0.699%
14 0.265 57.773% 0.003 0.635%
15 0.270 59.119% 0.003 0.650%
16 0.270 59.119% 0.003 0.650%
17 0.272 59.119% 0.003 0.650%
18 0.272 59.119% 0.003 0.650%
19 0.272 59.119% 0.003 0.650%
20 0.272 59.119% 0.003 0.650%
21 0.272 59.119% 0.003 0.650%
22 0.272 59.119% 0.003 0.650%
23 0.272 59.119% 0.003 0.650%
24 0.272 59.119% 0.003 0.650%
25 0.272 59.119% 0.003 0.650%
26 0.272 59.119% 0.003 0.650%
27 0.272 59.119% 0.003 0.650%
28 0.272 59.119% 0.003 0.650%
29 0.272 59.119% 0.003 0.650%
30 0.272 59.119% 0.003 0.650%
31 0.272 59.119% 0.003 0.650%
32 0.272 59.119% 0.003 0.650%

4. Funkce pro výpočet cos() algoritmem CORDIC

Goniometrická funkce kosinus se při použití algoritmu CORDIC počítá prakticky stejným způsobem, jako funkce sinus. Jediný rozdíl spočívá v tom, že po dokončení rotace vektoru r je hodnota sinu uložena v jeho y-ové složce, zatímco hodnota kosinu ve složce x-ové. Zdrojový tvar céčkovské funkce na výpočet kosinu je tedy nepatrně odlišný v posledním řádku:

/* výpočet funkce cos() pro zadaný úhel delta */
fx fx_cos_cordic_optim(fx delta)
{
    int i;
    static fx K_fx=(fx)(K_float*(2<<(B-1)));
    /* nastavení počátečních podmínek */
    fx x0=int2fx(1);
    fx y0=0;
    fx xn;
    for (i=0; i<MAX_ITER; i++) {            /* iterační smyčka */
        if (delta<0) {                      /* úhel je záporný => rotace doleva */
            xn=fx_add(x0, y0>>i);           /* místo násobení bitový posuv */
            y0=fx_sub(y0, x0>>i);
            delta=fx_add(delta, atans[i]);
        }
        else {                              /* úhel je kladný => rotace doprava */
            xn=fx_sub(x0, y0>>i);
            y0=fx_add(y0, x0>>i);
            delta=fx_sub(delta, atans[i]);
        }
        x0=xn;
    }
    return fx_mul(x0, K_fx);                /* opravit "zesílení" výsledku */
} 

Výpočet funkce cos() optimalizovanou metodou CORDIC

Výsledky výpočtu funkce kosinus pro šestnáct iterací algoritmu CORDIC jsou zobrazeny v následující tabulce. Opět jsou zvýrazněny ty úhly, pro něž je relativní chyba menší než jedno procento.

Úhel cos() dle CORDIC cos() dle FPU absolutní chyba relativní chyba
00 0.996 1.000 0.004 0.429%
01 0.996 1.000 0.004 0.414%
02 0.996 0.999 0.004 0.368%
03 0.993 0.999 0.005 0.529%
04 0.993 0.998 0.004 0.423%
05 0.991 0.996 0.005 0.523%
06 0.991 0.995 0.004 0.356%
07 0.989 0.993 0.004 0.396%
08 0.986 0.990 0.004 0.406%
09 0.984 0.988 0.004 0.385%
10 0.982 0.985 0.003 0.334%
11 0.977 0.982 0.005 0.493%
12 0.974 0.978 0.004 0.380%
13 0.970 0.974 0.005 0.480%
14 0.967 0.970 0.003 0.306%
15 0.963 0.966 0.003 0.344%
16 0.958 0.961 0.003 0.353%
17 0.953 0.956 0.003 0.331%
18 0.946 0.951 0.005 0.527%
19 0.941 0.946 0.004 0.445%
20 0.937 0.940 0.003 0.331%
21 0.929 0.934 0.004 0.438%
22 0.922 0.927 0.005 0.517%
23 0.918 0.921 0.003 0.309%
24 0.911 0.914 0.003 0.326%
25 0.903 0.906 0.003 0.313%
26 0.894 0.899 0.005 0.532%
27 0.887 0.891 0.004 0.459%
28 0.880 0.883 0.003 0.354%
29 0.870 0.875 0.004 0.487%
30 0.863 0.866 0.003 0.319%
31 0.854 0.857 0.003 0.392%
32 0.844 0.848 0.004 0.437%
33 0.835 0.839 0.004 0.451%
34 0.825 0.829 0.004 0.436%
35 0.816 0.819 0.003 0.389%
36 0.807 0.809 0.003 0.311%
37 0.795 0.799 0.004 0.496%
38 0.785 0.788 0.003 0.354%
39 0.773 0.777 0.004 0.483%
40 0.762 0.766 0.004 0.585%
41 0.752 0.755 0.003 0.345%
42 0.740 0.743 0.003 0.385%
43 0.728 0.731 0.003 0.396%
44 0.717 0.719 0.003 0.377%
45 0.705 0.707 0.002 0.326%
46 0.691 0.695 0.004 0.582%
47 0.679 0.682 0.003 0.471%
48 0.667 0.669 0.002 0.324%
49 0.653 0.656 0.003 0.501%
50 0.639 0.643 0.004 0.655%
51 0.627 0.629 0.003 0.408%
52 0.613 0.616 0.003 0.503%
53 0.598 0.602 0.003 0.572%
54 0.584 0.588 0.004 0.613%
55 0.570 0.574 0.004 0.625%
56 0.556 0.559 0.003 0.607%
57 0.542 0.545 0.003 0.556%
58 0.527 0.530 0.002 0.472%
59 0.513 0.515 0.002 0.351%
60 0.497 0.500 0.003 0.665%
61 0.482 0.485 0.002 0.480%
62 0.466 0.469 0.004 0.755%
63 0.452 0.454 0.002 0.496%
64 0.435 0.438 0.003 0.728%
65 0.421 0.423 0.002 0.385%
66 0.404 0.407 0.002 0.566%
67 0.388 0.391 0.003 0.730%
68 0.371 0.375 0.003 0.877%
69 0.357 0.358 0.001 0.345%
70 0.341 0.342 0.001 0.422%
71 0.324 0.326 0.002 0.475%
72 0.307 0.309 0.002 0.502%
73 0.291 0.292 0.001 0.500%
74 0.274 0.276 0.001 0.466%
75 0.258 0.259 0.001 0.395%
76 0.239 0.242 0.003 1.259%
77 0.222 0.225 0.003 1.169%
78 0.206 0.208 0.002 1.033%
79 0.189 0.191 0.002 0.839%
80 0.173 0.174 0.001 0.573%
81 0.154 0.156 0.003 1.727%
82 0.137 0.139 0.002 1.435%
83 0.121 0.122 0.001 1.025%
84 0.104 0.105 0.000 0.443%
85 0.085 0.087 0.002 2.308%
86 0.069 0.070 0.001 1.675%
87 0.052 0.052 0.000 0.580%
88 0.033 0.035 0.002 5.123%
89 0.017 0.017 0.001 5.138%
90 –0.002 0.000 0.002 0.000%

5. Vliv počtu iterací na přesnost výpočtů funkce cos()

Podobně jako u funkce sinus, i u kosinu je možné zjistit vliv maximálního počtu iterací algoritmu CORDIC na přesnost výpočtů funkce. Jelikož jsme použili FX formát s šestnácti bity umístěnými za binární řádovou čárkou, je možné předpokládat, že optimální bude použití šestnácti iterací, o čemž se můžeme přesvědčit po překladu a spuštění následujícího testovacího příkladu.

Vliv počtu iterací na výpočet cos() optimalizovanou metodou CORDIC

int main(void)
{
    int i;
    fx     cosfx;
    double delta;                           /* úhel, ze kterého se funkce počítá */
    double value;                           /* vypočtené hodnoty */
    double abs_err;                         /* absolutní chyby */
    double rel_err;                         /* relativní chyby */
    char  *zvyr1, *zvyr2;                   /* ukazatele na konstantní řetězce pro */
                                            /* generování HTML */

    fx_create_tables();

    puts("\n<h2>Výpočet funkce cos() optimalizovanou metodou CORDIC</h2>\n");
    puts("<table>");
    for (i=0; i<=90; i++) {                 /* výpočetní smyčka */
        delta=deg2rad(i);                   /* převod úhlu na radiány */
        cosfx=fx_cos_cordic_optim(fp2fx(delta));  /* aplikace algoritmu CORDIC */
        value=fx2fp(cosfx);                 /* výpočet funkce cos */
        abs_err=fabs(value-cos(delta));     /* výpočet absolutních chyb */
        rel_err=cos(delta)<=1e-10 ? 0:100.0*abs_err/cos(delta);
        if (rel_err<=1.0) {
            zvyr1="<strong>";
            zvyr2="</strong>";
        }
        else {
            zvyr1="";
            zvyr2="";
        }
        printf("<tr><td>%02d</td><td>%5.3f</td><td>%5.3f%</td><td>%5.3f</td><td>%s%5.3f%%%s</td></tr>\n",
           i, value, cos(delta), abs_err, zvyr1, rel_err, zvyr2);
    }
    puts("</table>");
    return 0;
} 

Výsledky běhu testovacího příkladu odpovídají hodnotám zjištěným u funkce sinus:

Počet iterací: Součet absolutních chyb: Součet relativních chyb: Průměrná absolutní chyba: Průměrná relativní chyba:
1 25.036 12524.416% 0.275 137.631%
2 12.128 5725.907% 0.133 62.922%
3 6.439 2063.404% 0.071 22.675%
4 3.579 1878.925% 0.039 20.648%
5 1.748 674.885% 0.019 7.416%
6 0.942 462.012% 0.010 5.077%
7 0.540 230.214% 0.006 2.530%
8 0.355 112.530% 0.004 1.237%
9 0.289 68.081% 0.003 0.748%
10 0.270 60.319% 0.003 0.663%
11 0.265 58.767% 0.003 0.646%
12 0.265 57.142% 0.003 0.628%
13 0.275 63.638% 0.003 0.699%
14 0.268 57.773% 0.003 0.635%
15 0.272 59.119% 0.003 0.650%
16 0.272 59.119% 0.003 0.650%
17 0.272 59.119% 0.003 0.650%
18 0.272 59.119% 0.003 0.650%
19 0.272 59.119% 0.003 0.650%
20 0.272 59.119% 0.003 0.650%
21 0.272 59.119% 0.003 0.650%
22 0.272 59.119% 0.003 0.650%
23 0.272 59.119% 0.003 0.650%
24 0.272 59.119% 0.003 0.650%
25 0.272 59.119% 0.003 0.650%
26 0.272 59.119% 0.003 0.650%
27 0.272 59.119% 0.003 0.650%
28 0.272 59.119% 0.003 0.650%
29 0.272 59.119% 0.003 0.650%
30 0.272 59.119% 0.003 0.650%
31 0.272 59.119% 0.003 0.650%
32 0.272 59.119% 0.003 0.650%

6. Literatura

  1. Yates Randy: Fixed-Point Arithmetic: An Introduction,
    Digital Sound Labs, March 3, 2001
  2. Hook Brian: An Introduction to Fixed Point Math,
    Game Design and Review, 2003
  3. Andraka, Ray: „A survey of CORDIC algorithms for FPGA based computers“,
    ACM, 1998
  4. Despain, A.M.:„Fourier Transform Computations Using CORDIC Iterations“,
    IEEE Transactions on Computers, Volume 23, strany 993–1001, 1974
  5. Mazenc C., Merrheim, X., Muller, J.M.: „Computing Functions Arccos and Arcsin Using CORDIC“,
    IEEE Transactions on Computers, Volume 42, strany 118–122, 1993
  6. Volder, Jack: „Binary computation algorithms for coordinate rotation and function generation“,
    Convair Report IAR-1, 1956
  7. Volder, Jack: „The CORDIC Trigonometric Computing Technique“,
    IRE Transactions on Electronic Computing, Vol EC-8, strany 330–334, 1959
  8. NVIDIA Corporation: „Floating-Point Specials on the GPU“,
    2005

7. Odkazy na Internetu

  1. P. Mikulec, M. Vojtíšek: Procesor IBM RS 6000,
    http://petam.chy­trak.cz/skola/RS6000
  2. Wikipedia: Fixed-point arithmetic,
    http://en.wiki­pedia.org/wiki/Fi­xed-point_arithmetic
  3. Wikipedia: Floating point,
    http://en.wiki­pedia.org/wiki/Flo­ating_point
  4. Wikipedia: IEEE floating-point standard,
    http://en.wiki­pedia.org/wiki/I­EEE_Floating_Po­int_Standard
  5. Grant R. Griffin: CORDIC FAQ,
    http://www.dspgu­ru.com/info/faq­s/cordic.htm
  6. Andraka Consulting Group, Inc.: What is all this CORDIC stuff anyhow?,
    http://www.an­draka.com/cor­dic.htm
  7. Cyliax Ingo: CORDIC (COordinate Rotation DIgital Computer), the swiss army knife for computing math functions…
    http://www.ee­.ualberta.ca/cou­rses/ee401/mi­croboard/cordic_CCin­k.html

8. Slovo závěrem

V tomto desetidílném seriálu jsme si přiblížili způsob použití dvou základních formátů podmnožiny racionálních čísel v operační paměti počítače. Jednalo se o široce používaný a podporovaný formát pohyblivé řádové binární čárky a již méně známý, ale stále užitečný a nenahraditelný formát pevné řádové binární čárky. Popsali jsme si vlastnosti obou formátů, včetně předností a záporů při jejich použití v různých typech úloh, jakými jsou počty s měnou, zpracování signálů, výpočty goniometrických funkcí atd. Také jsme si ukázali, jakým způsobem jsou v obou zmiňovaných formátech implementovány základní aritmetické operace (součet, rozdíl, součin, podíl), ale i operace složitější – výpočet druhé odmocniny, vyčíslení goniometrických funkcí, výpočet délky vektoru atd. V neposlední řadě byl v několika demonstračních příkladech prakticky ukázán algoritmus CORDIC, který má v mnoha systémech i výpočetně náročných aplikacích svoji nezastupitelnou­ úlohu.

Našli jste v článku chybu?

4. 8. 2006 15:03

Dobrý den,

především díky za pochvalu. Já to beru tak, že jedním článkem se člověk už z principu nemůže zavděčit všem. Buď to bude moc odborné nebo naopak příliš "laické" a vždycky se najde někdo z druhé strany spektra, komu se to nebude líbit - s tím se však nedá celkem nic dělat, i když některé hlášky v diskusích člověka zamrzí.

3. 8. 2006 16:35

Vit Hadacek (neregistrovaný)
nechci vypadat, jako ze pochlebuji, ale pridam se taky. Pan Tisnovsky produkuje clanky, ktere stoji za to precist. Ma je perfektne a systematicky pripravene, az se divim, kde na to bere cas. Tak tez pridavam pochvalu, aby se tim vykompenzovaly prispevky k predchozim clankum typu "Je tohle server o Open Source nebo vo matice"? :-)

Mozna byste mel, pane Tisnovsky, publikovat tez nekde jinde (abyste nebyl OT) a zkusit se povenovat vyuziti treba fraktalove matematiky v jinych oborech, nez…

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

DigiZone.cz: Sat novinky: Fransat UHD Demo

Sat novinky: Fransat UHD Demo

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Měšec.cz: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru