Cordic

[Dave Townsend]

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

[Victor Bazarov]

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

[Dave Townsend]

"Victor Bazarov" <v.********@com Acast.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@400080 00000000000000 (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@400080 00000000000000 (00423030)]
0040104B fstp qword ptr [ebp-18h]

[TB]

Dave Townsend skrev:

"Victor Bazarov" <v.********@com Acast.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@400080 00000000000000 (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@400080 00000000000000 (00423030)]
0040104B fstp qword ptr [ebp-18h]

And what do you deem as a more efficient substitute?

--
TB @ SWEDEN

[Dave Townsend]

"TB" <TB@SWEDEN> wrote in message
news:44******** **************@ taz.nntpserver. com...

Dave Townsend skrev:

"Victor Bazarov" <v.********@com Acast.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@400080 00000000000000 (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@400080 00000000000000 (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.

[Victor Bazarov]

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

[Marek Vondrak]

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

[Cesar Rabak]

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/

[Dave Townsend]

"Cesar Rabak" <cs*****@hotmai l.com> wrote in message
news:dt******** **@emma.aioe.or g...

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?

[Cesar Rabak]

Dave Townsend wrote:

"Cesar Rabak" <cs*****@hotmai l.com> wrote in message
news:dt******** **@emma.aioe.or g...

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/