Document fait avec Nvu Document made with Nvu
acceuilnouveautesintroductioncoeurmini_systemepages_techniquesrevue_de_presselienscourriel



Technical pages
Integer trigonometric calculations

Instructions
Use
Example

Principle

Trigonometric functions are indispensable for the realization of the geometrical plans on screen or printer or other digital calculation. To optimize the calculation times, anything of such as to work with integers rather than floating numbers especially when we want to use a processor in the moderate price.

A solution is to use BAM notation ( Binary Angular Measure). We choose then to reduce the representation of an angle with a 16 bits signed integer by considering:

  • 0 zero angle,
  • +/-16384 for +/-PI/2,
  • +/-32768 for +/-PI.

In the same way, we can set by agreement to represent values +/-1 by +/-32768 to have the best possible precision in integer calculation.

Now we have defined the rules of input and output parameters in integer trigonometric functions, it is necessary to determine the most performant possible algorithm. I chose the principle of the estimate by line segments.

Sine function, for example, can be approached in 3e-5 with 128 segments on a quarter of period (0 to PI/2) to compare with 1/32768=3e-5 for the representation of the value 1 in our case. For values different from the quarter of period previous, it is enough to apply the following formulae and so to come down to it:

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

The modulo +/PI modulo is automatic knowing that calculation is realized on signed 16 bits (least significant bits for a 32 bits number). The table allows to calculate value with only a multiplication and a division to give value approached in a line segment between 2 angles.


Cosine functione deducts of the sine function by applying the formula:

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

which is corresponding to the following FORTH sequence:

16384 + SIN

Arc-sine function could be built on the same principle as the sine function but with the inconvenience of an important difference towards the knowing value 1 that the ramp of the approached line side aims towards the infinity.

I propose a solution which allows to get back the table of the sine function by reaching it by the contents. It is enough then to determine the line segment between 2 angles from the sine table and the most significant bits of the input angle (algorithm with successive estimate). There is only to calculate value approached with a multiplication and a division.

Arc-cosine functione deducts of the arc-sine function by applying the formula:

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

wich is corresponding to the following FORTH sequence:

ASIN NEGATE 16384 +

For the arc-tangent, the problem is to calculate this value on some values taken altogether real numbers. Solution adopted here is to pass on this value by 2 integers (n and m) corresponding in a fraction and to calculate so the arc-tangent of n/m. It is necessary also to reduce calculation in values included among 0 and PI/2 by using the following formulae:

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

The second formula is particularly interesting because i is going to allow to define a table limited to values included between 0 to 1 (0 to 32768 here). It will be enough then to determine the biggest absolute value enters n and m to come down to the calculation of the arc-tangent of a lower positive number or equal to 1.

These some principles allow me to obtain results more than sufficient for the most part of graphic applications.


Instructions

bam is corresponding to a binary angle measure

- TABLE_SIN adr

Sine table address.
128 words of 16 bits are giving integer sine multiplied by 32768 from 0 to PI/2 (0 to 16384 in bam)

- TABLE_ATAN adr

Arc-tangent table address.
128 words of 16 bits are giving integer arc-tangent multiplied par 32768 from 0 à PI/4 (0 à 8192 in bam)

bam SIN n*32768

Sine

bam COS n*32768

Cosine

n*32768 ASIN bam

Arc-sine

n*32768 ACOS bam

Arc-cosine

n,m ATAN bam

Arc-tangent of n divided by m


Use

To use in best these functions, it is necessary to think well always of reducing his domain of work to integers and so, in the same spirit, to try to optimize at least the number of operation. If for example, we wishe to make a projection calculation of coordinates in 3 dimensions towards 2 dimensions, we will have any interest to be begun by calculating trigonometric functions and to store their value under shape of variable before applying their result to every point.

If the calculation of the tangent of an angle is indispensable, it is better to keep principle adopted for the arc-tangent to keep the maximum of precision. Result should so be preserved in 2 values which are sine and cosine. Here is for example what would be the instruction FORTH which would calculate it:

: TAN ( bam --> n,m : n is sine and m is cosine )
 DUP >R SIN R> COS
;

Do not forget your trigonometry formulae to calculate in a more effective way as for example to determine the sum 2 tangents ( tan(a)+ tan (b) ). If you make this from the previous function, you should make 2 calculations of tangent ( intermediate results na, ma and nb, mb) then an addition of 2 fractions ( final resul (na*mb)+(nb*ma,ma*mb) what leads to a total of 4 sine calculations ( for the 2 tangents ) and 3 supplementary multiplications for final result (each multiplication is followed by a division by 32768 to respect bam normalization). While, the following formula can be applied:

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

This can make with the following FORTH sequence:

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

In this case, there are only 3 sine calculations and 1 multiplication.

In the case of a 16 bits data FORTH kernel, 32768 =- 32768. So the sign must be inversed with the instruction "NEGATE" but in the result is -32768, the sign does not change. This case must be detected and then substract 1 from the number to obyain 32767. Finally, "NEGATE DUP 0< +" must be added.


Example

Here is for example what one can obtain in the case of a graphic demonstration with projection 3D towards 2D: