NUMERICAL RECIPES

[Uno]

Right. A pointer value is created by the conversion, but there's no
pointer object. (The unqualified word "pointer" is ambiguous; I
generally try to refer to pointer types, pointer objects, and pointer
values explicitly. Likewise for arrays.)

Ok. I think that's a very useful distinction. It doesn't take much to
talk past each other with this material.

 

[Martin Brown]

So is having source lines that are so long and convoluted.

1. I find your pointer code more difficult to read than mine.

2. I find array indexing easier to read than my pointer code.

3. I can convert to pointers with little effort or difficulty and do
so only to increase speed.

Have you actually benchmarked it? Many modern optimising compilers can
now make a perfectly good compilation of the indexed version or the
pointer version and may even generate the same executable code!

If you look at the code generated for both you may well find that the C
compiler is already smart enough to make optimisations somewhat better
than you have managed in that code snippet.

The basic for loop summing

sum += px*cx
or
sum += *px++ * *cx++

The canonical form in C for that sort of loop when compiled on a half
decent CPU architecture is often something like.

cxmpx = cx-px
for (i=psfm; i; i--) { sum += *px * *(px+cxmpx) ; px++ }

NB this saves one increment instruction in the inner loop and takes
advantage of indexing by a compile time constant offset.

It is crazy writing this out longhand - the compiler knows how to do it!

Most compilers I have seen in the past few years generated this code for
both program variants and will schedule the instructions to avoid
stalling the pipelines. Your micro optimisation might even put the
optimiser off from finding the correct solution. The obfuscated coding
style will certainly make any future maintenance much more difficult.

Profile directed compilers will try even harder on real bottlenecks.

If you *really* wanted it to go faster then you should be using the
vectorised SIMD instructions instead of messing about with pointers.

4. The compiler doesn't care.

Indeed. And the compiler can generate the same binary executable from
either way of coding it. This was not the case in the dim and distant
past but modern optimising compilers are better than you seem to think.
Toy ones for PICs and some microcontrollers are still behind the times.

Don't take my word for it use the debugger to inspect the code...

No, there usually are tradeoffs between human readability, speed and
RAM usage.

Certainly there are, but you need to spend the effort on the critical
bottlenecks and not waste time micro-optimising for its own sake.

Ditto.

I think you will find you are in a minority of one here. Apart from
submissions from contestants in the obfuscated C competition I haven't
seen a more ugly line of C code in a very long time.

Regards,
Martin Brown

 

[Peter Flass]

On 1/10/2011 8:10 PM, Seebs wrote:

I don't usually say this, but I agree with the poster who suggested
trimming NGs from posts to this thread. Maybe leave comp.lang.c only?

 

[nmm1]

This is getting ridiculous, so I shall stop with this one. I do
accept that the standard is not clear on this issue, and I almost
certainly wasn't, but this matter came up explicitly during WG14
discussions on C90 (c. 1988) and WG14's position was as I said.

The UK was distinctly unhappy that it wasn't properly specified;
it was in one of our hundreds of objections.

Array types, like any types, don't really exist after compilation.
Array objects do exist at run time, and they hold array values.

Any expression of array type is *converted* to a pointer to the array's
first element. This is conceptually a run-time operation, though it's
almost certainly handled at compile time.

None of that is true, though not all of it is wholly wrong. You
probably mean translation phase 8 by "after compilation", so let's
use that.

Base types DO exist in C99 phase 8 - see 6.5 on 'effective types'.
I accept that C90 appeared to eliminate them, and 'convert' them
to alignment and datum type restrictions, but WG14's position
was that the 'effective type' rules are a clarification of what was
already implicit.

I suggest that you try and think of a construct where phase 8 has
the concept of an array value (or even an array object) - you may
find it harder than you think

And, while the conversion can often be done in phase 8 (just as
sizeof() can be), it is conceptually a phase 7 operation. You can
see that if you look at the specification of function declarations
and calls in detail, or consider code like:

double a[100], b[sizeof(a+0)];

As I explained in my other followup, there are array values (see the
standard's definition of "value" in 3.17); it's just somewhat unusual to
manipulate them as values.

But as Seebs pointed out, a struct may contain an array member, which
may be assigned as part of assigning the struct value:

That doesn't give it any independent existence or, actually, any
existence at all in phase 8! There was a LOT of discussion on
this matter on the WG14 reflector, both with C90 and C99, and the
situation is very different from what most people think it is.
I baulk at describing it here, because it's foully complicated,
even for people who know the whole standard very well.

Functions don't *become* pointers. Expressions of function type are
*converted* to pointer values.

I accept that correction; as I said, I was over-simplifying. There
are reasons that I said what I did, but they aren't worth going into.


Regards,
Nick Maclaren.

 

[Jens Thoms Toerring]

No, there usually are tradeoffs between human readability, speed and
RAM usage.

This (and the stuff before) seems to have been dealt with already
extensively by Martin Brown...

On Jan 10, 8:18 pm, (e-mail address removed) (Jens Thoms Toerring) wrote:
In C++, the construct for a pointer to a member function is such that
it is as though it were designed to be unreadable and unwritable,
e.g., matrix& (matrix::*A)(matrix&). But, there are good reasons to
use those pointers. What would you say to person on the C++ committe
responsible for that?

Well, that's a rather special kind of pointers and I guess
it won't make it into a book using C. The syntax even for
normal function pointers takes a bit of getting used to,
but again this is rather likely not something too relevant
for a book like Numerical Recipes (and then it can't be cir-
cumvented by using array notation, which is what all this
started with).

I don't understand your question. It has been decades since I wrote
in C. Refresh my memory, does C have "&" whereby the address of x
is gotten with &x? If not, how do you get the address? It is also
used for bitwise and, which, of course is a completely different
operation.

The unary '&' operator is used to determine the address of
an object in C the same way as in C++. But the last time I
looked you couldn't take the address of the return value of a
function, neither in C nor C++. You can only take the address
of an lvalue that designates an object (or of a function),
which the return value of a function isn't. And that's what
got me puzzled.

Communicating numerical algorithms to other people in C++ is typically
worse in practice.

Worse than what? Which languages are more suitable and why?
Do you feel that one can't write understandable programs in
C++? There is definitely a not too small group of people that
would claim that C++ is superior to C in that respect (not
that I would include myself into that group;-)

Regards, Jens

 

[Keith Thompson]

Since C89,
expressions of function type are converted to pointers
in function calls.

Function calls aren't a special case. Any expression of function
type is converted to a pointer *unless* it's the operand of a unary
"&" (which yields a pointer anyway) or of a "sizeof" (in which
case it's a constraint violation rather than yielding the size of
a function pointer). C99 6.3.2.1p4.

(I just noticed that that paragraph, in discussing the type of the
function expression and of the resulting pointer value, leaves out
the type(s) of any parameters, an odd oversight.)

For example, in

void func(void);
void (*funcptr)(void);
funcptr = func;

the expression ``func'' on the last line is converted to a pointer,
not because it's on the RHS of an assignment, but because it's not
the operand of "&" or "sizeof". The same conversion occurs in:

func; /* No parentheses, so not a call */

Of course the vast majority of occurrences of expressions of
function type are function names in calls, so other cases don't
come up very often.

 

[Keith Thompson]

...once you put them [NR codes] in a shared library, it
becomes a useful prototyping tool and doesn't contaminate your code with
copylefts and suchlike.

Have you read the license conditions on the NR code? Regardless of what
one might think about copylefts, the copyright on the NR code is more
restrictive than any copyleft. Copylefts place conditions on
redistributing the code or programs built from it. The NR copyright
places an even stronger condition - namely that you cannot do it at all.

Quoting exactly from my copy of NR in Fortran 90

"Immediate License....You are not allowed to transfer or distribute
machine-readable copies to any other person, or to use the routines
on more than one machine, or to distribute executable programs
containing our routines. This is the only free license."

As the last sentence quoted above implies, there are other license
options, but you have to pay for all of them (paying for the book
doesn't count).

Sure, but I can use them for prototyping with no issues. Strictly
speaking, just linking a GPL routine into a program makes the whole
program GPL, whether I show it to anyone else or not.

If you don't show it to anyone else, why does it matter that it's
covered by the GPL? The GPL doesn't require distribution, it just
places conditions when you do distribute. (Disclaimer: IANAL.)

 

[aruzinsky]

So is having source lines that are so long and convoluted.







Have you actually benchmarked it? Many modern optimising compilers can
now make a perfectly good compilation of the indexed version or the
pointer version and may even generate the same executable code!

Amazingly, you don't see that this is a point on my side of the
argument in which I contended that such pointer use should not appear
in Numerical Recipes. In other words, you are more than agreeing with
me while falsely pretending to argue with me.

If you look at the code generated for both you may well find that the C
compiler is already smart enough to make optimisations somewhat better
than you have managed in that code snippet.

The basic for loop summing

  sum += px*cx
or
  sum += *px++ * *cx++

The canonical form in C for that sort of loop when compiled on a half
decent CPU architecture is often something like.

cxmpx = cx-px
for (i=psfm; i; i--) { sum += *px * *(px+cxmpx) ; px++ }

NB this saves one increment instruction in the inner loop and takes
advantage of indexing by a compile time constant offset.

Good point.

It is crazy writing this out longhand - the compiler knows how to do it!

Most compilers I have seen in the past few years generated this code for
both program variants and will schedule the instructions to avoid
stalling the pipelines.

My compiler is about 8 years old. I am more interested in upgrading
to 64 bit instructions.

Your micro optimisation might even put the
optimiser off from finding the correct solution. The obfuscated coding
style will certainly make any future maintenance much more difficult.

Not if I put the entire indexed version into a comment field.

Profile directed compilers will try even harder on real bottlenecks.

If you *really* wanted it to go faster then you should be using the
vectorised SIMD instructions instead of messing about with pointers.

Who said I don't in some cases? Again, you falsely pretend to argue
with me.

Indeed. And the compiler can generate the same binary executable from
either way of coding it. This was not the case in the dim and distant
past but modern optimising compilers are better than you seem to think.
Toy ones for PICs and some microcontrollers are still behind the times.

Don't take my word for it use the debugger to inspect the code...

Again, you are falsely pretending to argue with me.

Certainly there are, but you need to spend the effort on the critical
bottlenecks and not waste time micro-optimising for its own sake.

Again, you are falsely pretending to argue with me.

I think you will find you are in a minority of one here. Apart from
submissions from contestants in the obfuscated C competition I haven't
seen a more ugly line of C code in a very long time.

Being a minority of one is a good thing because I am apparently in the
bad company of schizophrenics who don't even know when they are
agreeing with me.

 

[Keith Thompson]

This is getting ridiculous, so I shall stop with this one. I do
accept that the standard is not clear on this issue, and I almost
certainly wasn't, but this matter came up explicitly during WG14
discussions on C90 (c. 1988) and WG14's position was as I said.

I don't have access to those discussions; all I can go by is what's
in the standard itself.

The UK was distinctly unhappy that it wasn't properly specified;
it was in one of our hundreds of objections.


None of that is true, though not all of it is wholly wrong. You
probably mean translation phase 8 by "after compilation", so let's
use that.

Let's not. By "after compilation" I meant "at run time". (I could
have been clearer; I wasn't even thinking about phase 8, i.e.,
linking.)

What I meant is that types are used by the compiler to resolve
the meanings of various program constructs and to constrain what's
valid and what isn't. They don't really exist in a running program.
By the time you have an executable, the type information, which is
internal to the compiler and/or linker, no longer really exists;
the same executable could have been generated from source in a
different language with a radically different type system.

I don't think the standard says this explicitly, but I think it's
a reasonable way of looking at it. I suppose it might also be
reasonable to think of types as existing in some abstract sense in
a running program. But I don't think that's entirely relevant to the
point I was making.

[snip stuff about phase 8]

And, while the conversion can often be done in phase 8 (just as
sizeof() can be), it is conceptually a phase 7 operation. You can
see that if you look at the specification of function declarations
and calls in detail, or consider code like:

double a[100], b[sizeof(a+0)];

When I wrote that the conversion "is conceptually a run-time
operation", I was being sloppy, and probably wrong. Most conversions
(such as casts) *are* run-time operations, though like any
other operation they can sometimes be resolved at compile time.
The standard uses the word "converted" to refer to what happens to
an array expression; I inferred from that that it's conceptually a
run-time operation. On further thought, I was likely wrong on this
point (which I consider to be a minor one); the array-to-pointer
conversion described in C99 6.3.2.1p3, and the function-to-pointer
conversion in p4, can only occur at compile time. (Which makes me
wonder if "converted" was the best word to use to describe it.)

It's not unusual; after phase 7, it's impossible. And, no, <string.h>
is NOT a counter-example.

I didn't say <string.h> is a counter-example.

An array value is the value of an array object. The definition of
"value" in C99 3.17:

precise meaning of the contents of an object when interpreted as
having a specific type

does not exclude array objects. Assignment of a struct containing an
array is a (rare) example of an array value being manipulated *at run
time* directly as a value, rather than indirectly via a pointer.

That doesn't give it any independent existence or, actually, any
existence at all in phase 8! There was a LOT of discussion on
this matter on the WG14 reflector, both with C90 and C99, and the
situation is very different from what most people think it is.
I baulk at describing it here, because it's foully complicated,
even for people who know the whole standard very well.

Again, I wasn't referring to phase 8. I'm saying that array values
exist *at run time*. Do you disagree?

I accept that correction; as I said, I was over-simplifying. There
are reasons that I said what I did, but they aren't worth going into.

I definitely think the are worth going into, and I urge you to do so.

Upthread you wrote:

In C, that is true. All of strings, arrays and (when used as
objects) functions are actually pointers, and it is important to
know and use that when passing them as function arguments.

There is a very common misconception that C arrays are really
pointers (see, for example, question 6.3 of the comp.lang.c
FAQ, <http://www.c-faq.com/>). I took your statement to be a
confirmation of that misconception. I don't believe you actually
have that particular misunderstanding, but if you'll re-read what
you wrote, I think you might find that your statement might tend
to reinforce the false idea that C arrays are really pointers.
Probably I misunderstood what you meant.

 

[Seebs]

On 1/10/2011 8:10 PM, Seebs wrote:

I don't usually say this, but I agree with the poster who suggested
trimming NGs from posts to this thread. Maybe leave comp.lang.c only?

Whoops, right you are, sorry. Followups set, and I'll try to just trim
when posting for anything else in this thread.

-s

 

[Seebs]

Sure, but I can use them for prototyping with no issues. Strictly
speaking, just linking a GPL routine into a program makes the whole
program GPL, whether I show it to anyone else or not.

This is both an oversimplification and simply untrue.

Read the license more carefully.

-s

 

[nmm1]

Your posting has raised a lot of new points, but I really AM going
to stop, because I have little interest in C debates as such. I may
use the language, but have given up on hoping for improvement. My
Email address is real.

I don't have access to those discussions; all I can go by is what's
in the standard itself.

Some of them are online, but most of the C90 ones aren't. I threw out
my stack of paper a long time back. Unfortunately, the C standard is so
ambiguous and inconsistent that it isn't possible to decode what its
intent is from only the standard itself.

Let's not. By "after compilation" I meant "at run time". (I could
have been clearer; I wasn't even thinking about phase 8, i.e.,
linking.)

My error! Sorry. I am involved in too many standards, and had got
confused - I misremembered that phase 8 included execution, but it
doesn't. So, in my response, I meant "after compilation" by phase 8.

What I meant is that types are used by the compiler to resolve
the meanings of various program constructs and to constrain what's
valid and what isn't. They don't really exist in a running program.
By the time you have an executable, the type information, which is
internal to the compiler and/or linker, no longer really exists;
the same executable could have been generated from source in a
different language with a radically different type system.

I don't think the standard says this explicitly, but I think it's
a reasonable way of looking at it. I suppose it might also be
reasonable to think of types as existing in some abstract sense in
a running program. But I don't think that's entirely relevant to the
point I was making.

Yes, all of that's correct, except that they exist in more than an
abstract sense, via alignment and data validity. For example, whether a
malloced area includes a double or not is both dynamic and semantically
significant. As I said, C99 includes that explicitly (and differently)
via effective types.

When I wrote that the conversion "is conceptually a run-time
operation", I was being sloppy, and probably wrong. Most conversions
(such as casts) *are* run-time operations, though like any
other operation they can sometimes be resolved at compile time.

Regrettably, that is NOT true. Some are; some aren't; and some can
be either. That is not made clear in either 6.6 Constant expressions
or 6.5.4 Cast operators, but is implied by the need for consistency
with other parts of the standard.

The worst mess in this area is array adjustment, where the standard
doesn't specify WHERE in translation phase 7 it must occur, and where at
least one C90 compiler did it after type equivalencing and sizeof
evaluation etc. Despite WG14's view and the current consensus, that IS
a conforming implementation. I tried to get this fixed in both C90 and
C99, and failed dismally both times :-(

The standard uses the word "converted" to refer to what happens to
an array expression; I inferred from that that it's conceptually a
run-time operation. On further thought, I was likely wrong on this
point (which I consider to be a minor one); the array-to-pointer
conversion described in C99 6.3.2.1p3, and the function-to-pointer
conversion in p4, can only occur at compile time. (Which makes me
wonder if "converted" was the best word to use to describe it.)
Precisely.


I didn't say <string.h> is a counter-example.
Sorry.

An array value is the value of an array object. The definition of
"value" in C99 3.17:

precise meaning of the contents of an object when interpreted as
having a specific type

does not exclude array objects. Assignment of a struct containing an
array is a (rare) example of an array value being manipulated *at run
time* directly as a value, rather than indirectly via a pointer.

My point is that there IS no case where an array can be manipulated as
an object - and, no, that is not a counter-example. Regrettably, the
reasons why it isn't are very complicated, but are necessary to avoid
undefined behaviour when copying unions and in some other cases. You
can see some of them in 6.2.6.1 Representations of types, which states
(unclearly) that structure assignment is a 'byte copy' of some number
of bits and does NOT break down into an elementwise copy, though it
may be implemented like that (but need not be).

Again, I wasn't referring to phase 8. I'm saying that array values
exist *at run time*. Do you disagree?

Yes. They don't. Sorry. There is a strong sense in which C arrays
have a Pascal-like syntax and BCPL-like semantics. At run-time,
arrays ARE pointers, and strings ARE arrays. Well, I say that,
but the standard doesn't make it clear - however, as with array
adjustment, it is WG14's view and the consensus interpretation.

It becomes important to do with the interpretation of pointer
arithmetic, object access and restrict, in the presence of type
conversion of all sorts. I have a document that describes the problem,
which I have tried to get fixed many times, but with no success. If it
is NOT true, assigning to two different elements of the same array
object with no intervening sequence point becomes undefined behaviour.
And other problems.

I definitely think the are worth going into, and I urge you to do so.

The function reasons really aren't. They are ridiculously arcane,
and don't affect any current C programs, though they DO affect what
classes of extensions to the standard are possible.

Upthread you wrote:

In C, that is true. All of strings, arrays and (when used as
objects) functions are actually pointers, and it is important to
know and use that when passing them as function arguments.

There is a very common misconception that C arrays are really
pointers (see, for example, question 6.3 of the comp.lang.c
FAQ, <http://www.c-faq.com/>). I took your statement to be a
confirmation of that misconception. I don't believe you actually
have that particular misunderstanding, but if you'll re-read what
you wrote, I think you might find that your statement might tend
to reinforce the false idea that C arrays are really pointers.
Probably I misunderstood what you meant.

I am afraid not. That isn't a misconception - it is one of the numerous
errors in the C FAQ. I haven't looked at it in over a decade but, when
I did, over half of then entries I looked at were seriously misleading
or erroneous.

You might also like to look at C1X (n1339 6.5.1.1 Generic selection)
and consider the consequences of that not being so

I accept that it is also misleading to state that C arrays are simply
pointers, because they are NOT pointers as far as most declarators and
type management go. But there it ends - semantically, they are just
pointers.


Regards,
Nick Maclaren.

 

[Richard Maine]

Keith Thompson wrote:
Because according to the license, unless I'm very wrong, linking one GPL
routine with my code, just once, makes the whole code base GPL
forever--even if I rip out the original GPL code before shipping it or
even showing it to anyone.

I'm not saying anyone would know, just that the exposure is a lot worse
than with Numerical Recipes!

I'm certainly not going to get into an extended argument about legal
points (even if I were a lawyer), so this will be my last post on the
subject, but it looks to me like you are "very wrong." It frankly sounds
to me like just FUD. I see no justification for that in the GPL. To the
contrary, I see what looks to me like a direct and explicit denial of
that position in the GPL FAQ. Lifting directly from that FAQ

"If a program combines public-domain code with GPL-covered code, can
I take the public-domain part and use it as public domain code?

You can do that, if you can figure out which part is the public
domain part and separate it from the rest. If code was put in the public
domain by its developer, it is in the public domain no matter where it
has been."

 

[gmail-unlp]

On Jan 11, 3:20 pm, Phil Hobbs

[snip a lot]

Because according to the license, unless I'm very wrong, linking one GPL
routine with my code, just once, makes the whole code base GPL
forever--even if I rip out the original GPL code before shipping it or
even showing it to anyone.

Hmmmm... I'm not and I don't want to be a lawyer, but from my last
(not very deep) read of GPL I can't figure out how this could be
understood, would you, please, explain? I know it's not about Fortran,
but I think it's very interesting, anyway (at least to me, of course).

Thanks in advance,

Fernando

 

[Seebs]

Because according to the license, unless I'm very wrong, linking one GPL
routine with my code, just once, makes the whole code base GPL
forever--even if I rip out the original GPL code before shipping it or
even showing it to anyone.

You are very, very, wrong.

IANAL, but so far as I can tell, the GPL never provides any such rules
unless you *distribute* something which incorporates such code. Furthermore,
it doesn't "make the whole code base GPL". All it can do is require you
to release the code base under terms compatible with the GPL... *in order
to be licensed to use the GPL code*.

You are always welcome to not be licensed to use the GPL code, and refrain
from copying it or otherwise relying on a license to it. Some people have,
in fact, done this rather than open code bases that were inadvertantly linked
with GPLd code, and so far as I know, that's one of the allowed responses.

-s

 

[nmm1]

Well sometimes not "real" mathematical greatness is necessary. Some
luck may be sufficient
Fantastic maybe is too much. It might be if also returned a pair of
nontrivial factors ;-))

You clearly don't know how much effort has been put into the problem
by first-class mathematicians.


Regards,
Nick Maclaren.

 

[pamela fluente]

You clearly don't know how much effort has been put into the problem
by first-class mathematicians.

I can imagine. But that was true even before AKS. It's not with a
negative
attitude that we can make progress.
An idea "out of the box" needs not to come from pure mathematicians.
It's even
more likely, i'd say, that won't come from them ;-))

Pam

 

[mecej4]

I can imagine. But that was true even before AKS. It's not with a
negative
attitude that we can make progress.
An idea "out of the box" needs not to come from pure mathematicians.
It's even
more likely, i'd say, that won't come from them ;-))

Pam

Well, we'll concede that it is not necessary to be a mathematician to
reach the stated goals. On the other hand, it is not sufficient to be a
non-mathematician.

-- mecej4

 

[pamela fluente]

Well, we'll concede that it is not necessary to be a mathematician to
reach the stated goals. On the other hand, it is not sufficient to be a
non-mathematician.

-- mecej4

;-)))

Apart mathematicians, everybody can be not only a "non-mathematician"
by
intersecting another condition ;-))

 

[John Bode]

The practice of initializing and
incrementing pointers separately from loop counters is moronic.  They
should both be put in the for statement because loop counters and
pointers are more the same than not.  If fact, a pointer can be used
as a loop counter.  So, then where do you put the pointer
initialization and increment?  Thusly, most people who have not
previously been brainwashed into accepting the absurdities of
programmer cultural would find my version more readable.

Then again, there is a school of thought that the only things that
should appear in the loop control expression are things that *actually
control the loop*; IOW, just because you *can* initialize other
variables in the loop control expression doesn't mean you *should*. I
prefer to keep my loop control expressions as clean as possible.

2. "Is 'c' some convoluted macro?" - No.  Since I told you that my
code was C++, you should have guessed that c is instantiation of a
class for allocating floating point arrays on the heap and c(int) and
c(int,int) are inline member functions for accessing an element of an
array by indices.  BTW, I don't want to see classes in Numerical
Recipes either.

Given that I'm reading this in comp.lang.c, and since a lot of us in
c.l.c. aren't also C++ experts, it's a little much to expect us to
immediately understand something that specific to C++.

To Others:

Everyone who wants to see or not see Jens Thoms Toerring's version of
pointer use in Numerical Recipes, please, vote.

Yo. His version was clearer for me to read at a glance than yours.