store_integers_missing_in_float.cpp

// Simple tool to store all integers which are missing in the float representation.
//
// Missing means here that if you convert integer into float and then back into 
// integer you will not get the same integer. This experiment reveals that for
// 96.5% of all integers n != int(float(n))
//
// It appears that missing integers go in blocks of length 2, 6, 14, 30, 62 
// and 126 of consecutive numbers (8388608 blocks of each type). 
// And there is one single integer -33554431 who stands apart.
//
// Plot of missing integers distribution created using output of this program
// http://www.anony.ws/i/2014/06/20/missing_integers_distribution.png
//
// To compile:
// g++ store_integers_missing_in_float.cpp -o store_integers_missing_in_float
// 
// Note this program creates 1.3G text file as result.

#include <fstream>
#include <limits.h>
#include <cassert>
#include <iostream>
#include <iomanip>

enum State {
  SKIP, UNKNOWN, SINGLE, LEFT, RIGHT
};

int main(int argc, char** argv) {
  if (argc != 2) {
    std::cerr << "USAGE: ./store_integers_missing_in_float output.txt\n";
    return 1;
  }

  std::fstream fs (argv[1], std::fstream::out);
  State state = SKIP;
  State prev_state = SKIP;
  int left,right; // Uninitialized, hope it will be initialized before printing.
  float total = UINT_MAX;
  size_t count = 0;
  size_t local_count = 0;
  size_t local_total = 0;
  for (int i = INT_MIN; i < INT_MAX; ++i) {
    bool missing = (i != static_cast<int>(static_cast<float>(i)));

    if (missing) {
      right = i;
      ++count;
      ++local_count;
    }
    // Determine new state
    switch (state) {
      case SKIP:
        if (missing) {
          left = i;
          state = UNKNOWN;
        }
        break;
      case UNKNOWN:
        if (missing) {
          state = LEFT;
        } else {
          state = SINGLE;
        }
        break;
      case LEFT:
        if (!missing) {
          state = RIGHT;
        }
        break;
      case RIGHT:
        if (missing) {
          left = i;
          state = UNKNOWN;
        } else {
          state = SKIP;
        }
    };

    // Action
    if ((prev_state == UNKNOWN) && (state == SINGLE)) {
        fs << left << " #1\n";
        assert(left == right);
    }
    if ((prev_state == LEFT) && (state == RIGHT)) {
        fs << "[" << left << "," << right << "] #" << right-left << "\n";
        assert(left < right);
    }
    prev_state = state;

    long int processed = static_cast<long int>(i) - static_cast<long int>(INT_MIN);
    float progress = processed / total;
    if ((processed!=0) && (i % (1 << 25) == 0)) {
      float local_percentage = 0;
      if (local_total != 0) {
        local_percentage = 100*static_cast<float>(local_count)/local_total;
      }
      float total_percentage = 100*static_cast<float>(count)/processed;
      std::cout << std::fixed << std::setw(2) << std::setprecision(2)
                << i << "\t" << 100*progress << "% \t"
                << count << " missing integers found so far:\t"
                << "local=" << local_percentage << "% "
                <<  "total=" << total_percentage << "%." << std::endl;
      local_count = 0;
      local_total = 0;
    }

    ++local_total;
  }
  fs.close();

  std::cout << "100% processed. " << count << " missing integers found."
            << std::endl;
  std::cout << "So " << std::fixed << std::setw(2) << std::setprecision(2)
            << 100*static_cast<float>(count)/UINT_MAX << "%"
            << " of all integers are missing in float." << std::endl;
  return 0;
}