A conversionless conversion function

A rant about programming interview questions

Software development is a peculiar field. An applicant for a more traditionally artistic position would bring a portfolio to eir job interview: a selection of creations ey deems representative of eir work and wants to be judged by. But in the field of software development, candidates are often asked to solve a programming problem live, the equivalent of telling a candidate for a photography job “these are nice photographs you have brought, but could you take a picture for me, right now, with this unfamiliar equipment?”

Lots have already been written on programming job interview questions. Googling “fizzbuzz” alone reveals plenty of positions taken, reacted to, and counter-argumented. I do not intend to add to the edifice. Taking a step back, however, I notice that many of these posts do not tackle the question of why what works for the traditional arts should not be appropriate for the art of programming.

What I intend to discuss is the poor quality of “do this simple task, but avoid this simple construct that makes it trivial” interview questions. I hate those. Everytime I hear a new one it seems to reach a new high in sheer stupidity. The questions are usually very poorly specified, too. One such question might be to convert a floating-point value to integer without using a cast. Is floor() or ceil() allowed? Are other library functions than these ones that solve the problem too directly allowed? May I use a union to access the bits of the floating-point representation? Or memcpy()?

Well, I have solved this particular question once and for all. The conversion function makes up the second part of this post. It uses only floating-point computations, no tricks. Now, one just needs to learn it and to regurgitate it as appropriate at interview time (there is no way one can write a working version of this program on blackboard, too). Who is hiring?

A program

The function below requires a strict IEEE 754 implementation. If your GCC is generating x87 instructions, options -msse2 -mfpmath=sse should prevent it from doing so and allow you to run the program:

#include <math.h> 
#include <float.h> 
#include <stdio.h> 
#include <limits.h> 
/*@ requires 0 <= f < ULLONG_MAX + 1 ; */ 
unsigned long long dbl2ulonglong(double f) 
{ 
  if (f < 1) return 0; 
  unsigned long long l = 0; 
  for (double coef = 3; coef != 0x1.0p53; coef = 2 * coef - 1, l >>= 1) 
    { 
      double t = coef * f; 
      double o = f - t + t - f; 
      if (o != 0) 
	{ 
	  l |= 0x8000000000000000ULL; 
	  f -= fabs(o); 
	} 
    } 
  l |= 0x8000000000000000ULL; 
  for ( ; f != 0x1.0p63; f *= 2) l>>=1; 
  return l; 
} 
int main() 
{ 
  double f = 123456.; 
  unsigned long long l = dbl2ulonglong(f); 
  printf(esult:%.18g %llu"  f  l); 
  f = ULLONG_MAX * 0.99; 
  l = dbl2ulonglong(f); 
  printf("result:%.18g %llu"  f  l); 
  printf("rounding:%llu %llu %llu %llu"   
	 dbl2ulonglong(DBL_MIN)  
	 dbl2ulonglong(1.4)  
	 dbl2ulonglong(1.5)  
	 dbl2ulonglong(1.6)); 
  return 0; 
} 

The expected result is:

result:123456 123456 
result:1.82622766329724559e+19 18262276632972455936 
rounding:0 1 1 1 

Incidentally does anyone know how to write a correctness proof for this function? A formal proof would be nice but just an informal explanation of how one convinces oneself that o = f - t + t - f is the right formula would already be something.