Answering My Own Interview Question On Integer Maths In C

I've been using this interview question for the last 20 years to test embedded C engineers:

Given the formula for Fahrenheit as

9 * C + 32 = F
-
5  

Write a function to convert unsigned char tempInC to unsigned char tempInF (ie. All values are bytes, including intermediate results). The processor has no floating point library.

Recently I was intrigued to find that a very similar problem was posed by professor James M. Conrad at the University of North Carolina at Charlotte at this point in his lecture on Embedded Systems: Software Testing.

Candidate Responses

The responses I used to get were similar to what the students gave in that video. Whilst some candidates would think this was a maths problem that needed rearranging to solve for tempInC, others thought that I just wanted them to write the formula in C syntax.

A large percentage of candidates would ignore the premise of the question and cast the parameters to floats, do the calculation as a floating point one and cast the result back to integers. As well as being not anywhere near what I was asking for, this approach leads to rounding down so that 21°C, which should be converted to 70°F (69.8°F) becomes 69°F. Once told that floats were not available, a few tried casting to 16 bit ints and possibly multiplication by 10 to increase precision. Whilst this is a reasonable practical solution, it wasn't what the test was about.

The next most popular answer would be to put the 9/5 in brackets, as if this forced the compiler to acknowledge that it was a real number. It showed that they were not aware that this would evaluate to 1 (1.8 truncated) which makes a mess of the conversion function.

A rare few would see that the real issue is loss of precision coupled with risk of overflow and would decide to do the multiply by 9 first, then the divide by 5. This appears to be a reasonable answer, although I once had a candidate realize that they could check for potential overflow caused by the multiply by 9 before doing it, and in that case do the divide by 5 first.

uint8_t ctof_truncates(uint8_t c)
{    //simple version, rounds fractions down
    uint8_t i;

    if (c < 255 / 9)
    {
        i = c * 9;
        i /= 5;
    }
    else
    {
        i = c / 5;
        i *= 9;
    }

    i += 32;

    return i;
}

Ask for the specification

One of the reasons for asking about this problem is that there is an unstated assumption which I was always hoping that a candidate would spot, or at least state their interpretation.

What is the input range?

Although we are talking about 8 bit unsigned numbers, is it realistic to expect 255°C as an input? The context was given verbally, that as manufacturers of heating controls, this problem would occur in the design of a room thermostat. So, no, 255°C would not be reasonable; 0°C to 40°C should be adequate.

The candidate should have attempted to clarify this before writing their solution or at least document their assumption, because this is an aspect of being an engineer that is encountered daily. Unless this is done, it will trip up others who then take that code and reuse it.

Without me meaning it to be so, I now think this is a trick question.

The problem is that there is an internal overflow condition as soon as you get to the hot but not impossibly hot 29°C. Because 29*9=261, you'd have to use the "divide by 5 first" method on inputs above 28, but that means that 30, 31, 32, 33 and 34 all give 86°F which is going to cause control problems if we can't distinguish these values for a room thermostat. That assumes integer division with it's truncating behaviour, but even if a good rounding method is used (too tricky to be expected to be invented in an interview) it still means that 29°C to 32°C all give 86°F which isn't good enough. And if you don't use a good rounding method there's also the weird problem that 29°C converts to 77°F (29/5)*9+32 which means the function isn't monotonically increasing.

Integer Divide With Rounding

Before we get back to the problem of handing 30°C and above, let's look at what happens to values below 30 and the inevitable rounding problem. Since we are working with so few bits of resolution here, we really can't be satisfied with 21°C being converted to 69°F (rounded down 69.8) when it should be rounded up to 70°F.

This sounds like it should a solved problem with a standard answer. Indeed, StackOverflow gives the standard answer as

#define ROUND_UDIVIDE(numer, denom) (((numer) + (denom) / 2) / (denom))

but this doesn't take my 8 bit unsigned integer constraint into account and do anything about the overflow problem. Taking ideas from another answer I ended up with this routine, which I have now exhaustively tested for all n and d values in the 8 bit unsigned range.

uint8_t divRoundClosest(const uint8_t n, const uint8_t d)
{
    uint8_t r, m;
    if (n <= UINT8_MAX - d / 2)    //addition will not overflow
        return (n + d / 2) / d;    //idea from https://stackoverflow.com/a/58568736/8157
    else //addition would overflow so do integer divide and see if needs rounding up
    {
        r = n / d;        //simple integer divide
        
        //in most cases, modulo result below is tested against d/2. But (d/2) needs to be calculated with rounding not truncation
        //so is replaced with (d + 2/2)/2 = (d+1)/2. But this will overflow if d=UINT8_MAX, so don't add 1 for that and it doesn't affect results.
        m = d;
        if (m < UINT8_MAX)
            m++;

        if (n % d >= m / 2)    //idea from https://stackoverflow.com/a/6967706/8157
            r++;            //result needed rounding up 
        
        return r;
    }
}

Note that this is specifically for unsigned ints and is not tested for signed ints.

Which gives good answers for the ctof conversion with inputs in the range 0 to 28.

Signed Int For Dividend And Divisor

Whilst looking for a good unsigned integer divide with rounding, I found a good function for the more general case of signed inputs. Try this StackOverflow answer

int divRoundClosest(const int n, const int d)
{
  return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}

Good Rounding Doesn't Help If You Divide Inputs by 5

Replacing the simple integer division with divRoundClosest doesn't help that much for the cases of inputs of 29 to 40 because you still get sets of inputs which all give the same output, for example 29 to 32 all give 86°F. Is there any way to avoid this, given the problem constraints?

Scaling up by 3

The most you can scale the input up by is 3, assuming a maximum input of 40°C, because otherwise you hit an overflow at the intermediate step when multiplying by 9 scaled up. Specifically, if you try to use a scale factor 4, at the max input of 40, the first step is (40*4)/(5*4)=8, but the second step is 8*9*4 = 288 which is more than 255.

If you do all the calculations scaled up by 3, you find that inputs 33 to 37 all give output 95, which then jumps to 104 at 38. Still not very good.

Trick Questions Have Trick Answers

A simple solution, which I don't think anyone ever came up with in an interview, was a lookup table. The code space of the solution so far is probably about the same size as this lookup table which is simple to calculate in Excel and paste in. The function becomes trivial:

//lookup table for fahrenheit values for centigrade range 0 to 40 inclusive
const uint8_t ctofLookup0_40[] = { 32,34,36,37,39,41,43,45,46,48,50,52,54,55,57,59,
61,63,64,66,68,70,72,73,75,77,79,81,82,84,86,88,90,91,93,95,97,99,100,102,104 };

uint8_t ctof_lookup(uint8_t c)
{
    if (c < sizeof(ctofLookup0_40))
        return ctofLookup0_40[c];
    return 0;    //f should not be zero, treat this as an error condition
}

Getting a comma separated value list out of Excel

Column 1 is the C values of interest.
Column 2 is the floating point F values =c*9/5+32
Column 3 is the rounded F values =round(f, 0)
The list of values is obtained with the formula =TEXTJOIN(",",TRUE,C2:C42)

Was the Question Unfair?

I didn't expect anyone to do anything like this amount of work under interview conditions, and in fact said several times that this is not a maths problem - I don't want you to calculate any limit values in your head or rearrange the equation. And I was not looking for a pat answer from someone who had happened to come across this previously.

The point of the question was to see how the candidate tackled the problem, to be a starting point for discussions about integer maths and overflows, to see where the limitations were and how to test the function. For that usage, it worked great.

As a side effect, it also showed if the candidate could write the barest minimum of C code with correct syntax. This always came after a few other C examples to warm them up and since I was only looking for a few lines of code could hardly be seen as overly demanding. After all, if they are going to be spending all day writing C code, they need to prove they can at least write a few lines before we talk about a job offer. (See The Joel Test, point 11).

But I always valued the discussion about the code more than what they had actually written. If a candidate had frozen (interview anxiety is common) but was still capable of intelligently discussing these points, I would still be interested in them.

Why I am not allowing 16 bit variables and calculations?

That of course is the way to solve this in practice, not lookup tables. It is worth recognizing that 16 bit variables on their own do not solve this, it still requires scaling up, and a decision on the scaling factor based on the maximum input. I purposely reduced the variable size to cause the overflow to be more obvious and at a common input value so that candidates had to think about that.

Comparing Implementations

Starting from a default STM32CubeIDE project for the STM32F4 discovery board, allowing the peripheral defaults and then disabling the USB stack, there is not much that needs to be changed. I added my ctof.c and ctof.h files which had been tested under VS2019, and the GPIO is already set up to drive the onboard LEDs such as the orange LED LD3 on PD13. main.c was modified just to declare two variables and run the calculation inside loop, setting a pin high at the start and low at the end so that it could be measured on the scope. The loop overhead including function call was subtracted from the timing before dividing by the number of loop iterations, and was running at 168 MHz sysclk.

/* USER CODE BEGIN 1 */
    uint8_t degC;
    volatile uint8_t degF; //so that compiler doesn't optimise out the function call entirely since result not used.

  /* USER CODE END 1 */

//later...

 /* USER CODE BEGIN WHILE */
  while (1)
  {
      HAL_GPIO_WritePin(GPIOD, GPIO_PIN_13, GPIO_PIN_SET);
      for(degC = 0;degC < 41;degC++)
      {
          degF= ctof_lookup(degC);
      }
      HAL_GPIO_WritePin(GPIOD, GPIO_PIN_13, GPIO_PIN_RESET);
    /* USER CODE END WHILE */

    /* USER CODE BEGIN 3 */
  }
  /* USER CODE END 3 */

It's no surprise that lookup is faster, but in this case it is also half the size of the simplest reasonable version.

Further Reading

round() for float in C++ 
Rounding integer division (instead of truncating)