Forums - Open Redstone Engineers
How to calculate the Sine ? - Printable Version

+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: ORE General (https://forum.openredstone.org/forum-39.html)
+--- Forum: Tutorials (https://forum.openredstone.org/forum-24.html)
+---- Forum: Advanced Tutorials (https://forum.openredstone.org/forum-26.html)
+----- Forum: Concepts (https://forum.openredstone.org/forum-28.html)
+----- Thread: How to calculate the Sine ? (/thread-4835.html)

How to calculate the Sine ? - GISED_Link - 10-07-2014

[Image: 586293ThundeRedResearchDepartment2.jpg]

Calculate the sine of an angle
(in combinatorial)

Hello, it's Link !

Today (or now...), I'm going to explain you how to calculate a sine. There is algorithme for this (like CORDIC), but I will show you how to do this in combinational.

Important to know :

We give a angle, and the system return a new value : The sine. But there some trouble you have to know :
  1. An angle can be given in radian or in degree,
  2. The sine is always between -1 and 1. And, the floating number are very difficult to work with.
  3. The precision of the system is very important. I'll show you my result below
Also in this condition, I will said those things for making the task easier for us :
  1. The input value is between 0 and 90 (corresponding to the value in degrees)
  2. For the sign, us an additional circuit
  3. For deleting the float problem, the sine value will be given between 0 and 255 (8 bits). You have only to divide the given sine value by 255 and then you will have the true value Smile
All right ? Then fallow me into the darkness world without any poney of :

Confused Mathematics Confused

Chapter 1 : Taylor Series Cool

for further information, look at the link.
See : Sine Series

With this series we have :
Code:
'      1     3
x - ( --- * x  )  // with x in Radian !!!!
       6
I voluntary stop at the 3rd power. Because, after, we have term in X^5 ... See what the mess it would be ^^.

Chapter 2 : Magic formula Huh

I skip the formula transformation, see official French topic for further precision

So, this is the final formula
[Image: 313317fonctionapprox2.jpg]
And what this function looks like ? Let see :
[Image: 260480Rsumdusinus.png]

What is the Floor ? Rolleyes

Floor() means that we take the integer portion of a division. Example: Floor(1,8) = 1 !

I choose C=76 (the best curve), and we have for precision something like that :
[Image: 113398Graphiquederreur.png]
The yellow curve represents the error due to the 8 bits resolution. See that Sin(87)=255... So not so good.

And Minecraft with all this S*** ?

A little example :
[Image: 44757220141001234453.png]
A quick view

[Image: 28643020141001234549.png]
down : the input (here = 32), and lamp up : the result in 8 bits (here = 134) !
(and if you do ArcSin(134 / 255) you will found : 31,7 ° ! AMAZING)

You just have to divide the given value by 255 to have the truth sinus !

RE: How to calculate the Sine ? - TSO - 10-07-2014

Lets see...
I can get the cosine quickly for you too, it's also from the Taylor/McClorin series.

Cos(0) = 1
-sin(0) = 0
-cos(0) = -1
Sin(0) = 0

Okay, the series centered at zero:

1 - (1/2) x^2 + (1/24) x^4 - (1/6!) x^6...

Good enough.

We can move the center away from zero if we want to by applying the following:

1 - 1/2 (x - c)^2 + 1/24 (x - c)^4 - 1/6! (x - c)^6

Knowing the following, we can calculate any vale of the cosine without complex tricks:

cos(-θ) = cos θ, and cos (θ+π/2) = -cos θ

I have forgotten how to calculate the maximum error, but it seems pretty easy. I think you just integrate the next term back up to the constant term... something like that.

tanθ = sinθ / cosθ (I'll find this series later, it isn't as convenient and I don't remember the derivative of tangent and secent)

RE: How to calculate the Sine ? - jxu - 10-07-2014

I'm impressed you had the time to make this
But a lookup table and an approximation algorithm is really the way to go for any "practical" use (whatever that means)

RE: How to calculate the Sine ? - TSO - 10-07-2014

If you have a lookup table:

sin(α+-β) = sin(α) cos(β) +- sin(β) cos(α)
cos(α+-β) = cos(α) cos(β) -+ sin(α) sin(β)
sin(2θ) = 2sin(θ) cos(θ)
cos(2θ) = cos^2(θ) - sin^2(θ) = 2cos^2(θ) - 1 = 1 - 2sin^2(θ)

With +- indicating the plus or minus operation and -+ indicating minus of plus. Note on cosine you subtract when adding angles and vice versa.

Now, a lookup table may not actually be faster than this because the table system has to figure out how input angle φ decomposes into α and β. This speed difference is especially true for cosθ approximations, you just square the number, shift down 1, negate, and carry a 1 in.

The maximum error for the sine function is (1/24) x^4
The maximum error for the cosine function (using 1 - 1/2 x^2) is 1/6 (x - c)^3

RE: How to calculate the Sine ? - jxu - 10-11-2014

Directing implementing trig identities is an awful idea. There are much better interpolation methods

RE: How to calculate the Sine ? - Mar_Win - 11-09-2014

I know about the CORDIC algorithm quite well I would say, but the formula u used to compute the sine seems to me slightly inefficient since you use multiplications.
I assume you solve the division with a shift, because you divide by a power of two.

But still the beginning with the Taylor Series isn't the best step in my opinion.
By using the rotation of a vector u can break down the needed arithmetic to an iterative algorithm only performing an Addition, a Subtraction and a shift getting a good approximation to actual result in only 15 iterations not only for sine, but also for cosine.

With small changes in the hardware all the elementary functions like trig(sine/cos/tan/arcsine/arccos/arctan), hyp(sinh/cosh/tanh/asinh/acosh/atanh), linear(mul/div) and other terms are possible to compute.

The algorithm was published originally by Jack E. Volder in 1959.
you can take a closer look by clicking the link below:
http://en.wikipedia.org/wiki/CORDIC

A deeper google-research will provide more.

Furthermore i recommend using radian which affords a higher precision.

You can take a trip to my plot to see a example of a implementation of the algorithm which I am currently working on with my friend.

Greetings Mar_Win.

RE: How to calculate the Sine ? - GISED_Link - 11-09-2014

Heeey ! I'm implement CORDIC right now in the server XD. The algoithm :

Code:
Cordic2(z)
Func{
  Local angle,x,y,temp,s,i
  {.7854,.46365,.24498,.12435,.06242,.03124,.01562,.00781,.00391,.00195,9.8–
ª4,4.9–ª4,2.4–ª4,1.2–ª4,6.–ª5}»angle
  0.60725»x
  0»y

  For i,0,14
    when(z=0,1,signe(z))»s
    x-s*y/2^i»temp
    y+s*x/2^i»y
    temp»x
    z-s*angle[i+1]»z
  EndFor

  Return {x,y}
EndFunc
This algo return the cos(=x) value AND the sin(=y) value ! The next algo do it, too.

And my version, to get a result between 0 and 255.
Code:
CORDIC255
1   VARIABLES
2     x EST_DU_TYPE NOMBRE
3     y EST_DU_TYPE NOMBRE
4     temp EST_DU_TYPE NOMBRE
5     s EST_DU_TYPE NOMBRE // this is the sign to change the - in +. so s = 1 or -1.
6     i EST_DU_TYPE NOMBRE
7     angle EST_DU_TYPE LISTE
8     z EST_DU_TYPE NOMBRE (z = input angle, in °)
9   DEBUT_ALGORITHME
10    LIRE z // z = angle
11    z PREND_LA_VALEUR z*2 //to increase the accuracy
12    angle[0] PREND_LA_VALEUR 90
13    angle[1] PREND_LA_VALEUR 53
14    angle[2] PREND_LA_VALEUR 28
15    angle[3] PREND_LA_VALEUR 14
16    angle[4] PREND_LA_VALEUR 7
17    angle[5] PREND_LA_VALEUR 3
18    angle[6] PREND_LA_VALEUR 2
19    angle[7] PREND_LA_VALEUR 1
20    //*end const*
21    x PREND_LA_VALEUR 155
22    y PREND_LA_VALEUR 0
23    //for
24    POUR i ALLANT_DE 0 A 7
25      DEBUT_POUR
26      SI (z==0) ALORS
27        DEBUT_SI
28        s PREND_LA_VALEUR 1
29        FIN_SI
30        SINON
31          DEBUT_SINON
32          s PREND_LA_VALEUR z/abs(z)
33          FIN_SINON
34      temp PREND_LA_VALEUR x - s*(round(y/pow(2,i)))
35      y PREND_LA_VALEUR y + s*(round(x/pow(2,i)))
36      x PREND_LA_VALEUR temp
37      z PREND_LA_VALEUR z - s*(angle[i])
38      FIN_POUR
39    AFFICHER "x cos = "
40    AFFICHER x
41    AFFICHER "y sin = "
42    AFFICHER y
43  FIN_ALGORITHME
Sorry for french XD
(si = if, alors = then, sinon = else, pour = for, prend_la_valeur = ':=' OR '=', afficher = print() ). I've made this with Algobox.

And where I am now :
[Image: 46296620141109154431.png]

[Image: 932198CORDIC255avancement.png]
And I have to make the state machine, too.

The precision (of my algo) is ± "1°" (when you take the inverse function). (for ±, do alt + 0177 ^^).

I've join CORDIC255, this is an example of the algorithm. Cordic2 is the file where I've found the first algorithm.

RE: How to calculate the Sine ? - Mar_Win - 11-10-2014

I'm pleased to see you used my advice Smile

RE: How to calculate the Sine ? - GISED_Link - 11-11-2014

heuu ... I have begun before you write your post ^^. But anyway, it will run very well !

RE: How to calculate the Sine ? - jxu - 11-13-2014

Nice job! Those french variables Tongue
There are nicer shifter designs (constant length), I suggest you look into them Smile

RE: How to calculate the Sine ? - GISED_Link - 11-13-2014

Thx. And fot the designs, have you some examples ? This one has benn made by me and is 2 ticks fast. I will certenly change the full adder, too. But now, after one week of works, corrections.... test :

[Image: 55403220141113093439.png]

[Image: 42387620141113093505.png]

[Image: 990270CORDIC255V1.png]
Compteur = counter XD

All errors are near fixed. The results are always correct with a slow clock rate. But, the huge problems with that, is that system is very slow (I think). But it is the better way to have the sin and the cos of a angle.