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:
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:
