Just Larger

This week, something short & sweet & probably useful for generic programming: find the next integral type just bigger than a given type. The obvious application would be that if you want to add ints, you’ll want the variable that holds the sums to be larger than int. In generic programming, however, you don’t necessarily know beforehand that the base type will be int.

Turns out, while there’s’nt anything built-in to do that, it isn’t very complicated either. First, we will define a series of templates with overloads; second, we will use using to extract the type seamlessly.

We will define a struct (rather than a class, merely to avoid adding public:) that defines a type type depending on its template argument. The trick is that if T is xyz then define nested type zyx and make it public. Since we can’t (or at least, I haven’t figured how to) have some kind of switch/case on types, we will have to define explicit specializations, one for each supported (integral) type.

The simplest possible implementation would be something like this:

////////////////////////////////////////
template <typename T> struct just_larger_; // incomplete type is default

// some are implementation-specific (char may or may not be signed)
template <> struct just_larger_<char> { using type = int16_t; };

// some standard types
template <> struct just_larger_<int16_t>  { using type = int32_t;  };
template <> struct just_larger_<uint8_t>  { using type = uint16_t; };
template <> struct just_larger_<uint16_t> { using type = uint32_t; };

// "extracts" type
template <typename T>
 using just_larger=
  typename just_larger_<T>::type;

Of course, one would have to define all overloads for the basic types, the types from headers <cstddef>, <cstdint>, and any other platform- or implementation-specific headers.

The usefulness of just_larger<T> is within another template. If one of the arguments of the this template is used with just_larger, then it’s simple. If, for some reason, you do not have directly access to the type, but only to, say, a field name, you may need to use decltype, a C++11 addition. decltype gives the declared type of an entity or of an arbitrary expression.

An example of use:

#include <iostream>
#include <cstdint>
#include <typeinfo>
#include <type_traits> // for typeid and type_info

#include <just_larger.hpp>

int main()
 {
  just_larger<char> z;

  std::cout
   // use from type
   << sizeof(just_larger<char>) << std::endl

   // use from variable
   << typeid(z).name() << std::endl
   << sizeof(decltype(z)) << std::endl
   << typeid(just_larger<decltype(z)>).name() << std::endl
   << sizeof(just_larger<decltype(z)>) << std::endl
   ;

  return 0;
 }

The typeid operator returns a (const) reference on a std::type_info, a class that holds some information on the type. Unfortunately, name() doesn’t print pretty names, but some implementation-specific string: int is not printed as int but as i. That’s somewhat cryptic, but enough to verify that the implementation works correctly.

*
* *

We could overload just_larger with just anything, not just integral types. One evident generalization would be from float to double, but it can be anything that makes sense for your application. Also, maybe just_larger needs a companion template much_larger, that could ensure that large sums a given type would not overflow.

ANSI soit-il.

There’s no easy way of getting a console-based color output with standard C++. Of course, you can use ncurse, which does pretty much everything, but that is also quite tedious to use. But if you need just a little bit of color, ncurse is pretty overkill. Fortunately, if you have an ANSI capable terminal, that’s much easier.

Smaller enums

As you may have noticed, efficient representation of information and data structure is kind of a hobby of mine. I often look at ways I can reduce the memory footprint, and, as often, it’s the small details that are the most annoying, like, for example, enums that use up pretty much anything the compiler feels like.

Indeed, the standard does not require that the compiler uses the smallest type, but merely one that can hold all values (§7.2.6, in ISO/IEC 14882:2011(E)), so you end up with something “convenient”, that is, int. Unless, of course, you do specify storage.

Rational Approximations (Part II)

Last week, we noticed a fun connection between lattices and fractions, which helped us get rational approximations to real numbers. Since only points close to the (real-sloped) line are of interests, only those points representing fractions are candidates for rational approximation, and the closer to the line they are, the better.

But what if we find a point real close to the line? What information can we use to refine our guess?

Rational Approximations

Finding rational approximations to real numbers may help us simplify calculations in every day life, because using

makes back-of-the-envelope estimations much easier. It also may have some application in programming, when your CPU is kind of weak and do not deal well with floating point numbers. Floating point numbers emulated in software are very slow, so if we can dispense from them an use integer arithmetic, all the better.

However, finding good rational approximations to arbitrary constant is not quite as trivial as it may seem. Indeed, we may think that using something like

will be quite sufficient as it will give you 6 digits precision, but why use 3141592/1000000 when 355/113 gives you better precision? Certainly, we must find a better way of finding approximations that are simultaneously precise and … well, let’s say cute. Well, let’s see what we could do.