On 16 Nov 2006 23:42:00 -0800, "Arlet" <usenet+5...@ladybug.xs4all.nl>
wrote:

>As always in embedded software: it depends.  If you automatically
>assume embedded means a small micro, you're just making different
>assumptions. Even though most embedded application use small 4/8 bit
>CPUs, there are plenty of other embedded applications that use a full
>power Pentium/AMD board. On such a CPU, the floating point square root
>can be done by a single 'fsqrt' instruction, which beats the integer
>version in size, and possibly speed.

According to early Pentium manuals (1995) the fsqrt takes 70 cycles
and the integer load/store to FP stack an additional 7-9 cycles, while
integer basic instructions are in the 1/2/3 cycle range, so the
integer square root should be done with about 30-60 integer
instructions executed, to beat the speed. 

Paul
 

Lanarcam wrote:

> "Arlet" <usenet+5...@ladybug.xs4all.nl> a =E9crit dans le message news:
> 1...@f16g2000cwb.googlegroups.com...
> >
> > Lanarcam wrote:
> >
> > > The only reasonable instruction is:
> > >  a =3D ++a & 0x01 ;
> >
> > No, that one is undefined, because it has two side effects to 'a' and
> > only one sequence point.
> >
> In this case the preincrement operator ++a is used and not the
> postincrement operator a++. What is the error in this line
> of reasoning: a is incremented first, then the new value of a is
> used to evaluate the right hand expression , then the result
> is assigned to a?

According to the C standard, the side effects of evaluations can be
delayed until the next sequence point. There are various sequence
points defined, but a 'full expression' is one of them, which
corresponds to the entire line above.

The preincrement '++a' expression results in 'a+1' for evaluation
purposes, but the implicit assignment back to 'a' can be delayed until
the entire expression is done.

So, a compiler could turn this into:

t1 =3D a + 1;
t2 =3D t1 & 0x01;
a =3D t2;
a =3D t1;

42Bastian Schick wrote:
>> If it doesn't need to be optimized, I prefer this version:
>>
>>    a = !a;
> 
> At least in C (AFAIK) the value of !a is not defined only it is 
> unequal 0 (correct me if I am wrong).
> 
> Most compilers I have seen change an int from 0 to -1 and back.

Could you name them?


-- 
WBR, Yuriy.
"Resistance is futile"

42Bastian Schick wrote:

>>>> More often than not it is more important than saving two bytes and 500 
>>>> nanoseconds.
>>> It is about embedded where 500ns could mean "go" or "no go".
>> There is no point to spend time optimizing small pieces of code. Most 
>> efficient optimization is changing the whole algorithm, not improving 
>> bit-banging.
> 
> Last comment (we are meanwhile far away from the OT):
> What if bit-banging is the only part of the algorithm or the algorithm
> is already optimized ?

Then the algorithm is too simple for the meaningful discussion.

-- 
WBR, Yuriy.
"Resistance is futile"

Lanarcam wrote:

>>> The only reasonable instruction is:
>>>  a = ++a & 0x01 ;
>> No, that one is undefined, because it has two side effects to 'a' and
>> only one sequence point.

Exactly.

> In this case the preincrement operator ++a is used and not the
> postincrement operator a++. What is the error in this line
> of reasoning: a is incremented first, then the new value of a is
> used to evaluate the right hand expression , then the result
> is assigned to a?

C standard, of course, what else?

ISO/IEC 9899:1999

6.5 Expressions

2. Between the previous and next sequence point an object shall have its 
stored value modified at most once by the evaluation of an expression. 
Furthermore, the prior value shall be read only to determine the value 
to be stored.
...
This paragraph renders undefined statement expressions such as
i = ++i + 1;
a[i++] = i;

-- 
WBR, Yuriy.
"Resistance is futile"

"Arlet" <usenet+5...@ladybug.xs4all.nl> a écrit dans le message news:
1...@h48g2000cwc.googlegroups.com...

Lanarcam wrote:

> "Arlet" <usenet+5...@ladybug.xs4all.nl> a écrit dans le message news:
> 1...@f16g2000cwb.googlegroups.com...
> >
> > Lanarcam wrote:
> >
> > > The only reasonable instruction is:
> > >  a = ++a & 0x01 ;
> >
> > No, that one is undefined, because it has two side effects to 'a' and
> > only one sequence point.
> >
> In this case the preincrement operator ++a is used and not the
> postincrement operator a++. What is the error in this line
> of reasoning: a is incremented first, then the new value of a is
> used to evaluate the right hand expression , then the result
> is assigned to a?

According to the C standard, the side effects of evaluations can be
delayed until the next sequence point. There are various sequence
points defined, but a 'full expression' is one of them, which
corresponds to the entire line above.

The preincrement '++a' expression results in 'a+1' for evaluation
purposes, but the implicit assignment back to 'a' can be delayed until
the entire expression is done.

So, a compiler could turn this into:

t1 = a + 1;
t2 = t1 & 0x01;
a = t2;
a = t1;

Thanks for the answer, it's never too late to learn something.

Arlet wrote:
> David Brown wrote:
> 
>> Arlet wrote:
>>> 42Bastian Schick wrote:
>>>
>>>>> Actually, it is
>>>>> s = sqrt(a);
>>>>> C programmer shall know basic standard library functions.
>>>> Sorry, failed. Question was: "...squart root of an integer"
>>>> Your solution imposes two castings and pulls in floating point
>>>> arithmetics.
>>> But his solution does produce the square root of an integer, as
>>> requested. The solution is simple, and it works (although you could
>>> complain the result is truncated rather than properly rounded). It
>>> could also allow a smart compiler to recognize it can pull in an
>>> optimized version of integer square root.
>>>
>> I'm not sure if a compiler is allowed to do that or not, but certainly
>> no compiler would do it (a C++ compiler would be another matter).
>>
>>> If you wanted it optimized, you should have provided more info. What is
>>> the word length, target CPU, required precision, and size/space
>>> constraints ? Do you want it in generic C, or ASM ?
>>>
>> The thread subject is "interview embedded software questions" - when
>> asked to find an integer square root, the interviewee should respond by
>> asking what sort of constraints apply (and what ready-written functions
>> and libraries are available).  If he has to answer without more
>> information, a programmer who assumes floating point operations are okay
>> for an integer task on a small micro fails on that question.
> 
> As always in embedded software: it depends.  If you automatically

Agreed - that's why the correct response is to look for more details. 
My point is just that if you have no choice but to make an assumption, 
then when asked for an integer square root on an embedded system, you 
should look for an integer-only solution.  The best integer-only 
solution, of course, depends entirely on the other constraints you don't 
know.  In a good interview situation, this would lead to the candidate 
demonstrating a knowledge of what might be important in an embedded 
system, rather than any integer square root algorithm.

> assume embedded means a small micro, you're just making different
> assumptions. Even though most embedded application use small 4/8 bit
> CPUs, there are plenty of other embedded applications that use a full
> power Pentium/AMD board. On such a CPU, the floating point square root
> can be done by a single 'fsqrt' instruction, which beats the integer
> version in size, and possibly speed.
> 
> Without any further information, there is something to be said for
> providing the simplest answer to the question.
> 

Yuriy K. wrote:
> 42Bastian Schick wrote:
> 
>>> Because three years later new programmer will spend two hours trying 
>>> to figure out if *a* can or can not be equal to 2 or 3, and what is 
>>> this silly line meant to do.
>>
>> I expect a "new programmer" to understand the whole source he is
>> responsible for and not only one line of code.
> 
> I feel pity for them. I saw quite a few projects that were easier to 
> rewrite completely than maintain and modify. Original developer was able 
> to write five lines of code "efficiently", but had no clue about project 
> design in general.
> 
>> Most code (C,Assembler, Cobol ....) is hard to understand without
>> the context.
> 
> Bad written code like is hard to understand. Good written code is easy.
> 
>>> More often than not it is more important than saving two bytes and 
>>> 500 nanoseconds.
>>
>> It is about embedded where 500ns could mean "go" or "no go".
> 
> There is no point to spend time optimizing small pieces of code. Most 
> efficient optimization is changing the whole algorithm, not improving 
> bit-banging.
> 

Always remember Knuth's rules of optimisation:
1) Don't do it.
2) (For experts only) Don't do it yet.

On Fri, 17 Nov 2006 03:19:39 -0600, "Yuriy K." <y...@mail.ru> wrote:

>42Bastian Schick wrote:
>>> If it doesn't need to be optimized, I prefer this version:
>>>
>>>    a = !a;
>> 
>> At least in C (AFAIK) the value of !a is not defined only it is 
>> unequal 0 (correct me if I am wrong).
>> 
>> Most compilers I have seen change an int from 0 to -1 and back.
>
>Could you name them?

*hmm* no. I was wrong,sorry. I go back where I belong ... bits and
bytes and
machine-code.

-- 
42Bastian
Do not email to b...@yahoo.com, it's a spam-only account :-)
Use <same-name>@monlynx.de instead !

larwe wrote:
> Al  Borowski wrote:
> 
>> You've got me. If I was asked this in an interview I'd be stumped. What
>> kind of non-seriously broken system could have z not being equal to
>> three?
> 
> This response illustrates nicely that cute interview questions do not
> select good employees, merely employees who know the answers to trick
> questions.

Reminds me of the time I was asked to construct an XOR gate out of the 
minimum number of NAND gates. It's not obvious, but I had happened to 
have seen this trick a long time ago, so I got it right. It said nothing 
of my qualifications for the job, just that the interviewer did not know 
what kinds of questions to ask.