/***************************************************************************
				  RACINE CARREE


	Les fonctions de ce fichier calculent des racines carr‚es entiŠre
	suivant diff‚rentes m‚thodes.

	Dans l'ensemble, elle ne sont donn‚es que comme support pour une
	programmation optimis‚e en assembleur.

	Pour ‚viter les warnings du compilateur et mˆme si les op‚rations
	fonctionnent correctement, j'ai cast‚ syst‚matiquement les variables.
	Malheureusement, cela rend la lecture du programme un peu plus
	difficile.

****************************************************************************

Auteur          : Pierre Larbier
D‚velopp‚ le    : 8.12.1993
DerniŠre MAJ    : 14.10.1994

Toutes les routines de ce fichier sont librement utilisables (si vous les
employez dans un programme commercial, envoyez-moi un petit mot ... ‡a fait
plaisir). Elles ont ‚t‚ test‚es mais c'est sans aucune garantie ...

***************************************************************************/
#include <stdio.h>
#include <stdlib.h>

/* La librairie math‚matique flottante du C n'est utilis‚e QUE pour constituer
   les tables et effectuer les v‚rifications des diff‚rentes routines. */
#include <math.h>
#include <time.h>


typedef unsigned int ushort;
typedef unsigned char uchar;
typedef unsigned long ulong;

/* Tables utilis‚es par sqrt_tabulee() et sqrt_newton() */
uchar trac16[256];
ushort tcar[256];

/* Prototype des fonctions de ce fichier */
/*****************************************/
/* Pr‚calcul des tables */
void sqrt_calc_tables(void);

/* Racine par la m‚thode de Nicomaque */
uchar sqrt_impair(ushort nbre);

/* Racine bit par bit */
ushort sqrt_bit_par_bit(ulong nbre);

/* Racine entiŠrement tabul‚e */
uchar sqrt_tabulee(ushort nbre);

/* Racine par l'algorithme de H‚ron */
ushort sqrt_newton(ulong nbre);

/* Calcule une distance par CORDIC */
ushort dist(short x, short y);

/*************************************************************************

  Proc‚dure : sqrt_calc_tables

  Auteur / Date : Pierre Larbier 8/12/1993

  Fonction : Cette fonction calcule les tables n‚cessaires … certaines rtns
	      de ce fichier.

	      Les tables sont en variable globale du fichier.


  Entr‚e : aucune

  Sortie : aucune

*************************************************************************/
void sqrt_calc_tables(void)
{
ushort i;

	/* Table pour sqrt_tabulee() et sqrt_newton() */
	/**********************************************/
	for (i=0 ; i < 256 ; i++)
		trac16[i] = (uchar)sqrt((double)i*256.);

	/* Table pour sqrt_tabulee() */
	/*****************************/
	for (i=0 ; i < 256 ; i++)
		tcar[i] = (i+1)*(i+1);
	tcar[255] = 65535U;

	return;
}



/*************************************************************************

  Proc‚dure : sqrt_impair

  Auteur / Date : Pierre Larbier 8/12/1993

  Fonction : Calcule la racine carr‚e d'un ushort en utilisant la somme des
	      nombres impairs.
	     Cette routine n'utilise ni table, ni multiplication ni division,
	     mais est en g‚n‚ral d'une lenteur … faire pleurer.

	     Enfin, elle est jolie et est employ‚e parfois dans les calculettes
	     bas-de-gamme.


  Entr‚es : nbre : nombre de d‚part dont on cherche la racine carr‚e.
	     C'est un nombre non sign‚ sur 16 bits

  Sortie  : r‚sultat renvoy‚ dans un char non sign‚ de 8 bits.

*************************************************************************/
uchar sqrt_impair(ushort nbre)
{
ulong somme , i , x , max;

	/* On fait les calculs sur des long pour ‚viter les problŠmes de
	   d‚bordement lorsque nbre est sup‚rieur … 65025 */
	somme = 0;
	i = 1;
	x = 0;
	max = (ulong)nbre;

	while (somme <= max) {
		somme += i;
		i += 2;
		x++;
	}
	return (uchar)(x-1);
}

/*************************************************************************

  Proc‚dure : sqrt_bit_par_bit

  Auteur / Date : Pierre Larbier 8/12/1993

  Fonction : Calcule la racine carr‚e d'un long en g‚n‚rant le r‚sultat
	     bit par bit.
	     Cette routine n'utilise ni table, ni multiplication ni division.

	     Dans le cas où la division est une op‚ration qui prend beaucoup
	     de temps, cette m‚thode peut ˆtre plus efficace que l'algorithme
	     de H‚ron.

  Entr‚es : nbre : nombre de d‚part dont on cherche la racine carr‚e.
	     C'est un nombre non sign‚ sur 32 bits

  Sortie  : r‚sultat renvoy‚ dans un entier non sign‚ de 16 bits.

*************************************************************************/
ushort sqrt_bit_par_bit(ulong nbre)
{
ulong x2 , dech , interm;
ushort i , x , decl;

	x = 0;
	x2 = 0L;
	decl = 0x8000;
	dech = 0x4000000L;

	for (i=16 ; i>0 ; i--) {
		interm = x2 + ((ulong)x << i) + dech;
		if (interm <= nbre) {
			x2 = interm;
			x = x | decl;
		}
		dech = dech >> 2;
		decl = decl >> 1;
	}
	return x;
}

/*************************************************************************

  Proc‚dure : sqrt_tabulee

  Auteur / Date : Pierre Larbier 8/12/1993

  Fonction : Calcule la racine carr‚e d'un ushort en utilisant 2 petites tables.

	     Cette routine est extrˆmement rapide mais au prix de 768 octets
	     de tables (256 seulement si on peut tol‚rer une erreur de 1 par
	     d‚faut).

	     Attention : cette rtn ne fonctionne que dans la gamme [0,65534].
			 elle renvoie 0 pour 65535.

  Entr‚es : nbre : nombre de d‚part dont on cherche la racine carr‚e.
	     C'est un nombre non sign‚ sur 16 bits

  Sortie  : r‚sultat renvoy‚ dans un char non sign‚ de 8 bits.

*************************************************************************/
uchar sqrt_tabulee(ushort nbre)
{
uchar estime;

	if (nbre > 4095) {
		if (nbre > 16383)
			estime = trac16[nbre >> 8];
		else
			estime = trac16[nbre >> 6] >> 1;
	}
	else {
		if (nbre > 255)
			estime = trac16[nbre >> 4] >> 2;
		else
			estime = trac16[nbre] >> 4;
	}

	/* AprŠs ces 2 tests, l'erreur est au plus ‚gale … 1 par d‚faut,
	   on la corrige. C'est … cause de cette correction que la fonction
	   renvoie 0 pour nbre = 65535. */
	if (tcar[estime] <= nbre)
		estime++;

	return estime;
}

/*************************************************************************

  Proc‚dure : sqrt_newton

  Auteur / Date : Pierre Larbier 8/12/1993

  Fonction : Calcule la racine carr‚e d'un long en utilisant la m‚thode de
	     Newton … l'ordre 1.

	     Cette routine utilise une table de 256 octets pour fixer le point
	     de d‚part des 2 it‚rations de Newton n‚cessaires. Le choix de la
	     taille de la table (ou de l'algorithme d‚terminant la graine) est
	     une affaire de compromis rapidit‚-taille des donn‚es; j'ai fait
	     celui de prendre une petite table.

	     Je n'ai pas r‚ussi … ‚tablir de preuve constructive que seules
	     2 it‚rations ‚taient n‚cessaires, donc j'ai fait un test
	     syst‚matique sur tous les nbres de 32 bits.

  Entr‚es : nbre : nombre de d‚part dont on cherche la racine carr‚e.
	     C'est un nombre non sign‚ sur 32 bits

  Sortie  : r‚sultat renvoy‚ dans un entier non sign‚ de 16 bits.

*************************************************************************/
ushort sqrt_newton(ulong nbre)
{
ushort x;

	/* Recherche la graine dans la table */
	if (nbre > 65535L) {
		if (nbre > 16777215L) {
			if (nbre > 268435455L)
				x = (ushort)(trac16[(uchar)(nbre >> 24)])<<8;
			else
				x = (ushort)(trac16[(uchar)(nbre >> 20)])<<6;
		}
		else
			x = (ushort)(trac16[(uchar)(nbre >> 16)])<<4;
	}
	else {
		if (nbre > 255)
			x = (ushort)(trac16[(uchar)(nbre >> 8)]);
		else {
			x = (ushort)(trac16[(uchar)nbre])>>4;
			if (x == 0)
				return 0;
		}
	}

	/* Les 2 it‚rations */
	x = (ushort)((x + nbre/x) >> 1);
	/* Ce test 'rageant' permet d'‚viter une division par 0 lorsque
	   nbre >= 2^32 - 2^16. On doit rajouter ce test pour 1/65536 des
	   nbres possibles .... je suis vert */
	if (x == 0)
		return 65535U;
	x = (ushort)((x + nbre/x) >> 1);

	/* Et la correction finale pour les cas malheureux où on a une erreur
	   de 1 par exc‚s.
	   Le cast en ulong de x pour l'‚lever au carr‚ est juste l… pour
	   forcer le compilateur … obtenir le carr‚ sur 32 bits. En r‚alit‚
	   on effectue une op‚ration : 16bits x 16 bits -> r‚sultat 32 bits */
	if (((ulong)x*(ulong)x) > nbre)
		x--;

	return x;
}

/*************************************************************************

  Proc‚dure : dist

  Auteur / Date : Pierre Larbier 14/10/1994

  Fonction : Calcule la distance euclidienne sqrt(x*x+y*y) par l'algorithme
	     CORDIC.

	     Le plus grand nombre produit est : 46338 (pour x=y=32767) et il
	     ne peut pas y avoir d'overflow.
	     L'erreur est de ñ 30 pour 6 it‚rations
		   ñ 9  pour 7 it‚rations
		   ñ 3  pour 8 it‚rations
		   ñ 2  pour 9 it‚rations et au del….
	     J'ai regard‚ l'erreur sur 1 millions de vecteurs pris au hasard …
	     chaque fois et sans retoucher le terme multiplicatif final en
	     fonction du nombre d'it‚ration (ce qui aurait peut-ˆtre m‚rit‚
	     d'ˆtre fait).


  Entr‚es : x et y, deux entiers sign‚s sur 16 bits

  Sortie  : r‚sultat renvoy‚ dans un entier non sign‚ de 16 bits.

*************************************************************************/
ushort dist(short x, short y)
{
long a,b,i,t;
	/* Les variables a,b,t tiennent dans 21 bits */

	/* On se d‚brouille pour forcer a = max(abs(x),abs(y)) et
	   b = min(abs(x),abs(y)). On multiplie tout par 16 pour limiter
	   les erreurs de troncature */
	a = (long)abs(x) << 4 ;
	b = (long)abs(y) << 4;
	if (b >= a) {
		t = a;
		a = b;
		b = t;
	}
	/* Les 9 it‚rations de CORDIC */
	for (i=0 ; i<9 ; i++) {
		t = a >> i;
		if (b >= 0) {
			a = a + (b>>i); /* d‚calage arithm‚tique */
			b = b - t;
		}
		else {
			a = a - (b>>i); /* d‚calage arithm‚tique */
			b = b + t;
		}
	}
	a >>= 5;
	/* Multiplication de 2 nombres de 16 bits non sign‚s, r‚sultat sur
	   32 bits, le r‚sultat aprŠs d‚calage tient sur 16 bits non
	   sign‚s */
	return (ushort)((unsigned long)((ushort)a*39797L)>>15);
}


int main(void)
{
ulong i;
clock_t debut,fin;

	/* O— on ‚crit la petite pr‚sentation */
	printf("\n\n");
	printf("Test des algorithmes de calcul de racines carr‚es\n");
	printf("*************************************************\n\n");

	/* Calcul des tables */
	sqrt_calc_tables();

	/* Mesure de la vitesse de sqrt */
	debut = clock();
	for (i = 0; i < 8*65536L  ; i++)
		sqrt((double)i);
	fin = clock();
	printf("Dur‚e du sqrt du coprocesseur: %.3f æs\n",
		(float)(fin - debut) / CLOCKS_PER_SEC/(float)i*1000000L);

	/* Mesure de la vitesse de sqrt_newton */
	debut = clock();
	for (i = 0; i < 8*65536L  ; i++)
		sqrt_newton(i);
	fin = clock();
	printf("Dur‚e du sqrt_newton: %.3f æs\n",
		(float)(fin - debut) / CLOCKS_PER_SEC/(float)i*1000000L);

	/* Mesure de la vitesse de sqrt_bit_par_bit */
	debut = clock();
	for (i = 0; i < 8*65536L  ; i++)
		sqrt_bit_par_bit(i);
	fin = clock();
	printf("Dur‚e du sqrt_bit_par_bit: %.3f æs\n",
		(float)(fin - debut) / CLOCKS_PER_SEC/(float)i*1000000L);

	/* Mesure de la vitesse de sqrt_tabulee */
	debut = clock();
	for (i = 0; i < 8*65536L  ; i++)
		sqrt_tabulee((ushort)(i & 0xffff));
	fin = clock();
	printf("Dur‚e du sqrt_tabulee: %.3f æs\n",
		(float)(fin - debut) / CLOCKS_PER_SEC/(float)i*1000000L);

	/* Mesure de la vitesse de sqrt_impair */
	debut = clock();
	for (i = 0; i < 8*65536L  ; i++)
		sqrt_impair((ushort)(i & 0xffff));
	fin = clock();
	printf("Dur‚e du sqrt_impair: %.3f æs\n",
		(float)(fin - debut) / CLOCKS_PER_SEC/(float)i*1000000L);

	puts("\n et c'est fini");

	return 0;
}

