473,320 Members | 1,979 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Cordic

Hi,

I'm working on an implementation of the CORDIC
algorithm for a library of functions.

One of the benefits of the CORDIC algorithm is that you
can implement it with simple additions of numbers and
division of (doubles) by powers of two. However, there
doesn't seem to be any mechanism in the C/C++ language
to direct the compiler to do this efficient form of division,
any ideas, experiences out there please?

dave
Feb 25 '06 #1
11 4792
Dave Townsend wrote:
I'm working on an implementation of the CORDIC
algorithm for a library of functions.

One of the benefits of the CORDIC algorithm is that you
can implement it with simple additions of numbers and
division of (doubles) by powers of two. However, there
doesn't seem to be any mechanism in the C/C++ language
to direct the compiler to do this efficient form of division,
any ideas, experiences out there please?


I am curious about how you've arrived to the [apparent] conclusion
that whatever the compiler does (without your direction) is somehow
inefficient.

V
--
Please remove capital As from my address when replying by mail
Feb 25 '06 #2

"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:Xs******************************@comcast.com. ..
Dave Townsend wrote:
I'm working on an implementation of the CORDIC
algorithm for a library of functions.

One of the benefits of the CORDIC algorithm is that you
can implement it with simple additions of numbers and
division of (doubles) by powers of two. However, there
doesn't seem to be any mechanism in the C/C++ language
to direct the compiler to do this efficient form of division,
any ideas, experiences out there please?


I am curious about how you've arrived to the [apparent] conclusion
that whatever the compiler does (without your direction) is somehow
inefficient.

V
--
Please remove capital As from my address when replying by mail

I happend to have looked at the assembly code generated - albeit in Debug
mode on VC6.

9: double d = 100.00;
00401028 mov dword ptr [ebp-8],0
0040102F mov dword ptr [ebp-4],40590000h
10: double e = d / 2 ;
00401036 fld qword ptr [ebp-8]
00401039 fdiv qword ptr [__real@8@40008000000000000000 (00423ff0)]
0040103F fstp qword ptr [ebp-10h]
11: double f = d / 2.5;
00401042 fld qword ptr [ebp-8]
00401045 fdiv qword ptr [__real@8@40008000000000000000 (00423030)]
0040104B fstp qword ptr [ebp-18h]
Feb 25 '06 #3
TB
Dave Townsend skrev:
"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:Xs******************************@comcast.com. ..
Dave Townsend wrote:
I'm working on an implementation of the CORDIC
algorithm for a library of functions.

One of the benefits of the CORDIC algorithm is that you
can implement it with simple additions of numbers and
division of (doubles) by powers of two. However, there
doesn't seem to be any mechanism in the C/C++ language
to direct the compiler to do this efficient form of division,
any ideas, experiences out there please? I am curious about how you've arrived to the [apparent] conclusion
that whatever the compiler does (without your direction) is somehow
inefficient.

V
--
Please remove capital As from my address when replying by mail

I happend to have looked at the assembly code generated - albeit in Debug
mode on VC6.


Are you trashing a compiler as inefficient based on the debug code?

9: double d = 100.00;
00401028 mov dword ptr [ebp-8],0
0040102F mov dword ptr [ebp-4],40590000h
10: double e = d / 2 ;
00401036 fld qword ptr [ebp-8]
00401039 fdiv qword ptr [__real@8@40008000000000000000 (00423ff0)]
0040103F fstp qword ptr [ebp-10h]
11: double f = d / 2.5;
00401042 fld qword ptr [ebp-8]
00401045 fdiv qword ptr [__real@8@40008000000000000000 (00423030)]
0040104B fstp qword ptr [ebp-18h]


And what do you deem as a more efficient substitute?

--
TB @ SWEDEN
Feb 25 '06 #4

"TB" <TB@SWEDEN> wrote in message
news:44**********************@taz.nntpserver.com.. .
Dave Townsend skrev:
"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:Xs******************************@comcast.com. ..
Dave Townsend wrote:
I'm working on an implementation of the CORDIC
algorithm for a library of functions.

One of the benefits of the CORDIC algorithm is that you
can implement it with simple additions of numbers and
division of (doubles) by powers of two. However, there
doesn't seem to be any mechanism in the C/C++ language
to direct the compiler to do this efficient form of division,
any ideas, experiences out there please?
I am curious about how you've arrived to the [apparent] conclusion
that whatever the compiler does (without your direction) is somehow
inefficient.

V
--
Please remove capital As from my address when replying by mail

I happend to have looked at the assembly code generated - albeit in Debug mode on VC6.


Are you trashing a compiler as inefficient based on the debug code?

9: double d = 100.00;
00401028 mov dword ptr [ebp-8],0
0040102F mov dword ptr [ebp-4],40590000h
10: double e = d / 2 ;
00401036 fld qword ptr [ebp-8]
00401039 fdiv qword ptr [__real@8@40008000000000000000 (00423ff0)] 0040103F fstp qword ptr [ebp-10h]
11: double f = d / 2.5;
00401042 fld qword ptr [ebp-8]
00401045 fdiv qword ptr [__real@8@40008000000000000000 (00423030)] 0040104B fstp qword ptr [ebp-18h]


And what do you deem as a more efficient substitute?

--
TB @ SWEDEN


Did everybody get out of bed on the wrong side this morning?
I'm not trashing anybody or any compiler, I'm just trying to investigate the
benefits of using a CORDIC algorithm. I was looking for a "shift" type
operation which would divide a double by a power of two which presumably
would be more efficient than a general purpose division algorithm. If people
have some useful comments, please post.


Feb 25 '06 #5
Dave Townsend wrote:
[..]
Did everybody get out of bed on the wrong side this morning?
Not me. You sound like that, however. I was just asking where you
get your information about the alleged inefficiency.
I'm not trashing anybody or any compiler, I'm just trying to
investigate the benefits of using a CORDIC algorithm.
I have no idea what that is. C++ Standard doesn't define one, so
you might actually mention some source of information (besides the
obvious Google) about your subject.
I was looking
for a "shift" type operation which would divide a double by a power
of two which presumably would be more efficient than a general
purpose division algorithm. If people have some useful comments,
please post.


Dividing by a power of two the most efficiently would be subtracting
from the exponent stored in some bits of the FP number. Is that what
you're trying to do? Essentially you need to extract the exponent
(see 'frexp' function), subtract and then recombine the new exponent
with the mantissa (see 'ldexp' function).

V
--
Please remove capital As from my address when replying by mail
Feb 25 '06 #6
Did everybody get out of bed on the wrong side this morning?
I'm not trashing anybody or any compiler, I'm just trying to investigate
the
benefits of using a CORDIC algorithm. I was looking for a "shift" type
operation which would divide a double by a power of two which presumably
would be more efficient than a general purpose division algorithm. If
people
have some useful comments, please post.


Assuming that floating point values are stored in a certain format (ie. IEEE
floats) you can implement your own shift operations that would modify the
mantisa fields of the binary representations directly. This would obviously
be non-portable and certainly not guaranteed to be faster than the
corresponding multiplications/division performed on the FPU.

-- Marek


Feb 25 '06 #7
Dave Townsend wrote:
[snipped] Did everybody get out of bed on the wrong side this morning?
I'm not trashing anybody or any compiler, I'm just trying to investigate
the benefits of using a CORDIC algorithm. I was looking for a "shift" type
operation which would divide a double by a power of two which presumably
would be more efficient than a general purpose division algorithm. If
people have some useful comments, please post.


Dave,

For start of the discourse, why in the Earth you think it is possible to do
'efficient' division with floats using shifts?

--
Cesar Rabak
GNU/Linux User 52247.
Get counted: http://counter.li.org/

Feb 26 '06 #8

"Cesar Rabak" <cs*****@hotmail.com> wrote in message
news:dt**********@emma.aioe.org...
Dave Townsend wrote:
[snipped]
Did everybody get out of bed on the wrong side this morning?
I'm not trashing anybody or any compiler, I'm just trying to investigate
the benefits of using a CORDIC algorithm. I was looking for a "shift" type operation which would divide a double by a power of two which presumably
would be more efficient than a general purpose division algorithm. If
people have some useful comments, please post.


Dave,

For start of the discourse, why in the Earth you think it is possible to

do 'efficient' division with floats using shifts?

--
Cesar Rabak
GNU/Linux User 52247.
Get counted: http://counter.li.org/

Why not? I never did computer science at school, so I only have a limited
knowledge of how floating point numbers are manipulated in the hardware.
From what I do know, it doesn't seem a stretch to shift the mantissa part of
the number by 2 and then deal with the possible change in mantissa? That
would appear to be less effort than a general double precision divide. What
am I missing here?

I thought there might be a special instruction on many CPU architectures
which could do divide by a power of two. Notice that I did put "shift" in
quotes, not to imply that it was literally possible that the operation could
be done in shifts. The idea is not so unreasonable, the CORDIC algorithm
is used extensively in chip design where the "divide-by-power-of-two" can
be performed by relatively simple digital logic. For that matter, I
understand that a lot of early portable calculators computed trig functions
this way.

Oh, dear, perhaps this is getting a little too far off-topic?


Feb 26 '06 #9
Dave Townsend wrote:

"Cesar Rabak" <cs*****@hotmail.com> wrote in message
news:dt**********@emma.aioe.org...
Dave Townsend wrote:
> [snipped]
> Did everybody get out of bed on the wrong side this morning?
> I'm not trashing anybody or any compiler, I'm just trying to
> investigate the benefits of using a CORDIC algorithm. I was looking for
> a "shift" type > operation which would divide a double by a power of two which
> presumably would be more efficient than a general purpose division
> algorithm. If people have some useful comments, please post.


Dave,

For start of the discourse, why in the Earth you think it is possible to

do
'efficient' division with floats using shifts?

Why not? I never did computer science at school, so I only have a limited
knowledge of how floating point numbers are manipulated in the hardware.


OK. This explains certain things.
From what I do know, it doesn't seem a stretch to shift the mantissa part
of
the number by 2 and then deal with the possible change in mantissa? That
would appear to be less effort than a general double precision divide.
What am I missing here?
The first thing I think you should consider is that in most hosted
environments the floating point operation will done in a specific silicon
real state in the machine generally called "Floating Point Processor" or
something along this name.

Caveat: YMMV if you're coding for free standing environments like SBCs or
some other exotic hardware.

Second thing is the representation of the mantissa can not be in a format
that shifting bits may be not enough to do a division by two.

Last but not the least. It remains that the platform gives you access to
manipulating the mantissa bits themselves and then (obviously that would be
not portable from this point on) a means to expose this to the compiler
you're using.

I thought there might be a special instruction on many CPU architectures
which could do divide by a power of two. Notice that I did put "shift" in
quotes, not to imply that it was literally possible that the operation
could
be done in shifts.


OK. I see you put '"shift" in quotes'. I think we can now settle this
special instruction, even if it exists for some exotic architecture, is not
part of the C++ standard.

You would need to check the targed CPU of your project and then see if it is
worhtwhile to expend time to call it via an embedded assembly instruction.
The idea is not so unreasonable, the CORDIC algorithm

is used extensively in chip design where the "divide-by-power-of-two" can
be performed by relatively simple digital logic. For that matter, I
understand that a lot of early portable calculators computed trig
functions this way.


The CORDIC algorithm and specially the trick you mention is intended for use
when all the math is done with integer arithmetic. I also was exposed to
the CORDIC routine with this information the early hand calculator used it.

HTH

--
Cesar Rabak
GNU/Linux User 52247.
Get counted: http://counter.li.org/

Feb 26 '06 #10

"Cesar Rabak" <cs*****@hotmail.com> wrote in message
news:dt**********@emma.aioe.org...
Dave Townsend wrote:

"Cesar Rabak" <cs*****@hotmail.com> wrote in message
news:dt**********@emma.aioe.org...
Dave Townsend wrote:

>
[snipped]
> Did everybody get out of bed on the wrong side this morning?
> I'm not trashing anybody or any compiler, I'm just trying to
> investigate the benefits of using a CORDIC algorithm. I was looking for > a "shift" type
> operation which would divide a double by a power of two which
> presumably would be more efficient than a general purpose division
> algorithm. If people have some useful comments, please post.

Dave,

For start of the discourse, why in the Earth you think it is possible
to
do
'efficient' division with floats using shifts?

Why not? I never did computer science at school, so I only have a limited knowledge of how floating point numbers are manipulated in the hardware.


OK. This explains certain things.
From what I do know, it doesn't seem a stretch to shift the mantissa part of
the number by 2 and then deal with the possible change in mantissa? That would appear to be less effort than a general double precision divide.
What am I missing here?


The first thing I think you should consider is that in most hosted
environments the floating point operation will done in a specific silicon
real state in the machine generally called "Floating Point Processor" or
something along this name.

Caveat: YMMV if you're coding for free standing environments like SBCs or
some other exotic hardware.

Second thing is the representation of the mantissa can not be in a format
that shifting bits may be not enough to do a division by two.

Last but not the least. It remains that the platform gives you access to
manipulating the mantissa bits themselves and then (obviously that would

be not portable from this point on) a means to expose this to the compiler
you're using.

I thought there might be a special instruction on many CPU architectures
which could do divide by a power of two. Notice that I did put "shift" in quotes, not to imply that it was literally possible that the operation
could
be done in shifts.
OK. I see you put '"shift" in quotes'. I think we can now settle this
special instruction, even if it exists for some exotic architecture, is

not part of the C++ standard.

You would need to check the targed CPU of your project and then see if it is worhtwhile to expend time to call it via an embedded assembly instruction.
The idea is not so unreasonable, the CORDIC algorithm is used extensively in chip design where the "divide-by-power-of-two" can be performed by relatively simple digital logic. For that matter, I
understand that a lot of early portable calculators computed trig
functions this way.


The CORDIC algorithm and specially the trick you mention is intended for

use when all the math is done with integer arithmetic. I also was exposed to
the CORDIC routine with this information the early hand calculator used it.
HTH

--
Cesar Rabak
GNU/Linux User 52247.
Get counted: http://counter.li.org/

Cesar,

Thanks that was useful information. I think I understand that I could apply
this CORDIC algorithm
if I can use integer arithmetic ( which is ok). In fact, the algorithm will
eventually run on a special
multiprocessor chip without OS and without a coprocessor, the investigation
was to look at a simulation
of the code written in C and running on a workstation to evaluate
performance, size, pros/cons, etc.

thanks,
dave

Feb 26 '06 #11
In article
<Dd******************************@comcast.com>,
da********@comcast.net says...

[ ... ]
Thanks that was useful information. I think I understand that I could apply
this CORDIC algorithm if I can use integer arithmetic ( which is ok).
You can apply CORDIC to floating point as well -- though
it works a bit differently.

Floating point is an integer with a scale factor --
nothing more or less than that. For fixed point, the
scale factor is...fixed. For floating point, you store
the scale factor along with the integer being scaled.

That means a few things are a bit different when you do
math on floating point numbers -- but only a few things.
You're dealing a number of the form 2^N * y. That means
to multiply, you have to add the exponents and multiply
the significands. To divide, you subtract exponents and
divide the significands. Interestingly, addition and
subtraction are almost more complex than multiplication
or division -- you have to normalize the two numbers so
they have the same exponent, and then add or subtract the
significands. (e.g. 1.2e12 + 1.1e10 => 1200e10 + 1.1e10
=> 1201.1e10)

When you're done with whichever operation above, you need
to re-normalize your results (if possible -- if it's not
possible, you'll have to decide whether to support
denormals or not).

If memory serves, CORDIC is mostly matrix multiplication,
which means lots of multiplication and addition but
little or no subtraction or division. I don't believe
that CORDIC in general reduces all multiplications to
powers of two though -- at least IIRC, you have to
restrict the angles you work with to get that.
In fact, the algorithm will eventually run on a special
multiprocessor chip without OS and without a coprocessor,
the investigation was to look at a simulation of the
code written in C and running on a workstation to evaluate
performance, size, pros/cons, etc.


The first thing to consider would be what your processor
supports natively, and what you need for your final
results. If you need a format (e.g. floating point) that
it doesn't support directly, you'll need emulate it on
your own to produce results that really mean much. Using
your compiler's native floating point will tell you
nearly nothing about what emulated floating point on your
target will be like. To emulate the floating point, you
could start with something along this line:

struct FP {
unsigned int exponent : 8;
long significand : 24;

FP(float const &initial);
FP const &operator=(FP const &c);
};

FP operator+(FP const &a, FP const &b);
FP operator-(FP const &a, FP const &b);
FP operator*(FP const &a, FP const &b);
FP operator/(FP const &a, FP const &b);
// quite a few more operators and probably functions
// to provide as well.

This particular format is a reasonable approximation of a
typical single-precision floating point type. Of course,
it'll be up to you to emulate it in a usable fashion. As
a lot of hardware manufacturers have found, doing
floating point at all is hard; doing it well is quite a
bit harder.

Of course, if you're going to do fixed point, the same
basic point applies -- meaningful results will depend
(heavily) upon closely emulating what you're going to do
on your target machine.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Feb 27 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

45
by: OcelotIguana | last post by:
Hello, Does anyone have any suggestions for where to find a good sincos routine (i.e. a routine that calculates both the sin and cos of a given argument) written in c? Thanks, ...
5
by: Davidlohr Bueso | last post by:
Hi, I've been trying to write some trigonometric functions of the math library (sin, cos, tan, etc, etc.) in C and I've learned that instead of using series, the best way to go is by using the...
9
by: Hans | last post by:
Hi All, In the stripped down code example below Visual C++ 2005 issues the following error: error LNK2019: unresolved external symbol "public: void __thiscall Addsub<24>::do_process123(void)"...
4
by: astri | last post by:
#include "Unit1.h" #include "math.h" #include "fixed_math.hpp" #include "algorithm.h" #define MBIT 0x4000 #define CBIT 16 long constbl; void __fastcall TForm1::Button1Click(TObject...
4
by: astri | last post by:
i`m doing thesis about comparing calculation of arctan by polynomial and CORDIC. I`ve read a lot of journal and books about CORDIC and this is what i understand. 1. make x and y 2. make...
12
by: astri | last post by:
i`m doing my thesis comparing CORDIC with polynomial in counting arctan with fixed point. I`m using Q15 format now. I`m using this site CORDIC arctan as a referenced when making with floating...
15
by: Roman Mashak | last post by:
Hello, I'd like to make a simple replacement of 'pow()' function for the embedded platform I'm working on. What is the better way, probably bit shifting? Thanks. Best regards, Roman Mashak.
1
by: manish2008 | last post by:
Assignment statement Background theory Consider a phasor at an angle of Ø (0 <= Ø <= 90°) with projections on the x and y axes as x0 and y0, respectively. Let it be rotated by an angle of Ø0...
2
kadghar
by: kadghar | last post by:
Hello Experts: I was wondering if anyone knows how does a computer do exponents operations (powers). I know its simple when the exponent is a positive integer. a^b can be easily done with: c...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.