## Friday, November 28, 2008

### More on price gas hysteresis

We redo the hysteresis analysis we conducted on gas prices, now for a longer period of time and using much more data than before:
• Average weekly retail prices without taxes of 95 octane gasoline and gasoil in Spain have been obtained from the European Commision Oil Bulletin (thanks to Wonka for the pointer).
• The US Energy Information Administration provides daily spot prices of Brent oil in dollars per barrel.
• Historical data on euro to dollar exchange rates can be retrieved from FXHistory.

Using this information we have constructed the following figure showing the evolution of Brent prices and gasoline and gasoil Spanish retail prices without taxes, all in c€ per liter, between January 2006 and October 2008.

And this is the scatter plot of Δ(gasoline price before taxes) against Δ(Brent price):

The linear regressions of this plot for the semiplanes Δ(Brent price) ≥ 0 and ≤ 0 are:

ΔBrent ≥ 0 → y = f+(x) = b+ + m+x = 0.1854 + 0.1691x,
ΔBrent ≤ 0 → y = f(x) = b + mx = 0.1273 + 0.3636x.

On one hand, m is more than twice as large as m+, which indicates that gasoline price follows oil price reductions much more strongly than oil price increases when these variations are large; when oil price variations are small, it is the fact that both b+ and b+ are positive that dominates the situation: gasoline prices have a very clear bias towards increasing then. The "consumer unfavorable" region in which f+(x) > −f(−x) is

−1.61 c€/l < ΔBrent < 1.61 c€/l.

As for gasoil, the plot look like this:

with regression lines

ΔBrent ≥ 0 → y = f+(x) = b+ + m+x = 0.2669 + 0.1269x,
ΔBrent ≤ 0 → y = f(x) = b + mx = 0.2391 + 0.4134x.

Again, m is much greater than m+ (~3.25 times), but this is masked for small variations of Brent price by the constants b+ and b+ being greater than zero. The consumer unfavorable region is

−1.77 c€/l < ΔBrent < 1.77 c€/l,

which is very similar to the consumer unfavorable region for gasoline.

So, we have a somewhat mixed scenario: when oil prices do not vary much, there is a tendency for retail gas prices to increase, whereas when oil price variations are high, reductions are tracked much more strongly than increases. We propose two explanations, both highly speculative, for this phenomenon:

• Small variations of oil prices do not reach public attention, which allows retailers to silently increase gas prices; high variations in oil price, however, generally make it to the news, so that retailers are under greater public scrutiny when transferring these variations to the pump.
• So as to soften the public negative reaction to price increments (and associated contractions in consumption), retailers do not reflect high increases in oil price as abruptly as oil price reductions, but opt to distribute the increment over a longer period of time; this would account both for the fact that m+ < m and for the positive bias in small price variations.

## Monday, November 24, 2008

### Optimizing red-black tree color bits

C++ associative containers are almost universally implemented on top of a structure known as a red-black tree. An rb tree node has approximately the following look:

`‎enum color_type{red=false,black=true};‎‎template<typename T>‎struct rb_node‎{‎  color_type color;‎  rb_node*   parent;‎  rb_node*   left;‎  rb_node*   right;‎  T          value;‎};`

The color of a node, from which the data structure receives its name, is used to implement some algorithms to keep the tree balanced. Note that the information conveyed by `color` is exactly one bit; yet, this member takes at least one `char` of storage and, in most platforms, much more than that because of alignment issues. Increasingly more libraries implement an optimization technique that is able to get rid of the extra storage demanded by `color` by embedding the information bit into one of the additional node fields. As this technique does not appear to be much documented on the Internet, this entry describes it in detail. Much of the material draws from the source code of Boost.MultiIndex. Some acquantaince with Boost.MPL is welcome to understand what follows.

To embed a bit into the representation of a pointer we need to use in place of the pointer an unsigned integer type with the same size. In most 32bit platforms this type is `unsigned int`, but the standard does not guarantee this, or even that such an integral type exists. We assume that we have the following utilities at our disposal:

`‎typedef ... has_uintptr_type;‎typedef ... uintptr_type;`

where `has_uintptr_type` is a Boost.MPL boolean indicating whether an unsigned integral type exists with exactly the same size as a pointer, and if so `uintptr_type` is such type. We will provide later an implementation for these.

Alignment considerations dictate that many types must lie in memory addresses that are multiple of some small integer greater than 1; in particular, it is extremely usual that the alignment of a type `T` is even (i.e. a multiple of 2), in which case the least significant bit of the representation of pointers to `T` is always zero. And this is precisely the situation in which we can reuse this bit to embed the color information:

`‎template<typename T,bool ColorBitCompression=true>‎class rb_node:‎  public boost::mpl::if_c<‎    ColorBitCompression&&‎    has_uintptr_type::value&&‎    (boost::alignment_of<compressed_rb_node_header>::value%2==0),‎    compressed_rb_node_header,‎    regular_rb_node_header‎  >::type‎{‎  T value_;‎‎public:‎  T&       value(){return value_;}‎  const T& value()const{return value_;}‎};`

`rb_node` uses a header with the color bit impression technique when:

1. This is requested by the user via `ColorBitCompression`.
2. There is an unsigned integer with which pointers can be represented.
3. The alignment of headers is even.

Otherwise a regular header is used. The implementation of the latter is entirely obvious:

`‎class regular_rb_node_header‎{‎  typedef regular_rb_node_header* pointer;‎‎  color_type                color_;‎  regular_rb_node_header*   parent_;‎  regular_rb_node_header*   left_;‎  regular_rb_node_header*   right_;‎‎public:‎  color_type& color(){return color_;}‎  color_type  color()const{return color_;}‎  pointer&    parent(){return parent_;}‎  pointer     parent()const{return parent_;}‎  pointer&    left(){return left_;}‎  pointer     left()const{return left_;}‎  pointer&    right(){return right_;}‎  pointer     right()const{return right_;}‎};`

As for `compressed_rb_node_header`, the most interesting part lie in the use of proxy classes `color_ref` and `parent_ref` to isolate the user from the representation of the color information and the parent pointer as a merged `uintptr_type`:

`‎class compressed_rb_node_header‎{‎  typedef compressed_rb_node_header* pointer;‎  struct color_ref‎  {‎    color_ref(uintptr_type* r_):r(r_){}‎ ‎    operator color_type()const‎    {‎      return color_type(*r&uintptr_type(1));‎    }‎ ‎    color_ref& operator=(color_type c)‎    {‎      *r&=~uintptr_type(1);‎      *r|=uintptr_type(c);‎      return *this;‎    }‎ ‎    color_ref& operator=(const color_ref& x)‎    {‎      return operator=(x.operator color_type());‎    }‎ ‎  private:‎    uintptr_type* r;‎  };‎  struct parent_ref‎  {‎    parent_ref(uintptr_type* r_):r(r_){}‎ ‎    operator pointer()const‎    {‎      return (pointer)(void*)(*r&~uintptr_type(1));‎    }‎ ‎    parent_ref& operator=(pointer p)‎    {‎      *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));‎      return *this;‎    }‎ ‎    parent_ref& operator=(const parent_ref& x)‎    {‎      return operator=(x.operator pointer());‎    }‎‎    pointer operator->()const‎    {‎      return operator pointer();‎    }‎‎  private:‎    uintptr_type* r;‎  };‎‎  uintptr_type parentcolor_;‎  pointer      left_;‎  pointer      right_;‎‎public:‎  color_ref  color(){return color_ref(&parentcolor_);}‎  color_type color()const{return color_type(parentcolor_&std::size_t(1ul));}‎  parent_ref parent(){return parent_ref(&parentcolor_);}‎  pointer    parent()const‎    {return (pointer)(void*)(parentcolor_&~uintptr_type(1));}‎  pointer& left(){return left_;}‎  pointer  left()const{return left_;}‎  pointer& right(){return right_;}‎  pointer  right()const{return right_;}‎};`

A complete example program is provided. In typical 32bit architectures, color bit compression makes the size of `rb_node<T>` reduce by 4 bytes.

This color bit compression technique introduces some penalty when accessing and modifying the color and parent information. This penalty, however, is entirely negligible. What is more, the reduction of size brought about by color bit compression usually results in a performance speedup for associative containers taking advantage of this trick: as nodes are smaller, more of them can be stored in L1 cache, which accelerates execution noticeably.

One final remark about this technique: as the parent pointer is no longer declared as a regular pointer, but rather represented by a masked integer, most C++ garbage collectors will not recognize the implicit pointer, which in principle can cause problems. All is fine, however, as it is only the parent that is masked: the right and left pointers are stored as genuine pointers, and as every node of a red/black tree is reachable only through left and right garbage collectors will not fail.

Thank you to Thorsten Ottosen for discussing this color bit compression technique with me.

## Thursday, November 20, 2008

### Infinitely many voters

As we have discussed before, the famous Arrow's Theorem is equivalent to this basic theorem on ultrafilters:

Every ultrafilter on a finite set is principal.

(See for instance Joel W. Robbin's paper for a proof of this equivalence.) Basically, the set on which the ultrafilter is built represents the voters, and the member sets of an ultrafilter can be equated with forcing coalitions, groups of voters which, if unanimous on a given preference, determine the overall result with respect to that preference. The theorem above says that every ultrafilter on a finite set of voters has a forcing coalition of size 1, i.e. a dictator.

If we have an inifite set, however, the Axiom of Choice implies that there are non-principal ultrafilters: so if there were infinitely many voters we could devise (alas, nonconstructively) a fair voting system free of dictatorships. It is interesting to try to take advantage of this result to somehow circumvent the limitations for the finite case, and see what fails (something must fail after all):

Let our voters be represented by the set V={v1,...,vN}: we "extend" them by assigning to each vi an enumerable set of fictitious voters vi1, vi2,... Thus the set V' of fictitious voters is infinite and we can have a non-principal ultrafilter F on it. We design the following voting system: for any given preference the vote of each vi is obtained and assigned to the associated fictitious voters vij; if the overall resulting set of fictitious voters supporting the preference is a forcing coalition according to F, the preference is approved, otherwise rejected.

We already know that this voting system cannot be fair, and in fact it is easy to uncover the underlying flaw: the range of our mapping f : VV' is not the entire powerset of V', but only a finite subset of it (with cardinality 2N); although F is non-principal, it becomes principal (streching somewhat the meaning of the concept) when restricted to range(f): F necessarily contains then a pseudodictatorial forcing coalition comprising exactly all the fictitious voters associated to a single vi, who is the resulting dictator for the so devised voting system.

## Sunday, November 16, 2008

### State semantics

The following is a proposal for the classification of types in an imperative language according to the way the state of their objects changes over time.

Immutable. Objects of an immutable type cannot change state during their lifetime.

Stateful. On the other side of the spectrum, an object of a stateful type publish some methods that cause the object's internal state to change when executed.

Bound. (For lack of a better name.) The state of an object `x` of a bound type remains immutable unless `x` is explicitly given the same state as some `y` through explicit assignment `x = y`. A very popular example of a bound type is `java.lang.String`. Although Java strings are commonly characterized as immutable, it is actually their associated states that are immutable, since an object of type `java.lang.String` can be rebound through assignment. In C++, bound semantics are approximated by pointers to constant objects—C++ references, on the other hand, do not have bound semantics since they cannot be reassigned, that is, rebound.

It turns out that bound types are sufficiently powerful to emulate stateful semantics using the following mapping technique: let `T` be a stateful type and an associated mutable method

`void T::f(args);`
We construct an associated bound type `BT` whose internal state is represented by values of `T`. We replace `T::f` with the following immutable method:
`‎BT BT::f(args)‎{‎  T state=this->state;‎  state.f(args);‎  return BT(state);‎} `
so that the expression
`‎T x;‎...‎x.f(args);`
can be rewritten with `BT` as
`‎BT x;‎...‎x=x.f(args);`
And similarly we can provide a stateful façade to a bound type: let `T` be a bound type with some method
`‎T T::f(args);`
We define a stateful type `ST` whose internal state is represented by values of `T`, and implement the associated method `f` as follows:
`‎void ST::f(args)‎{‎  this->state=this->state.f(args);‎}`
In summary, bound and stateful types are to some extent equivalent, though practical considerations might favor one kind over the other depending on the use context. For instance, bound types are more amenable to interning techniques and can be more easily equipped with locking mechanisms for use in multithreaded environments.

## Wednesday, November 12, 2008

### Gas price hysteresis

Due to the extreme rise of gas prices during the last couple of years, car users have become very sensitive (if not specially elastic) to the translation of oil price variations to retail gasoline prices. In particular, some have expressed the suspicion that increases in oil price are rapidly transferred to gas stations, whereas when the oil price decreases, this reflects less directly into a reduction of retail gas prices. Is this a case of actual price hysteresis or just consumer hysteria?

The figure shows the evolution of Brent prices and average retail prices of 95 octane gasoline and gasoil (diesel) in Spain, all in c€/l (source: Cores, via WonkaPistas).

The final price of a liter of gasoline or gasoil in Spain can be expressed as

final price = (1 + VAT) × (price before taxes + special tax),

where the applicable VAT is currently 16% and the special tax, known as the impuesto especial sobre hidrocarburos, is approximately fixed. So, the variations on this price do not depend on this special tax:

Δ(final price) = (1 + VAT) × Δ(price before taxes).

These variations can be then attributed to the volatile part of the product cost, the most important of which is oil price. This is how Δ(gasoline price before taxes) plots against Δ(Brent price) monthly between February 2007 and August 2008:

The dotted lines are the linear regressions of the points for Δ(Brent price) ≥ 0 and ≤ 0, respectively:

ΔBrent ≥ 0 → y = f+(x) = b+ + m+x = −0.5378 + 0.9885x,
ΔBrent ≤ 0 → y = f(x) = b + mx = 2.4610 + 1.4865x,

How can we interpret this? If the variations of gasoline price were symmetrical with respect to the sign of Δ(Brent price), we would have

f+(x) = −f(−x),
b+ = b,
m+ = m,

which is clearly not the case. In fact, we have that

f+(x) > −f(−x) for x in [0,3.86),

that is, variations in the price of the gasoline when 0 ≤ ΔBrent < 3.86 are larger than the corresponding reductions when − 3.86 < ΔBrent ≤ 0. In this interval, gasoline price can be said to present hysteresis unfavorable to the consumer. The situation is reversed when ΔBrent > 3.86, though this phenomenom is mainly accounted for by the presence of the outlier point at (−5.64,−5.41).

As for the variations on the price of gasoil before taxes, we have the following:

with regression lines

ΔBrent ≥ 0 → y = f+(x) = b+ + m+x = −0.7877 + 1.3841x,
ΔBrent ≤ 0 → y = f(x) = b + mx = 2.4676 + 1.6557x,

resunting in an user unfavorable hysteresis interval −6.19 < ΔBrent < 6.19, which spans the entire dataset.

In conclusion, only to some extent does the analysis corroborate the feeling many users share that oil companies do not reflect oil price reductions as faithfully as they do reflect increases. These results are not very trustworthy since negative variations of oil price are underrepresented. Given the recent drop in the international oil market, it will be interesting to repeat the calculations when the data for the last two months become available.

## Saturday, November 8, 2008

### Multiattribute querying with Boost.MultiIndex

We saw in a prior entry how to define database indexes on a set of columns so that all possible queries involving clauses of the form columni = valuei are accelerated by some index. We see now how to model this situation for an in-memory C++ container, which gives us the opportunity to use Boost.MultiIndex and show some template and preprocessor metaprogramming in action.

So, suppose we have the following struct:

`‎struct element‎{‎  int x1,x2,x3,x4;‎};`
and we are assigned the task of designing a container of `elements`s along with efficient querying functions of the form:
`‎typedef ... container;‎‎template<int N>‎struct field‎{‎  field(int x):x(x){}‎  int x;‎};‎‎template<int N0>‎const element* find(const container& c,const field<N0>& f0);‎‎...‎‎template<int N0,int N1,int N2,int N3>‎const element* find(‎  const container& c,‎  const field<N0>& f0,const field<N1>& f1,‎  const field<N2>& f2,const field<N3>& f2);`
so that operations like the following are possible:
`‎container c;‎...‎// x3==10 && x1==20‎find(c,field<3>(10),field<1>(20));‎‎// x1==5 && x4==40 && x2==11‎find(c,field<1>(5),field<4>(40),field<2>(11));`
Boost.MultiIndex is a natural choice to implement the container. As we already know, we need as many as six indices to cover all the possible variations:
`‎typedef member<element,int,&element::x1> key1;‎typedef member<element,int,&element::x2> key2;‎typedef member<element,int,&element::x3> key3;‎typedef member<element,int,&element::x4> key4;‎‎‎typedef multi_index_container<‎  element,‎  indexed_by<‎    ordered_non_unique<composite_key<element,key1,key3,key2,key4> >,‎    ordered_non_unique<composite_key<element,key4,key1,key3,key2> >,‎    ordered_non_unique<composite_key<element,key2,key1,key3,key4> >,‎    ordered_non_unique<composite_key<element,key4,key2,key1,key3> >,‎    ordered_non_unique<composite_key<element,key3,key2,key1,key4> >,‎    ordered_non_unique<composite_key<element,key4,key3,key2,key1> >‎  >‎> container;`

Actually, the combined composite keys are redundant, and we can shorten some of them. Also, we add a little instrumentation to the type for future use, so the final definition of `container` is:

`‎struct key1:member<element,int,&element::x1>,boost::mpl::int_<1>{};‎struct key2:member<element,int,&element::x2>,boost::mpl::int_<2>{};‎struct key3:member<element,int,&element::x3>,boost::mpl::int_<3>{};‎struct key4:member<element,int,&element::x4>,boost::mpl::int_<4>{};‎‎template<int>struct cover;‎‎typedef multi_index_container<‎  element,‎  indexed_by<‎    ordered_non_unique<‎      tag<cover<1>,cover<13>,cover<123>,cover<1234> >,‎      composite_key<element,key1,key3,key2,key4>‎    >,‎    ordered_non_unique<‎      tag<cover<4>,cover<14>,cover<134> >,‎      composite_key<element,key4,key1,key3>‎    >,‎    ordered_non_unique<‎      tag<cover<2>,cover<12> >,‎      composite_key<element,key2,key1>‎    >,‎    ordered_non_unique<‎      tag<cover<24>,cover<124> >,‎      composite_key<element,key4,key2,key1>‎    >,‎    ordered_non_unique<‎      tag<cover<3>,cover<23> >,‎      composite_key<element,key3,key2>‎    >,‎    ordered_non_unique<‎      tag<cover<34>,cover<234> >,‎      composite_key<element,key4,key3,key2>‎    >‎  >‎> container;`
The `keyn` extractor derives from `boost::mpl::int_<n>`, which makes these types easily indexable. As for the `cover` tags, they simply indicate the different query formulas supported by each index using a straightforward coding technique: for instance, the second index covers the querying formulas
`‎x4==v4 --> cover<4>‎x1==v1 && x4==v4 --> cover<14>‎x1==v1 && x3==v3 && x4==v4 --> cover<134>`
To avoid ambiguities, cover numbers are coded assuming the attribute names appear in the order `x1`, `x2`, `x3`, `x4`, even if the tagged index does not respect this order in the specification of the composite key; also, when two different types cover the same formula, we assign the tag to only one of them. So, there are a total of 15 different tags, exactly as many as the number of different query formulas with up to 4 attributes. `cover_number` does the metaprogrammatic work of calculating a cover number from an MPL sequence of `field<n>` types:
`‎template<typename FieldSequence>‎struct cover_number:‎  boost::mpl::fold<‎    typename boost::mpl::sort<FieldSequence>::type,‎    boost::mpl::int_<0>,‎    boost::mpl::plus<‎      boost::mpl::times<boost::mpl::_1,boost::mpl::int_<10> >,‎      boost::mpl::_2‎    >‎  >::type‎{};`
The following is a possible realization of the overload of `find` with three fields:
`‎template<int N0,int N1,int N2>‎const element* find(‎  const container& c,‎  const field<N0>& f0,const field<N1>& f1,const field<N2>& f2)‎{‎  // find the tag associated to the index conering our fields‎  typedef cover<‎    cover_number<‎      boost::mpl::vector_c<int,N0,N1,N2>‎    >::value‎  >                                                tag;‎‎  // retrieve the index type‎  typedef typename container::index<tag>::type     index_type;‎‎  // retrieve the type of the associated composite key extractor‎  typedef typename index_type::key_from_value      composite_key_type;‎‎  // an MPL sequence containing the field types passed‎  typedef boost::mpl::vector<‎    field<N0>,field<N1>,field<N2>‎  >                                                fields_type;‎‎  // get the index‎  const index_type&         i=c.get<tag>();‎‎  // pack the field values into a tuple...‎  boost::tuple<int,int,int> t=boost::make_tuple(f0.x,f1.x,f2.x);‎‎  // ...and use it with i.find(), rearranging the tuple‎  // so that each field<n> matches its key<n> in the composite key‎  typename index_type::iterator it=i.find(‎    boost::make_tuple(‎      get<composite_key_type,fields_type,boost::mpl::int_<0> >(t),‎      get<composite_key_type,fields_type,boost::mpl::int_<1> >(t),‎      get<composite_key_type,fields_type,boost::mpl::int_<2> >(t)‎    )‎  );‎  if(it!=i.end())return &*it;‎  else return 0;‎}`
The only missing part is the `get` template function, that accepts a composite key extractor type, an MPL sequence of fields, a position and a tuple of field values and returns the value associated to the `field<n>` with the same `n` as the `key<n>` at the indicated position in the composite key extractor:
`‎template<‎  typename CompositeKey,typename FieldSequence,‎  typename Pos,typename Tuple‎>‎int get(const Tuple& t)‎{‎  typedef typename boost::tuples::element<‎    Pos::value,‎    typename CompositeKey::key_extractor_tuple‎  >::type key_at_pos;‎  const int M=‎    boost::mpl::distance<‎      typename boost::mpl::begin<FieldSequence>::type,‎      typename boost::mpl::find<‎        FieldSequence,‎        field<key_at_pos::value>‎      >::type‎    >::value;‎  return t.template get<M>();‎}`

The code is simpler than it might appear at first glance: if the key at the position `Pos` of `CompositeKey` is of the form `key<n>`, `M` is simply the distance from the beginning of `FieldSequence` to the type `key<n>`. The expression `key_at_pos::value` takes advantage of the fact that each `key<n>` is derived from boost::mpl::int_`<n>`.

The different overloads of `find` are entirely similar to the one we have just seen. Boost.Preprocessor allows us to generate the overloads without code repetition:

`‎#define FIND_PARAM_MACRO(z,n,data) \‎const field<BOOST_PP_CAT(N,n)>& BOOST_PP_CAT(f,n)‎‎#define FIND_FIELD_MACRO(z,n,data) field<BOOST_PP_CAT(N,n)>‎‎#define FIND_VALUE_MACRO(z,n,data) BOOST_PP_CAT(f,n).x‎‎#define FIND_GET_MACRO(z,n,data) \‎get<composite_key_type,fields_type,boost::mpl::int_<n> >(t)‎‎#define DEFINE_FIND(num_fields) \‎template<BOOST_PP_ENUM_PARAMS(num_fields,int N)> \‎const element* find( \‎  const container& c, \‎  BOOST_PP_ENUM(num_fields,FIND_PARAM_MACRO,~)) \‎{ \‎  typedef cover< \‎    cover_number< \‎      boost::mpl::vector_c<int, \‎        BOOST_PP_ENUM_PARAMS(num_fields,N) \‎      > \‎    >::value \‎  >                                                tag; \‎  typedef typename container::index<tag>::type     index_type; \‎  typedef typename index_type::key_from_value      composite_key_type; \‎  typedef boost::mpl::vector< \‎    BOOST_PP_ENUM(num_fields,FIND_FIELD_MACRO,~) \‎  >                                                fields_type; \‎ \‎  const index_type& i=c.get<tag>(); \‎  boost::tuple< \‎    BOOST_PP_ENUM_PARAMS(num_fields,int BOOST_PP_INTERCEPT) \‎  > t=boost::make_tuple( \‎    BOOST_PP_ENUM(num_fields,FIND_VALUE_MACRO,~) \‎  ); \‎  typename index_type::iterator it=i.find( \‎    boost::make_tuple( \‎      BOOST_PP_ENUM(num_fields,FIND_GET_MACRO,~) \‎    ) \‎  ); \‎  if(it!=i.end())return &*it; \‎  else return 0; \‎}‎‎DEFINE_FIND(1)‎DEFINE_FIND(2)‎DEFINE_FIND(3)‎DEFINE_FIND(4)`
A complete implementation program is provided.

Although we have metaprogrammed the code for selecting and using the indices of an n-attribute container, still the definition of `container` was done manually. The following is a very tough challenge for the reader: program a metafunction that accepts an integer n and produces a suitable `multi_index_container` instantiation providing full query coverage for a struct with attributes `x1`,...,`xn`. Note that solving this challenge implies metaprogramming the permutation cover algorithm we devised some entries ago.

## Tuesday, November 4, 2008

### Filling up at dawn

I recently read in a free daily paper that it is advisable to fill up the car tank early in the morning rather than at noon because the gasoline will be usually cooler at that time of the day and thus denser, so we are pumping more grams of gas per liter paid. Does this really make a difference?

The volumetric thermal expansion coefficient of gasoline is 950·10-6/°C, which means that when the gasoline is colder we obtain an excess mass of

(mcold mhot)/mhot = 950·10-6ΔT.

For a rather large ΔT of 20 °C the gain would be around 2%. Take into account, however, that station tanks are buried a couple of meters underground, which damps the temperature oscillations experienced at the surface. This damping effect can be estimated as:

ΔT(z) = ΔTsurface·ez/D,
D = √(2K/ω),

where K is the soil thermal diffusivity, with typical values for natural soils ranging from 0.2 to 0.8 10-6m2/s. Setting z = 2 m and ω = 2π rad/day, we have

1.9·10-12ΔTsurface ≤ ΔTstation tank ≤ 1.4·10-6ΔTsurface,

that is, the temperature of the station tank is basically constant across the day. So, filling up the car tank in the cool hours of the day does not seem to make any difference.

There is a measurable gain, though, when we compare car tank filling during different seasons of the year. Here, the temperature oscillations are higher and, most importantly, the damping effect of the soil is much lesser. Taking

ΔTsurface = 30 °C,
z = 2 m,