/***************** SYSTEM ************************
******** Cpu: Intel Q6600 ************************
******** O.S.: Windows 7 x64 *********************
******** Compiler: Visual Studio 2012 (C++11) ****
******** Optimizations disabled ******************
****************** OUTPUT ************************
******** Benchmark uintSqrt(): 1326 ticks ********
******** Benchmark 1.0/Q_rsqrt(): 546 ticks ******
******** Benchmark sqrt(): 640 ticks *************
******** Benchmark pow(): 1139 ticks *************
**************************************************/

#include <stdio.h>
#include <time.h>
#include <Windows.h>
#include <math.h>

typedef unsigned int uint32_t;

// Calcola la radice quadrata di un numero intero senza segno
uint32_t uintSqrt(uint32_t n)
{
    register uint32_t i;
    register uint32_t val;

    // se n vale 0 ritorna 0
    if (!n) return 0;

    // calcola il numero di bit di n
    i = 0;
    val = n;
    do
    {
        val = val >> 1;
        if (val) i++;
    } while (val);

    // assume val come 2^(i/2)
    if (!i) val=1; else val = 1 << (i>>1);

    // Calcola la radice babilonese.
    // 4 passaggi sono sufficienti
    for(i=0; i<4; i++) val = (val + n/val) >> 1;

    return val;
}

float Q_rsqrt( float number )
{
    register long i;
    register float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );
    return y;
}

int main()
{
    srand(time(0));
    auto ticks = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++) {
        register unsigned int f = uintSqrt((unsigned int)(rand()%20000));
    }
    ticks = GetTickCount() - ticks;
    printf("Benchmark uintSqrt(): %u ticks\n", ticks);

    ticks = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++) {
        register float f = 1.0f/Q_rsqrt((float)(rand()%20000));
    }
    ticks = GetTickCount() - ticks;
    printf("Benchmark 1.0/Q_rsqrt(): %u ticks\n", ticks);

    ticks = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++) {
        register float f = sqrt((float)(rand()%20000));
    }
    ticks = GetTickCount() - ticks;
    printf("Benchmark sqrt(): %u ticks\n", ticks);

    ticks = GetTickCount();
    for (unsigned int i = 0; i < 10000000; i++) {
        register float f = pow((float)(rand()%20000), 0.5f);
    }
    ticks = GetTickCount() - ticks;
    printf("Benchmark pow(): %u ticks\n", ticks);
    return 0;
}