Efficiency of math.h

[CBFalconer]

[snip]

Unfortunately, the typical response you are going to get to that
from the trolls mentioned in the FAQ is going to be along the
lines of

"<blush> I'm Famous!!!"

I'm thinking about the infrequent & new readers of the NG. Many
of you provide valuable, informative help with kids' homework
assignments. If by reading the FAQ they can avoid misinformation
by avoiding certain Trolls, wouldn't that offset the c.l.c worry
of immortalizing said Troll(s)? Just an idea... =)

For one thing, the troll population changes much more rapidly than
the FAQ does. For another, some trolls have been known to
reform. At most the FAQ could contain generic advice about
identifying trolls and idiots, and lurking.

Fortunately most trolls are not consciously malicious.
Unfortunately we seem to have an exception to that rule.

 

[pete]

What's to explain?
There is no need to quote and it is discouraged.
It is as evil as top posting.
I fix the quotes, to reflect my understanding of what was said,
because I'm too stupid to understand the difference
between a quote and a reply.

Well, now that I've tried it, I can see the appeal.

 

[Joona I Palaste]

Well, now that I've tried it, I can see the appeal.

5 Euros says Tisdale will now insult and flame you and call you a troll
because you claimed he said something he did not say.

 

[pete]

5 Euros says Tisdale will now insult and flame you
and call you a troll
because you claimed he said something he did not say.

I quoted exactly what he meant.
When you think that somebody has made a mistake in their post:
you quote the suspect portion of the post correctly
and you address the matter in your reply, don't you ?
Doesn't everybody ?

 

[Malcolm]

Getting called a troll by Tisdale is a sign of great respect on this
newsgroup. Therefore I am still anxiously waiting the day when
Tisdale calls me a troll.

This was a perfectly good and interesting thread on how to implement or
optimise the acos() function, ruined by this sort of C content-free
bickering.

 

[Joona I Palaste]

This was a perfectly good and interesting thread on how to implement or
optimise the acos() function, ruined by this sort of C content-free
bickering.

I think Tisdale is to blame for that.

 

[Christian Bau]

This was a perfectly good and interesting thread on how to implement or
optimise the acos() function, ruined by this sort of C content-free
bickering.

If you want a very fast implementation of the acos() function with good
precision: Have a look first at the cephes implementation to get an idea
how their method works. Download

http://www.netlib.org/cephes/cmath.tgz

The acos function is together with asin in asin.c

Now do a few improvements to make it faster:

1. The cephes implementation uses an approximation by a rational
function (one polynomial divided by another polynomial). It is better to
use a single polynomial of higher degree to avoid division. Evaluating
high degree polynomials is _not_ done using the Horner scheme because
latency kills you; for example a polynomial of degree 7 might be
evaluated as

((ax+b)*x^2 + (cx+d))*x^4 + ((ex+f)*x^2 + (gx+h))

This will need some experimentation which scheme is fastest on your
processor.

2. For x > 0.5, the cephes scheme calculates 2*asin (sqrt ((1-x)/2)).
Change this as follows: If you substitute the asin formula then you will
get an odd polynomial in sqrt ((1-x)/2). That is the same as
sqrt((1-x)/2) multiplied by a polynomial in ((1-x)/2). Calculate
(1-x)/2, then calculate the square root and the polynomial in parallel
to avoid latency. The code for square root needs to be inlined; it can
be simplified because you know the range of the argument. And I hope you
know how to calculate a square root without using divisions.

3. Instead of using two different methods for x <= 0.5 and x > 0.5, use
a different point for the switch between these methods. The reason is
that the method used for large values is slower; if you restrict the
range where the slower method is used to fewer arguments then the
average runtime will be better.

 

[E. Robert Tisdale]

If you want a very fast implementation of the acos() function
with good precision, have a look first at the cephes implementation
to get an idea how their method works. Download

http://www.netlib.org/cephes/cmath.tgz

I did. I can't get it to build. Can you?

The acos function is together with asin in asin.c

Now do a few improvements to make it faster:

1. The cephes implementation uses an approximation by a rational
function (one polynomial divided by another polynomial).
It is better to use a single polynomial of higher degree
to avoid division. Evaluating high degree polynomials
is _not_ done using the Horner scheme because latency kills you;
for example, a polynomial of degree 7 might be evaluated as

((ax+b)*x^2 + (cx+d))*x^4 + ((ex+f)*x^2 + (gx+h))

This will need some experimentation
which scheme is fastest on your processor.

Don't forget to test against the built-in function.

2. For x > 0.5, the cephes scheme calculates 2*asin (sqrt ((1-x)/2)).
Change this as follows: If you substitute the asin formula
then you will get an odd polynomial in sqrt ((1-x)/2).
That is the same as sqrt((1-x)/2) multiplied by a polynomial

in ((1-x)/2). Calculate (1-x)/2, then calculate the square root
and the polynomial in parallel to avoid latency.

Exactly how does one effect this "parallel" calculation?

The code for square root needs to be inlined;
it can be simplified because you know the range of the argument.
And I hope you know how to calculate a square root
without using divisions.

Please show us how to calculate a square root without using division.

3. Instead of using two different methods for x <= 0.5 and x > 0.5,
use a different point for the switch between these methods.
The reason is that the method used for large values is slower;
if you restrict the range where the slower method is used
to fewer arguments then the average runtime will be better.

Have you ever done this before Christian?
If so, please post your code so that we can test it ourselves.

 

[Christian Bau]

I did. I can't get it to build. Can you?

Why would I try? I said "look first at the cephes implementation".
"Look". Can't you read?

Don't forget to test against the built-in function.



Exactly how does one effect this "parallel" calculation?

Inline the sqrt implementation and use a good compiler. Come on, you are
programming since 30 years. Haven't you learned anything in the last 29?

Please show us how to calculate a square root without using division.

Hint: Why do PowerPC and AMD processors have an "inverse square root
estimate"?

Have you ever done this before Christian?
If so, please post your code so that we can test it ourselves.

Troll Troll Troll Troll Troll.

My offer for a bet is still standing. ?20,000 for an acos implementation
that is faster than anything you can find.

 

[Dan Pop]

I also did not put []'s around the word "interpolation."

Actually, You originally wrote "extrapolation". It was Tisdale who
changed "extrapolation" to "interpolation" when he modified your post.

And, for once, he did the *right* thing and marked his editorial change
with the []'s.

Dan

 

[Dan Pop]

I quoted exactly what he meant.
When you think that somebody has made a mistake in their post:
you quote the suspect portion of the post correctly
and you address the matter in your reply, don't you ?
Doesn't everybody ?

It depends on the context. If the mistake is an *obvious* typo, I prefer
to silently correct it and pretend that it didn't exist in the original
message. Then spend my time addressing the *real* issue of the OP.

No one blamed me, until now, for this "unfair" quoting practice.

While other people prefer to post corrections to the typo and ignore the
real problem raised by the OP...

Dan

 

[CBFalconer]

.... snip ...

It depends on the context. If the mistake is an *obvious* typo,
I prefer to silently correct it and pretend that it didn't exist
in the original message. Then spend my time addressing the
*real* issue of the OP.

No one blamed me, until now, for this "unfair" quoting practice.

While other people prefer to post corrections to the typo and
ignore the real problem raised by the OP...

Horrors. I suspect nobody noticed it because you use discretion
and knowledge, unlike Trollsdale. Now you have given it an excuse
(albeit an invalid one).

You will now be watched by various hawks. Prepare for flames.

 

[juergen perlinger]

Joona I Palaste wrote:

I think Tisdale is to blame for that.

You can have only one prima donna in an opera. There are some around
here in this theatre, and they want to fight it out.

Ignoring someone (or at least pretending to do) is much more
discouraging than this stupid bickering. And if some people want do it,
they simply should do it by eMail: most of us around here should have
access to a computer. So to *ALL* flaming/insulting/trolling: simply
spare us from this childish stuff and fight your petty little wars
somewere else, ok?