01_jednoduche_algoritmy

Opakuj y = y + rad dokud nenajdeš y * y > x 

   y = y – rad

pomocí y = x / y      x je vstup; y odmocnina  
- vezmi nějakou hodnotu y a vypočti x/y. Pokud je výsledek 
dostatečně blízký y skonči 
- vezmi nový odhad hodnoty y (např. (y+x/y)/2)

Newtonova metoda 

-  iterativní metoda využívající geometrické interpretace a derivací 

݂ሺݔሻ = ݔ − ܽ = 0  Pokud rovnici vyřešíme, a se rovná odmocnině z x 
 

ݔ = ݔ − 

( ೔)

ᇲ( ೔)   

algoritmus končí pro f(x) = 0, nebo dostatečně blízko

ݔ =  ݔ − 

మ

Fast inverse square root    - výpočet 

√ 

 pomocí znalosti architektury výpočetní jednotky 

původně pro normalizaci vektorů v grafice 

vychází ze znalosti architektury a bitů v typu float 32  (pro 64 bitů 0x5fe6eb50c7b537a9) 

principem je převod na int (log2(x)) a následný výpočet na log2(

√ 

)) a převod zpět 

float Q_rsqrt( float number ) 
// zdroj wikipedia – fast inverse square root 
{ 
 

long i; 

float x2, y; 

const float threehalfs = 1.5F; 

x2 = number * 0.5F; 

y  = number; 

i  = * ( long * ) &y; // evil floating point bit level hacking 

i  = 0x5f3759df - ( i >> 1 );               // what the fxxk?  

y  = * ( float * ) &i; 

y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration 

// doladění Newtonovým algoritmem 
//  y  = y * ( threehalfs - ( x2 * y * y ) );    
// 2nd iteration, this can be removed 
 
 

return y;}

Výpočet Pi 

-  různé metody – geometrické, matematické, náhodné (statistické),