Document fait avec Nvu Document made with Nvu




Trigonométrie en nombres entiers

Instructions
Utilisation
Exemple

Principe

Les fonctions trigonométriques sont indispensables pour la réalisation des tracés géométriques sur écran ou imprimante ou autre traitement numérique. Pour optimiser les temps de calcul, rien de tel que de travailler avec des nombres entiers plutôt que des nombres flottants surtout lorsque l'on veut utiliser un processeur au prix raisonnable.

Une solution est d'utiliser la notation BAM pour Binary Angular Measure (Mesure Angulaire Binaire). On choisit alors de réduire la représentation d'un angle sur un entier signé de 16 bits en considérant:

  • 0 pour l'angle nul,
  • +/-16384 pour +/-PI/2,
  • +/-32768 pour +/-PI.

De la même façon, on peut prendre par convention de représenter les valeurs +/-1 par +/-32768 afin d'avoir la meilleure précision possible en calcul en nombres entiers.

Maintenant que l'on a défini les règles des paramètres entrant et sortant des fonctions trigonométriques en nombres entiers, il faut encore déterminer un algorithme le plus performant possible.J'ai choisi le principe de l'approximation par segments de droite.

La fonction sinus, par exemple, peu être approchée à 3e-5 avec 128 segments sur un quart de période (0 à PI/2) à comparer à 1/32768=3e-5 pour la représentation de la valeur 1 dans notre cas. Pour les valeurs différentes du quart de période précédent, il suffit d'appliquer les formules suivantes et ainsi à s'y ramener:

  • sin(-x) = -sin(x),
  • si x>(PI/2) alors sin(x) = sin((PI/2)-x).

Le modulo +/-PI est automatique sachant que le calcul est réalisé sur 16 bits signés (poids faibles pour un nombre de 32 bits). La table permet de calculer la valeur avec seulement une multiplication et une division pour donner la valeur approchée dans un segment de droite entre 2 angles.

La fonction cosinus se déduit de la fonction sinus en appliquant la formule:

  • cos(x) = sin(x+(PI/2)),

ce qui correspond à la séquence FORTH suivante:

16384 + SIN

La fonction arc-sinus pourrait être construite sur le même principe que la fonction sinus mais avec l'inconvénient d'une divergence importante vers la valeur 1 sachant que la pente de la droite approchée tend vers l'infini.

Je propose une solution qui permet de récupérer la table de la fonction sinus en y accédant par son contenu. Il suffit alors de déterminer le segment de droite entre 2 angles à partir de la table des sinus et des poids forts de l'angle d'entrée (algorithme à approximation successive). Il n'y a plus qu'à calculer la valeur approchée avec une multiplication et une division.

La fonction arc-cosinus se déduit de la fonction arc-sinus en appliquant la formule:

  • acos(x) = (PI/2)-asin(x),

ce qui correspond à la séquence FORTH suivante:

ASIN NEGATE 16384 +

Pour l'arc-tangente, le problème est de calculer cette valeur sur des valeurs quelconques prises dans l'ensemble des nombres réels. La solution adoptée ici est de transmettre cette valeur par 2 nombres entiers (n et m) correspondant à une fraction et de calculer ainsi l'arc-tangente de n/m. Il faut aussi réduire le calcul au valeurs comprises entre 0 et PI/2 en utilisant les formules suivantes:

  • atan(-x) = -atan(x),
  • atan(x)+atan(1/x) = (PI/2).

La deuxième formule est particulièremen intéressante car elle va permettre de définir une table limitée aux des valeurs comprises entre 0 et 1 (0 e 32768 ici). Il suffira alors de déterminer la plus grande valeur absolue entre n et m pour se ramener au calcul de l'arc-tangente d'un nombre positif inférieur ou égal à 1.

Ces quelques principes me permettent d'obtenir des résultats plus que suffisants pour la plupart des applications graphiques.


Instructions

bam représente un angle codé en mesure angulaire binaire

- TABLE_SIN adr

Adresse de la table des sinus.
128 mots de 16 bits donnent le sinus entier multiplié par 32768 de 0 à PI/2 (0 à 16384 en bam)

- TABLE_ATAN adr

Adresse de la table des arc-tangentes.
128 mots de 16 bits donnent l'arc-tangente en nombre entier multipliée par 32768 de 0 à PI/4 (0 à 8192 en bam)

bam SIN n*32768

Sinus

bam COS n*32768

Cosinus

n*32768 ASIN bam

Arc-sinus

n*32768 ACOS bam

Arc-cosinus

n,m ATAN bam

Arc-tangente de n divisé par m


Utilisation

Pour utiliser au mieux ces fonctions, il faut bien toujours penser à réduire son domaine de travail aux nombres entiers et donc, dans le même esprit, essayer d'optimiser au minimum le nombre d'opérations. Si par exemple, on désire faire un calcul de projection de coordonnées en 3 dimensions vers 2 dimensions, on aura tout intérêt à commencer par calculer les fonctions trigonométriques et stocker leur valeur sous forme de variable avant d'appliquer leur résultat sur chaque point.

Si le calcul de la tangente d'un angle est indispensable, il vaut mieux conserver le principe adopté pour l'arc-tangente afin de garder le maximum de précision. Le résultat devra donc être conservé dans 2 valeurs qui sont le sinus et le cosinus. Voici par exemple ce que serait l'instruction FORTH qui la calculerait:

: TAN ( bam --> n,m : n est le sinus et m le cosinus)
 DUP >R SIN R> COS
;

N'oubliez pas vos formules de trigonométrie pour calculer de manière plus efficace comme par exemple déterminer la somme de 2 tangentes ( tan(a)+tan(b) ). Si vous faites ceci à partir de la fonction précédente, vous devrez faire 2 calculs de tangente ( résultats intermédiaires na,ma et nb,mb) puis une addition de 2 fractions ( résultat final (na*mb)+(nb*ma),ma*mb ) ce qui conduit à un total de 4 calculs de sinus ( pour les 2 tangentes ) et 3 multiplications supplémentaires pour le résultat final (chaque multiplication est suivie d'une division par 32768 pour respecter la normalisation bam). Alors que, la formule suivante peut être appliquée:

tan(a)+tan(b) = sin(a+b)/(cos(a)*cos(b))

Ceci peut se faire avec la séquence FORTH suivante:

OVER OVER + SIN ( sin(a+b) ou n ) ROT COS ROT COS 32768 */ ( cos(a)*cos(b) ou m )

Cette fois, il n'y a plus que 3 calculs de sinus et 1 multiplication.

Dans le cas d'un noyau FORTH avec données de 16 bits, 32768 = -32768. Il faut donc inverser le signe avec l'instruction "NEGATE" mais si le résultat est -32768, le signe ne change pas. Il faut aussi détecter ce cas et alors soustraire 1 au nombre pour obtenir 32767. Il faut donc ajouter "NEGATE DUP 0< +".


Exemple

Voici par exemple ce que l'on peut obtenir dans le cas d'une démonstration graphique avec projection 3D vers 2D: