Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > NUMERICAL RECIPES

Reply
Thread Tools

NUMERICAL RECIPES

 
 
Uno
Guest
Posts: n/a
 
      01-11-2011
On 1/10/2011 9:45 AM, Keith Thompson wrote:

> 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.
--
Uno
 
Reply With Quote
 
 
 
 
Martin Brown
Guest
Posts: n/a
 
      01-11-2011
On 11/01/2011 04:21, aruzinsky wrote:
> On Jan 10, 8:18 pm, (E-Mail Removed) (Jens Thoms Toerring) wrote:
>> In comp.lang.c aruzinsky<(E-Mail Removed)> wrote:
>>
>>> 1. "it already looks a bit more accessible without doing anything that
>>> might slow the program down." - Speak for yourself; it looks more
>>> accessible to you because you have been brainwashed into accepting the
>>> absurdities of programmer culture. The practice of initializing and
>>> incrementing pointers separately from loop counters is moronic.


So is having source lines that are so long and convoluted.
>>
>> I don't see writing easy to read code as "moronic" or being
>> "brainwashed",

>
> 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[i]*cx[i]
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.
>
>>> 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.

>>
>> Suit yourself as long as I don't have to deal with your code
>> on a regular basis...


> 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
 
Reply With Quote
 
 
 
 
Peter Flass
Guest
Posts: n/a
 
      01-11-2011
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?
 
Reply With Quote
 
nmm1@cam.ac.uk
Guest
Posts: n/a
 
      01-11-2011
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:

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. 198 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.


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

>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.

>> Similarly, functions become pointers in all contexts except actual
>> calls.

>
>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.
 
Reply With Quote
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      01-11-2011
< Crossposting cut down to clc >

> 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...

In comp.lang.c aruzinsky <(E-Mail Removed)> wrote:
> On Jan 10, 8:18*pm, (E-Mail 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).

> > > 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.

> >
> > I may not be too good at C++ but when c(int) (let's assume
> > int was the type of the argument) is, as you say, for acces-
> > sing an element of an array, which probably means that it is
> > returning a float value element of that array (or what means
> > "accessing" in this context?), how does taking the address of
> > that (or any) return value makes sense, may it be C or C++?


> 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[i]
> is gotten with &x[i]? 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
--
\ Jens Thoms Toerring ___ http://www.velocityreviews.com/forums/(E-Mail Removed)
\__________________________ http://toerring.de
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-11-2011
pete <(E-Mail Removed)> writes:
> (E-Mail Removed) wrote:
>
>> >> Similarly, functions become pointers in all contexts except actual
>> >> calls.

>
>> 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.

>
> 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 (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-11-2011
Phil Hobbs <(E-Mail Removed)> writes:
> Richard Maine wrote:
>> Phil Hobbs<(E-Mail Removed)> wrote:
>>> ...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.)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
aruzinsky
Guest
Posts: n/a
 
      01-11-2011
On Jan 11, 3:06*am, Martin Brown <|||(E-Mail Removed)>
wrote:
> On 11/01/2011 04:21, aruzinsky wrote:
>
> > On Jan 10, 8:18 pm, (E-Mail Removed) (Jens Thoms Toerring) wrote:
> >> In comp.lang.c aruzinsky<(E-Mail Removed)> *wrote:

>
> >>> 1. "it already looks a bit more accessible without doing anything that
> >>> might slow the program down." - Speak for yourself; it looks more
> >>> accessible to you because you have been brainwashed into accepting the
> >>> absurdities of programmer culture. The practice of initializing and
> >>> incrementing pointers separately from loop counters is moronic.

>
> So is having source lines that are so long and convoluted.
>
>
>
> >> I don't see writing easy to read code as "moronic" or being
> >> "brainwashed",

>
> > 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!
>


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[i]*cx[i]
> 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.

>
>
> > 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...
>


Again, you are falsely pretending to argue with me.

> > 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.
>


Again, you are falsely pretending to argue with me.

>
>
> >>> 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.

>
> >> Suit yourself as long as I don't have to deal with your code
> >> on a regular basis...

> > 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.
>


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.

> Regards,
> Martin Brown


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-11-2011
(E-Mail Removed) writes:
> In article <(E-Mail Removed)>,
> Keith Thompson <(E-Mail Removed)> wrote:
>
> 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. 198 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.
>
>>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.


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.)

>>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.

>
> 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.

>>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.


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

>>> Similarly, functions become pointers in all contexts except actual
>>> calls.

>>
>>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.


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.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      01-11-2011
On 2011-01-11, Peter Flass <(E-Mail Removed)> wrote:
> 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
--
Copyright 2010, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Chicken Recipes - The Web's Largest Chicken Recipes Collection Lew Java 1 02-21-2009 02:44 AM
Java numerical recipes online... Al Murphy Java 1 02-05-2004 06:14 PM
Error in Numerical Recipes lubksb routine mma C Programming 5 12-09-2003 09:36 AM
Re: numerical recipes book E. Robert Tisdale C Programming 0 07-31-2003 02:02 AM
Re: numerical recipes book Rouben Rostamian C Programming 0 07-30-2003 02:04 PM



Advertisments