binary_search_VS_division.c

/*
Testing Binary tree searches against straight floating point multiplication
specifically for the purpose of placing coordinates into 'zones' (grid cells)
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <stdint.h>

typedef struct vec2d_struct{
    double x, y;
} vec2d;

#define ZEL 2048//zone edge length
#define ooZEL 0.00048828125
#define pitch 8

int zoner_bts16( double v ){
	if( v < 0 ){
		if( v < -4*ZEL ){
			if( v < -6*ZEL ){
				if( v < -7*ZEL ) return 0;//-8;
				else             return 1;//-7;
			}
			else{
				if( v < -5*ZEL ) return 2;//-6;
				else             return 3;//-5;
			}
		}
		else{
			if( v < -2*ZEL ){
				if( v < -3*ZEL ) return 4;//-4;
				else             return 5;//-3;
			}
			else{
				if( v < -1*ZEL ) return 6;//-2;
				else             return 7;//-1;
			}
		}
	}
	else{
		if( v < 4*ZEL ){
			if( v < 2*ZEL ){
				if( v < 1*ZEL ) return 8;//0;
				else            return 9;//1;
			}
			else{
				if( v < 3*ZEL ) return 10;//2;
				else            return 11;//3;
			}
		}
		else{
			if( v < 6*ZEL ){
				if( v < 5*ZEL ) return 12;//4;
				else            return 13;//5;
			}
			else{
				if( v < 7*ZEL ) return 14;//6;
				else            return 15;//7;
			}
		}
	}
	return -1;
}

void printnc( int n, char c ){
	for (int i = 0; i < n; ++i ){
		putchar( c );
	}
}


void write_case( int Q, int level, int top ){

	printnc( level*4, ' ' );
	printf( "if(v < %d*ZEL)", Q );
	if( level == top ){
		int ht = lrint(pow(2, top-1));
		printf(" return %d;//%d\n", Q-1 + ht, Q-1 );
		printnc( level*4, ' ' );
		printf("else           return %d;//%d\n", Q + ht, Q );
	}
	else{
		printf("{\n");
		int qd = lrint(pow(2, (top-level)-1));
		write_case( Q-qd, level+1, top );
		printnc( level*4, ' ' );printf("}\n");
		printnc( level*4, ' ' );
		printf("else{\n");
		write_case( Q+qd, level+1, top );
		printnc( level*4, ' ' ); printf("}\n");
	}
}

void write_BTS_zoners( int levels ){
	printf( "int zoner_%d( double v ){\n", lrint(pow(2,levels)) );
	write_case( 0, 1, levels );
	printf("    return -1;\n}");
}

int zoner_DIV( double v ){
	return floor( v * ooZEL ) + pitch;
}

int random( int min, int max ){
	//printf("%.16lf", 1/(double)RAND_MAX);
    return floor(rand() * 0.0000305185094760 * (double)(max-min)) + min;
}


#define N 100000

void test_zoners(){
	
	vec2d pts [N];
	for (int i = 0; i < N; ++i ){
		pts[i] = (vec2d){ random(-pitch*ZEL, pitch*ZEL -1), random(-pitch*ZEL, pitch*ZEL -1) };
	}
	int zone [N];

	clock_t T = clock();
	for (int i = 0; i < N; ++i ){
		zone[i] = 2*pitch * zoner_bts16( pts[i].y ) + zoner_bts16( pts[i].x );
	}
	printf("BTS: %d\n", clock()-T );
	long int res = 0;
	for (int i = 0; i < N; ++i ){
		res += zone[i];
	}
	printf("result: %ld\n", res );


	T = clock();
	for (int i = 0; i < N; ++i ){
		zone[i] = 2*pitch * zoner_DIV( pts[i].y ) + zoner_DIV( pts[i].x );
	}
	printf("DIV: %d\n", clock()-T );
	res = 0;
	for (int i = 0; i < N; ++i ){
		res += zone[i];
	}
	printf("result: %ld\n", res );
}



int main(int argc, char const *argv[]){

	srand (time(NULL));

	//write_zoners( 6 );
	test_zoners();

	return 0;
}