Efficiency of math.h

[Richard Heathfield]

I think the point of Christian's posting was that
he would like more information from the [Dave Rudolf]
[about] why the acos() function was called so often.
If it is something that requires high precision
and MUST be called often
(as in a signal processing application),
then it is one thing.

If it does not require high precision
or [high precision] is used gratuitously,
there might be better ways to accomplish the same thing.
As one poster pointed out, a rough [interpolation]
between values in a static array may satisfy the requirement.
Without knowing the degree of precision needed,
we just don't know.

[You misunderstood at least one part in your paraphrase
of my post. In the second paragraph I meant ...
"If it does not require high precision or *acos()* is
used gratuitiouly, ..." not, as you have interpreted it.
But, re-reading it, I can see how the sentence
could be so interpreted. I also did not put []'s
around the word "interpolation."]

The [] thing is fairly standard notation for "editorial modification made
here".

In fact, I rattled off an article suggesting Mr Tisdale (if he insists on
editing people's stuff) should start to use such notation, before noticing
(by reading your article) that he has in fact done so.

What he is doing may be stupid, but it's not actually misleading, provided
he marks it appropriately (as he appears to be doing). The point of marking
his editorialisations is that those who distrust them can go back and check
what the original actually said. Unmarked editorialisations are more
insidious. Basically, if you trust a poster not to make unmarked
editorialisations, then okay, you trust them. If you don't, then the
editorial markers probably don't do much for you anyway. But reputable
editors will use them when it is appropriate.

 

[Dik T. Winter]

> Dik T. Winter wrote:
>

> > OK, the Tschebyshev approximation in the above case:
> > double dc[] = {-0.16666666666666662966,
> > 0.00833333333333094971,
> > -0.00019841269836759707,
> > 0.00000275573161030613,
> > -0.00000002505113193827,
> > 0.00000000015918135277};
> > The algorithm reads (y = x*x):
> > sin = ((((((dc[5] * y + dc[4]) * y + dc[3]) * y + dc[2]) * y + dc[1]) * y
> > + dc[0]) * y + 1.0) * x;
> > (Actually this is for x in [-pi/2, pi/2] with a relative precision of about
> > 1 ULP, or, in tangible terms, the relative error is bounded by about 2e-16.)

>
> That's only about 4 or 5 decimal digits. You will probably find that
> your algorithm would benefit from a "range reduction".

Since when is 2e-16 relative error only about 4 or 5 decimal digits? I
would have thought 15+ *decimal* digits... Or do you noe know what
2e-16 means? And in what way do you suggest to do the range reduction?

> Anyway, Have you tried to "benchmark" your implementation
> against the sin(x) function in your standard C library.

What do you think? Not with regards to time, but with regards to
precision.

> If so, please report your results
> including the architecture and operating system
> where you ran the benchmarks.

Sun Solaris, relative error bounded by about 2e-16.

 

[Guillaume]

Since when is 2e-16 relative error only about 4 or 5 decimal digits? I

would have thought 15+ *decimal* digits... Or do you noe know what
2e-16 means? And in what way do you suggest to do the range reduction?

He might have confused 2e-16 with 2^(-16) ?

 

[Dave Rudolf]

I think the point of Christian's posting was that
he would like more information from the [Dave Rudolf]
[about] why the acos() function was called so often.
If it is something that requires high precision
and MUST be called often
(as in a signal processing application),
then it is one thing.

If it does not require high precision
or [high precision] is used gratuitously,
there might be better ways to accomplish the same thing.
As one poster pointed out, a rough [interpolation]
between values in a static array may satisfy the requirement.
Without knowing the degree of precision needed,
we just don't know.

Unfortunately,
I don't know what degree of precision is required either.
We can only hope that Dave Rudolf is still following this thread
and will reply with the answer.

Ya, I'm back. The signal-to-noise ratio in this thread is getting pretty
small . In short, I don't know the exact accuracy that will be needed. I
am using the acos function do determine the angle between vectors, in order
to simulate angular spring torque in a numeric sumulation of elastic
surfaces. It's for non-scientific graphical simulation, and we do not have a
theoretically rigid physical model, so we can probably get away with some
approximation.

At any rate, I now have a number of avenues to explore. Thank you all for
your ideas.

Dave

 

[Thomas Matthews]

Yes. At 20 years, he is just getting started.



Get a life Mike. And a sense of humor to make it bearable

Mr. E. Tisdale,

I have over 20 years experience with the C language and have
purposely avoided the math library. Most of the embedded systems
I worked would die (come to a hault) or worse if the math
library was included. But, from reading your past posts,
you either claim that embedded systems don't exist or
insuate that only desktop and the like exist.

In smaller embbeded applications, either a lookup table
is used (due to size and speed) or the numerical base
is changed so floating point is not required. Many
times, the accuracy is not required to move a solenoid.

I have learned calculus and numerical analysis. Just
because I don't use all the features of the language
doesn't make me a newbie.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Dan Pop]

This depends completely on the C compiler used and is not standardised.

It is entirely a library issue and need not depend at all on the C
compiler being used. I have seen assembly-only implementations of
<math.h>.

Dan

 

[Mike Wahler]

Yes. At 20 years, he is just getting started.


Get a life Mike.

I'm quite happy with my life, but thanks for your concern.

And a sense of humor to make it bearable

I'm also quite satisfied with my sense of humor (some
folks often ask me to 'tone it down'.

Ya know, I should probably just plonk you, but you're
just too darn amusing.

-Mike

 

[E. Robert Tisdale]

I have over 20 years experience with the C language
and have purposely avoided the math library.
Most of the embedded systems I worked would die (come to a hault)

You probably meant halt.

or worse if the math library was included.
Why?

But, from reading your past posts, you either claim that
embedded systems don't exist or insuate

You probably meant insinuate.

that only desktop and the like exist.

Not that I recall.
Can you quote such an instance?

In smaller embbeded

You probably meant embedded.

applications, either a lookup table is used
(due to size and speed) or the numerical base is changed
so [that] floating point is not required. Many times,
the accuracy is not required to move a solenoid.

I have learned calculus and numerical analysis.
Just because I don't use all the features of the language
doesn't make me a newbie.

No.
You're a newbie because you have only 20 years experience.

 

[E. Robert Tisdale]

E. Robert Tisdale:


I'm quite happy with my life, but thanks for your concern.



I'm also quite satisfied with my sense of humor

It's perverse.

(some folks often ask me to 'tone it down'.

Ya know, I should probably just plonk you,

Not likely. Trolls never use kill files.
Their egos won't let them. They just threaten.

but you're just too darn amusing.

Yes, everyone knows that you troll for fun.

 

[CBFalconer]

.... snip ...


I'm also quite satisfied with my sense of humor (some
folks often ask me to 'tone it down'.

Ya know, I should probably just plonk you, but you're
just too darn amusing.

You also need to watch your back with Trollsdale around. ;-[

 

[E. Robert Tisdale]

You also need to watch your back with Trollsdale around. ;-[

You need to get a job Chuck.
You spend too much time trolling in the comp.lang.c newsgroup.
If you can't get a job, retire and take up a real hobby
like fishing or card playing with the local cronies.

 

[Default User]

You spend too much time trolling in the comp.lang.c newsgroup.

As always, Trollsdale speaks from personal experience.




Brian Rodenborn

 

[Mike Wahler]

Not likely. Trolls never use kill files.
Their egos won't let them. They just threaten.


Yes, everyone knows that you troll for fun.

So now you're a mind reader... no wait....

I'll admit to everyone here that I'm ashamed that I've
allowed myself to stoop to your level. I'll stop now.

-Mike

 

[Christian Bau]

So now you're a mind reader... no wait....

I'll admit to everyone here that I'm ashamed that I've
allowed myself to stoop to your level. I'll stop now.

Mike, you couldn't reach Tisdale's level even if you tried very very
hard.

 

[Roc]

I have over 20 years experience with the C language
and have purposely avoided the math library.
Most of the embedded systems I worked would die (come to a hault)

You probably meant halt.

or worse if the math library was included.
Why?

But, from reading your past posts, you either claim that
embedded systems don't exist or insuate

You probably meant insinuate.

that only desktop and the like exist.

Not that I recall.
Can you quote such an instance?

In smaller embbeded

You probably meant embedded.

applications, either a lookup table is used
(due to size and speed) or the numerical base is changed
so [that] floating point is not required. Many times,
the accuracy is not required to move a solenoid.

I have learned calculus and numerical analysis.
Just because I don't use all the features of the language
doesn't make me a newbie.

No.
You're a newbie because you have only 20 years experience.

Why do you digress to correcting spelling, and ending commentary with
[another] insult? The ending insult negates any claim to goodwill you think
you have with the initial spelling/grammar checks. If you truly claim to be
an adult professional, surely you know the counterproductive effect you are
having by posting ridiculous, childish replies like this.

I don't read this NG as often as I would like. When I have the chance, I
read it to *learn* more. In other threads, I saw your name (and seemingly
appropriate comments) being trashed in replies. At first, I really felt
sorry for you.

In this thread, at multiple times, you demanded people post code and
algorithms (at times, bullishly). They did. Each time you were asked to do
so, you posted nothing, or posted something similar to the above.
Furthermore, I reread threads and found a trend: you post nothing
definitive to back up your "answers", and when finally called-out, it seems
your resort to belittling and name-calling or refrain from further posting
to that thread. You really think people believe you were on a panel that
reviewed the AMD K5 after you post this crap?

So I have one semi-serious question for the NG, since I no longer feel sorry
for Tisdale... The FAQ is for frequently-asked-questions: is it possible to
add something to the FAQ about certain Trolls - since his knowledge is
frequently questioned? =)

 

[Nick Landsberg]

I think the point of Christian's posting was that
he would like more information from the [Dave Rudolf]
[about] why the acos() function was called so often.
If it is something that requires high precision
and MUST be called often
(as in a signal processing application),
then it is one thing.

If it does not require high precision
or [high precision] is used gratuitously,
there might be better ways to accomplish the same thing.
As one poster pointed out, a rough [interpolation]
between values in a static array may satisfy the requirement.
Without knowing the degree of precision needed,
we just don't know.

Unfortunately,
I don't know what degree of precision is required either.
We can only hope that Dave Rudolf is still following this thread
and will reply with the answer.

But I'll tell you what you can do without knowing any more
about Dave Rudolf's precision requirements.
You can implement you proposed interpolation scheme
and benchmark it against the acos provided with your C compiler.
I predict that you will find that your interpolation scheme
is *slower* even if you need just a few decimal digits precision.
Please post your implementation so that we can repeat
your benchmark experiments ourselves.

There is a reason why math functions like acos
are included in the standard library.
There is *no* single portable implementation
that will deliver performance and accuracy everywhere.
Compiler developers hire experts to customize implementations
for each target platform and, usually, they are hard to beat.

I have been reading this NG for about a month or two, made a few
faux pas, kept my mouth shut for a while, then posted what I
thought was a reasonable question, based on previous posts
in the thread. This post prompted a post by the resident troll
that paraphrased my quote
and a challenge from the resident troll. Not only that, the
troll's post insinuated that I had made statements which
had been made by others. The challenge was rather blunt:

"I predict that you will find that your interpolation scheme
is *slower* even if you need just a few decimal digits precision.
Please post your implementation so that we can repeat
your benchmark experiments ourselves."

Note: Unedited, no []'s.

Primus, there was the observed hubris which attempted
to correct the grammar of my attributions and put the
troll's own spin on them. While my wording may not have been
precise, this recasting of my comments without confirmation
was downright rude! A simple "what did you mean by this"
before launching into a diatribe would have been sufficient
to clear up any misconceptions.

Secundus, it was not MY interpolation scheme,
(as the troll claims), though I have written more than
several interpolation schemes over the the course
of the last 29 years, but another poster's. I was just
referring to it. If the troll wants credibility, he should
be accurate in his accusations. Maybe he should have
noted that "XXX should post his interpolation scheme"
since the troll was so scrupulous about correcting my references
to "OP" to have the correct name in it.

Tertius, when I requested that the troll post HIS benchmarks,
to prove HIS point, I got no answer.

Prior to this incident, I sat back and tried to make my own judgement
as to this particular denizen. I have now made it.

Result: "Case closed, 30 days, next case!" *PLONK*

Or, as they say, "Illegitimus Non Carborundum!"

 

[Rob Thorpe]

I think the point of Christian's posting was that
he would like more information from the [Dave Rudolf]
[about] why the acos() function was called so often.
If it is something that requires high precision
and MUST be called often
(as in a signal processing application),
then it is one thing.

If it does not require high precision
or [high precision] is used gratuitously,
there might be better ways to accomplish the same thing.
As one poster pointed out, a rough [interpolation]
between values in a static array may satisfy the requirement.
Without knowing the degree of precision needed,
we just don't know.

Unfortunately,
I don't know what degree of precision is required either.
We can only hope that Dave Rudolf is still following this thread
and will reply with the answer.

Ya, I'm back. The signal-to-noise ratio in this thread is getting pretty
small . In short, I don't know the exact accuracy that will be needed. I
am using the acos function do determine the angle between vectors, in order
to simulate angular spring torque in a numeric sumulation of elastic
surfaces. It's for non-scientific graphical simulation, and we do not have a
theoretically rigid physical model, so we can probably get away with some
approximation.

At any rate, I now have a number of avenues to explore. Thank you all for
your ideas.

Dave

Another possibility is changing the internal representation of your
program from rectagular vectors to a polar form. Even using both in
different places of the program.

 

[E. Robert Tisdale]

I think the point of Christian's posting was that
he would like more information from the [Dave Rudolf]
[about] why the acos() function was called so often.
If it is something that requires high precision
and MUST be called often
(as in a signal processing application),
then it is one thing.

If it does not require high precision
or [high precision] is used gratuitously,
there might be better ways to accomplish the same thing.
As one poster pointed out, a rough [interpolation]
between values in a static array may satisfy the requirement.
Without knowing the degree of precision needed,
we just don't know.

Unfortunately,
I don't know what degree of precision is required either.
We can only hope that Dave Rudolf is still following this thread
and will reply with the answer.

But I'll tell you what you can do without knowing any more
about Dave Rudolf's precision requirements.
You can implement you proposed interpolation scheme
and benchmark it against the acos provided with your C compiler.
I predict that you will find that your interpolation scheme
is *slower* even if you need just a few decimal digits precision.
Please post your implementation so that we can repeat
your benchmark experiments ourselves.

There is a reason why math functions like acos
are included in the standard library.
There is *no* single portable implementation
that will deliver performance and accuracy everywhere.
Compiler developers hire experts to customize implementations
for each target platform and, usually, they are hard to beat.

When I requested that [E. Robert Tisdale] post HIS benchmarks,
to prove HIS point, I got no answer.

I'm not the one claiming that I can beat the acos function
that came with my compiler's implementation of the standard library.
You are claiming that you can use interpolation
to beat the built-in acos function.
The burden of proof lies with you and not me.
I challenged to to demonstrate this and you failed.

This is typical of almost all such claims about the performance
of standard library functions. They collapse immediately
when you challenge them to produce benchmark results.

Result: "Case closed, 30 days, next case!" *PLONK*

In my experience, plonkers never actual use their killfile.
Their egos won't permit them to ignore what other people say about them.
But I'm certain that all of the subscribers to the comp.lang.c newsgroup
would appreciate it very much
if you did *not* respond to *any* of my postings.
We can only hope that you will keep your promise for 30 days.

 

[E. Robert Tisdale]

Something that calls itself Mac wrote:

[snip]

Go away troll.

 

[Mac]

What's to explain?
There is no need to quote and it is discouraged.

But you quote all the time. And it is the deliberate alteration of quoted
text that we are talking about.

It is as evil as top posting.
I fix capitalization, punctuation, spelling and grammar errors
to reflect my understanding of what was said.
I am pretty sure that Nick Landsberg meant interpolation
when he said extrapolation and that he meant Dave Rudolf
when he said OP.

I also quietly fix style and programming errors in other people's code
if they aren't essential to understanding the point in question.

There is nothing wrong with correcting the posts of others provided that
it follows usenet conventions.

There is an expectation in usenet that any line which begins with a quote
indicator (e.g., the greater than sign, '>') is a verbatim quote. If you
want to correct other's posts, do it on a separate line, and do not put a
quote indicator at the beginning of that line. Judging from your posting
history, I would say that you arleady know all of this. Which means that
you must be violating community norms deliberately. I don't really
understand this.

--Mac