Interview Embedded Software Questions

Sorry, failed. Question was: "...squart root of an integer" Your solution imposes two castings and pulls in floating point arithmetics.

I expect a "new programmer" to understand the whole source he is responsible for and not only one line of code.

Most code (C,Assembler, Cobol ....) is hard to understand without the context.

It is about embedded where 500ns could mean "go" or "no go".

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.

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 ?

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

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

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. But I've seen also one which does what was asked, changing 0->1->0.

I do not believe I would even consider going. Inability to ask an accurate questions is not a good sign.

My solution takes 15 seconds of expensive programmer time to write and it works. If you expected employee to read minds, you should mention "psychic ability" in the job requirements. :)

As I quoted earlier, "Premature optimization is the root of all evil". In 99% cases using standard library is the best choice.

The real questions to be answered are: "What need to be done?" and "How much time and money do we have?" Calculating square roots is a minor technical problem with zillion different ways to do and it is not worth mentioning at all. :)

According to the standard, section 6.5.3.3:

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.

Bad written code like is hard to understand. Good written code is easy.

There is no point to spend time optimizing small pieces of code. Most efficient optimization is changing the whole algorithm, not improving bit-banging.

Then it is not a C compiler. From N869:

... snip ...

Semantics

... snip ...

Now I know it better ;-)

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 ?

"Arlet" a écrit dans le message news: snipped-for-privacy@f16g2000cwb.googlegroups.com...

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

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;

Could you name them?

Then the algorithm is too simple for the meaningful discussion.

Exactly.

C standard, of course, what else?

ISO/IEC 9899:1999

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

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.