Exploring the CORDIC algorithm with the WP34S

05312014, 07:25 PM
(This post was last modified: 06022014 06:29 PM by Thomas Klemm.)
Post: #1




Exploring the CORDIC algorithm with the WP34S
Introduction
In a recent thread somebody mentioned John Stephen Walther which lead me to his paper: A Unified Algorithm for Elementary Functions. This made me look again at the CORDIC algorithm. I like to hit a key repeatedly and look what happens: Quote: Try this during a boring lecture: Set your calculator to radians mode and then repeatedly press the cos button until you obtain the fixed point.Structure and Interpretation of Computer Programs Footnote 57 Rotation Since CORDIC is all about rotation I wanted to use complex multiplication. The WP34S provides a command that simulates this with the stack: Code: [cmplx][times] Let's assume we want to calculate arg(4, 3), that is the angle of the complex number z = 4 + 3i. How would we fill up the stack? For reasons that become apparent later I want to keep the imaginary part of z in register X. Thus X and Y are swapped and the usual rotation becomes counterclockwise. We use for instance w = 1 + 0.1i. This will rotate z by tan^{1}(0.1) = 5.7105931375°. T: 0.1 Z: 1 Y: 4 X: 3 We run ©× multiple times until the register X turns negative: \(\begin{matrix} Y: & 4 & 4.3 & 4.56 & 4.777 & 4.9484 & 5.07203 & 5.146176 & 5.1696017 \\ X: & 3 & 2.6 & 2.17 & 1.714 & 1.2363 & 0.74146 & 0.234257 & 0.2803606 \end{matrix}\) But now we've gone one step too far. Therefore let's get the last value back: Code: [cmplx]x[<>] L Thus in total we executed the rotation 6 times which is about 34.263558825°. Let's write a little program for that. We use register A as counter: Code: [cmplx][times] Now you can probably see why I wanted to keep the imaginary part of z in register X: we have to check whether it is still positive. Iteration What's the next step of the algorithm? We have to reduce the angle of rotation and use w = 1 + 0.01i instead. Thus we're going to shift the imaginary value of w one digit to the right using SDR: Code: R[^] This is the small program that we have so far: Code: 0001 [cmplx][times] Initialize the stack and registers with: A: 0 T: 1 Z: 1 Y: 4 X: 3 And then run the program multiple times to see what happens: \(\begin{matrix} & X & Y & A \\ 0: & 3.0000 & 4.0000 & 0 \\ 1: & 0.2343 & 5.1462 & 6 \\ 2: & 0.0283 & 5.1525 & 10 \\ 3: & 0.0025 & 5.1525 & 15 \\ 4: & 0.0005 & 5.1525 & 19 \end{matrix}\) From the counter A we can conclude that the total angle of rotation was: 6tan^{1}(0.1) + 4tan^{1}(0.01) + 5tan^{1}(0.001) + 4tan^{1}(0.0001) = 36.8647107295° Therefore we should probably reset the counter A to 0. But before we have to multiply it by the corresponding angle and add it to the total of angles. Initialization of Constants This little program will fill the registers with the corresponding angles: Code: 0001 # 013 Prototype Since we don't want to loose the values of the stack we have to use SSIZE8 for further calculations. Please keep in mind that now both registers A and B are part of the stack. We keep using J as the loop control variable. Code: 0001 [cmplx][times] Initialize the stack and registers with: J: 0.013 B: 0 A: 0 T: 1 Z: 1 Y: 4 X: 3 And then run the program to get: 36.8698976458 Compare this to tan^{1}(0.75). Finalisation We're not finished yet: it's a hassle that we have to initialize the stack and registers for each run. Thus let's do that beforehand. Add a nice label as well: Code: 0001 LBL'ARG' This final version of the program can be used to calculate arg(4, 3): 4 ENTER 3 XEQ'ARG' 36.8698976458 Addendum On request of Tugdual I attached a Python program with examples from the aforementioned paper. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)