Mass exhalation

How much bodily mass do we give out through breathing? The chemical reaction for aerobic respiration is

C₆H₁₂O₆ + 6O₂ → 6CO₂ + 6H₂O

The amount of carbon dioxide we exhale is then

6 mol CO₂ / mol glucose = 1.47 g CO₂ / g glucose.

Processing of fatty acids yields a different amount of exhaled CO₂. For instance, the oxidation of a saturated fatty acid is expressed as

C_nH_2nO₂ + (3n/2 − 1) O₂ → n CO₂ + n H₂O

yielding

44n/(14n + 32) g CO₂ / g C_nH_2nO₂.

This last expression also serves approximately for unsaturated fatty acids, since these are missing only a few lightweight hydrogen atoms with respect to the saturated acid with the same amount of carbon. Assuming most consumed fat is in the form of palmitate, we have a carbon dioxide yield of

2.75 g CO₂ / g fat;

Carbohydrates produce 4 kcal per gram, whereas fatty acid processing yields 9 kcal per gram of fat. While at rest, the human body takes 30% of the energy from carbohydrates and 70% from fat; so, this results in a combined production of carbon dioxide of

0.324 g CO₂ / kcal.

For a daily energy consumption rate around 2,500 kcal, 810 grams of carbon dioxide are then expelled through breathing. There is a experimental study by the USDA on the subject that unfortunately I haven't been able to find, but some sources cite it as reporting a value beween 445 and 450 liters of CO₂ (881-891 g) per day, which is in good agreement with our calculations.

The value calculated is not the answer to our original question about exhaled bodily mass: much of the oxygen in the CO₂ produced comes from the air rather than catabolized substances, specially in the case of fat. We will assume that all the oxygen coming from the burned substance goes to CO₂: under these conditions, the amount of bodily mass expelled through breathing is

0.933 g / g glucose,
0.875 g / g fat,

or, using the assumed ratios of carbohydrate and fat consumption,

0.138 g / kcal,

which yields 345 g for a typical daily energy consumption of 2,500 calories.

Generating permutation covers: part I

We investigate ways of efficiently generating minimal permutation covers for a set S of N elements. As we have already proved, such covers have size C(N,floor(N/2)). The following intermediate results reduce the problem to simpler terms.

Theorem. Assume that N is even and greater than zero. Let a be an an arbitrary element of S and Σ a minimal permutation cover of S − {a}. The set Σ' defined as

Σ' = {aσ, σa : σ in Σ}

is a minimal permutation cover of S.

Proof. Σ' is a permutation cover: let X be a subset of S; if a is not in X, X is covered by some permutation σ of Σ and a fortiori by σa in Σ'; if a belongs to X, some σ in Σ covers X − {a} and then aσ in Σ' covers X. Σ' is minimal as |Σ'| = 2|Σ| = 2 C(N − 1, floor((N − 1)/2)) = 2 C(N − 1, N/2 − 1) = C(N,N/2) = C(N,floor(N/2)), where the equalities depend on basic properties of binomial coefficients and the fact that N is even.

This result reduces the problem to N odd. The Hasse diagram of the powerset of S when N is odd looks like this (the particular case depicted is N = 5):

We name the layers of the diagram S₀,...,S_N. S_i consists of the subsets of S with cardinality i. We have |S_i| = C(N,i). A permutation covers exactly one element of each S_i. Similarly, a tuple τ of n non-repeating elements covers exactly one element of each of S₀,...,S_n. So, a minimal tuple cover of S₀,...,S_n can be proved to have as many elements as the largest layer covered. The next result shows how to extend a minimal tuple cover of S₀,...,S_{(N − 1)/2} , which has cardinality C(N,(N − 1)/2) = C(N,floor(N/2)) and spreads over the bottom half of the powerset of S, to a minimal permutation cover of S.

Theorem. Assume that N is odd and set M = (N − 1)/2. Let Τ be a minimal set of M-tuples of non-repeating elements covering S₀ U ... U S_M, and d : S_M → S_M a bijection with X ∩ d(X) = Ø for all X in S_M. The set Σ defined as

Σ = { τ·a·reverse(τ') : τ,τ' belong to Τ, range(τ') = d(range(τ)), a = S − range(τ) − range(τ')}

is a minimal permutation cover of S.

Proof. We see first that to each τ in Τ there corresponds exactly one permutation σ_τ of the form τ·a·reverse(τ') described above: since Τ is minimal each element of S_M is covered by one and only one element of Τ; so, for each τ there is exactly one τ' covering d(range(τ)). We prove now that Σ covers S: let X be a subset of S; if |X| ≤ M, X is covered by some τ in Τ and hence also by the associated σ_τ; if |X| > M, the set Y = S − X has |Y| ≤ M and is thus covered by some τ' in Τ; as we have seen, τ' univocally determines a permutation σ = τ·a·reverse(τ'), and σ obviously covers X, as all the elements of Y are packed at the tail of the permutation. Finally, Σ is minimal, since |Σ|= |Τ| and we saw before that |Τ| = C(N,floor(N/2)).

The mapping τ → σ_τ just defined can be described in a more algorithmic fashion as follows:

1. Find the τ' in Τ covering d(range(τ)).
2. Let a be the only element of S not present in τ nor τ'.
3. σ_τ := τ·a·reverse(τ').

Note that the last theorem extends easily to N even: in this case, the permutations have the form τ·reverse(τ'), i.e. there is no middle element a. However, it is more efficient to reduce the case N even to N − 1 using the first theorem of this entry.

Now we are left with the tasks of designing an algorithm to generate a tuple set Τ covering S₀ U ... U S_M and finding a suitable bijection d : S_M → S_M.

Profiling stable_vector

The two random access containers of the C++ standard library, std::vector and std::deque, have the same big-O complexity as stable_vector for the following operations:

• push_back: amortized constant
• middle insert: O(n)
• operator[]: constant

Yet the differences in actual performance vary wildly. I have written a profile program that measures the time taken by the three containers at these operations for two different value types: int and a "heavy" user defined type bigobj holding an int and an std::string. The program was built with release mode settings with MSVC++ 8.0 and GNU GCC 3.4.4 for Cygwin/MinGW. Resulting times are summarized in the following table: values are normalized to the minimum among the three containers.

MSVC++ 8.0
	int			bigobj
	std:: vector	std:: deque	stable_ vector	std:: vector	std:: deque	stable_ vector
push_back	1.00	4.06	21.37	1.00	1.09	1.26
insert	1.00	4.24	5.29	1.50	1.73	1.00
operator[]	1.00	3.35	1.01	1.00	3.27	1.09
GNU GCC 3.4.4
	int			bigobj
	std:: vector	std:: deque	stable_ vector	std:: vector	std:: deque	stable_ vector
push_back	1.09	1.00	91.57	1.08	1.00	1.14
insert	1.00	1.30	5.17	21.38	21.36	1.00
operator[]	1.00	41.04	1.11	1.00	81.68	2.03

For small objects like int, std::vector is, as expected, the fastest or very close to the fastest at every operation. push_back takes much longer for stable_vector than std::deque presumably because the latter allocates element chunks thus amortizing allocation time whereas stable_vector performs an allocation for every new node. The poor performance of stable_vector at insert can be attributed to the operation of adjustment of "up" pointers with each insertion operation, which is considerably slower than the simple int copying incurred by the other two containers. Finally, note that random access is very slow for std::deque because it involves some non-trivial arithmetical calculations, whereas std::vector and stable_vector only perform simple pointer offsets and indirections.

When storing heavy objects with expensive copy, the situation changes somewhat. The fact that stable_vector does not internally copy elements upon resizing or shrinking improves its relative performance with respect to the other two containers at push_back, and specially at insert, where stable_vector is the fastest.

This basic analysis suggests that the main performance handicap of stable_vector stems from the fact that it is a node-based container, as opposed to the chunk-based nature of std::vector and std::deque. This drawback might be alleviated by the use of burst-allocation, as proposed by Ion Gaztañaga.

Too powerful to evolve

Paragraph 1.4.8 of the C++ standard (draft copy) states that

A conforming implementation may have extensions (including additional library functions), provided they do not alter the behavior of any well-formed program.

It turns out that, strictly speaking, this unexpectedly bans many possible extensions an implementation of the C++ standard library might provide; C++ is such a powerful beast that a well-formed program might be made to depend on the non-existence of certain entities.

Function and function templates. The following program

‎#include <algorithm>
‎
‎using namespace std;
‎
‎int any_of(int count,int n1,...){/*...*/}
‎
‎int main()
‎{
‎  int n=any_of(2,1023,233);
‎}
‎

is valid C++03, but will fail with the upcoming C++0x revision of the standard, as this includes a function template any_of within <algorithm>:

‎template <class InputIterator, class Predicate>
‎bool any_of(InputIterator first, InputIterator last, Predicate pred);

that takes precedence over the user defined any_of due to the using namespace std directive.

Classes and class templates. Similarly, this C++03 valid program

‎#include <functional>
‎
‎using namespace std;
‎
‎template<typename T>
‎struct hash
‎{
‎  size_t operator()(const T& t){/*...*/}
‎};
‎
‎int main()
‎{
‎  hash<int>   h;
‎  size_t s=h(983265);
‎}
‎

will fail with C++0x due to the presence of an homonym hash in <functional>.

Member functions. The previous situations can be avoided if non-standard extensions are declared in separate headers or belong to a namespace other than std. These measures cannot be taken, however, when we are adding members to a standard class. The following is a totally artificial yet valid C++03 program:

‎#include <vector>
‎
‎template<class Vector>
‎int foo(char x){/*...*/}
‎
‎template <typename T,void (T::*)()> struct mfp{};
‎
‎template<class Vector>
‎void* foo(int x,mfp<Vector,&Vector::shrink_to_fit>* =0){/*...*/}
‎
‎int main()
‎{
‎  int x=foo<std::vector<int> >(0);
‎}

The so-called SFINAE rule prevents the second overload of foo to be selected because vector has no member function called shrink_to_fit; but it does in C++0x, rendering the program invalid (the second foo return type is not convertible to int).

Of course this is not a serious objection to the C++ standard text: 1.4.8 could always be rephrased to restrict it to reasonable well-formed programs, for some definition of "reasonable". But it can be instructive to reflect on how C++ has become so powerful (some would say complex) that such devious tricks can emerge (and, in some cases, be benefited from).

A causality calculus

Let us design a first-order calculus including causality as non-truth-functional connective for which causality semantics is defined at the same level as the rest of the (truth-functional) connectives, according to the philosophical position stated in a previous entry. We assume we are given an infinite set of variables V and a set R of predicate symbols with associated arities.

Propositional constants: F (falsehood).

Connectives: → (only if), > (causal implication).

Quantifiers: V (for all).

Axioms and rules of inference: the usual ones for standard first-order calculus plus the following axiom schemas dealing with causality:

(C₁) p > q, q > r → p > r

(C₂) (p > p) → F

(C₃) p > q → (p and q)

(C₄) p > r → (p or q) > r

(C₅) p > (q and r) → p > q

These axioms deserve some comment: C₁ states the usual transitivity of causation, while C₂ says that no event causes itself; C₃ allows us to speak about causation only among events actually taking place, which makes this a "realist" semantics. C₄ and C₅ translate some usual properties of material implication to causal implication.

Semantics: a valuation v specifies several mappings:

• From V to some set U.
• From each n-ary predicate in R to some n-ary relation in U.
• From each formula to the set {F,T}.

and obeys the following rules:

• v(F) = F.
• v(φ → ψ) = T iff v(φ) = F or v(ψ) = T.
• v(R(t₁,...,t_n)) = T iff (v(t₁),...,v(t_n)) is in v(R).
• v(Vx φ) = T iff v'(φ) = T for every valuation v' identical to v except possibly at x.
• The relation on formulas of the calculus defined by v(φ > ψ) = T is consistent with axiom schemas C₁,..., C₅. In particular, this implies that the relation thus defined is a strict partial order.
  

As usual, a statement is valid if it is true for any valuation. It is easy to see that there are valuations with the properties described above: just take any valuation for standard first-order predicate calculus and augment it with v(φ > ψ) = F for all φ, ψ (we may call this a Humean valuation).

Introducing stable_vector

We present stable_vector, a fully STL-compliant stable container that provides most of the features of std::vector except element contiguity. The underlying data structure has been discussed in a prior entry.

• stable_vector.hpp. The code uses Boost.
• test_stable_vector.cpp: Test suite for stable_vector.
  

In the following we are using the terminology of the C++98 standard.

General properties. stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in std::vector. Like std::vector, iterators are random access. stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a stable_vector remain valid as long as the element is not erased, and an iterator that has been assigned the return value of end() always remain valid until the destruction of the associated stable_vector.

Operation complexity. The big-O complexities of stable_vector operations match exactly those of std::vector. In general, insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector does not internally perform any value_type destruction, copy or assignment operations other than those exactly corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of performance for the extra burden of doing more pointer manipulation and an additional allocation per element.

Exception safety. (according to Abrahams' terminology) As stable_vector does not internally copy elements around, some operations provide stronger exception safety guarantees than in std::vector:

operation	exception safety for std::vector<T>	exception safety for stable_vector<T>
insert	strong unless copy or assignment of T throw (basic)	strong
erase	no-throw unless copy or assignment of T throw (basic)	no-throw

Memory overhead. The C++ standard does not specifiy requirements on memory consumption, but virtually any implementation of std::vector has the same behavior wih respect to memory usage: the memory allocated by a vector v with n elements of type T is

m_v = c·e,

where c is v.capacity() and e is sizeof(T). c can be as low as n if the user has explicitly reserved the exact capacity required; otherwise, the average value c for a growing vector oscillates between 1.25·n and 1.5·n for typical resizing policies. For stable_vector, the memory usage is

m_sv = (c + 1)p + (n + 1)(e + p),

where p is the size of a pointer. We have c + 1 and n + 1 rather than c and n because a dummy node is needed at the end of the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that

m_sv/m_v ≈ (fp + e + p)/fe.

So, stable_vector uses less memory than std::vector only when e > p and the capacity to size ratio exceeds a given threshold:

m_sv < m_v ↔ f > (e + p)/(e − p). (provided e > p)

This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.

Summary. stable_vector is a drop-in replacement for std::vector providing stability of references and iterators, in exchange for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to move around, the performance overhead can turn into a net performance gain for stable_vector if many middle insertions or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when the memory used by stable_vector can actually be less than required by std::vector.

Causality as a primitive concept

The supposedly metaphysical nature of causality, according to such radical empiricists as Hume, stems from the fact that there cannot be a direct perception of a causal connection between events: perception of causes and effects is indistinguishable from perception of unrelated events that happen to be contiguous in space and time. This non-commitmental position is, however, untenable, as causality is absolutely central to any theory admitting the existence of an objective world: it is only by postulating a cause-effect relation between external events and our internal perceptions of them that we can escape solipsism.

It is my take then that causality, at least within the context of the human perception of events, can be seen as a primitive concept at the same level as event occurrence; saying "A causes B" is as basic a statement as "It is the case that C", because causality can only be explained in terms of event occurrence, and any account of an event occurrence depends on the implied causality connecting events and their perception. Formal renditions of causality, however, propose modal-like semantics denying this concept its primitiveness, which adds to the methaphysical aura sourrounding the subject: while the truth or falsity of a statement in a logical calculus is directly represented by the models of the calculus (cf. first-order predicate calculus semantics), causality semantics rely on more complex structures (vg. possible worlds) that build on "basic" models.

What would a formalization look like in which the truth of a statement and the causal connection between two statements are modeled at the same basic level? We will explore this approach in a later entry.

A combinatory theorem

Definition. Let S be a finite set of cardinality N, σ = (σ₁,...,σ_N) a permutation of the elements of S and X a subset of S. We say the σ prefix-covers (or simply covers) X if X is one of Ø, {σ₁}, {σ₁,σ₂}, ... , {σ₁,...,σ_M}.

For instance, if S = {a,b,c,d} and σ = (b,d,a,c), the following subsets of S are covered by σ: Ø, {b}, {b,d}, {a,b,d}, {a,b,c,d} = S.

In the following we use the notation C(a,b) for the binomial coefficient a choose b.

Theorem. C(N,floor(N/2)) is the minimum number of distinct permutations of S jointly covering all the subsets of S.

Proof. Let P be the power set of S partially ordered by inclusion. The sets covered by a permutation of S form a maximal chain of P, and this correspondence between permutations and maximal chains is clearly one-to-one. So, the minimum number of permutations of S required to cover S is the same as the minimum number of chains partitioning P. By Dilworth's Theorem, this number is equal to the partial order width of P, that Sperner's Theorem shows to be C(N,floor(N/2)).

The first values of C(n,floor(n/2)) are: 1, 1, 2, 3, 6, 10, 20, 35, 70, 126... The following table shows some possible permutation covers for |S| = 1,...,5.

S	permutation cover
{a}	(a)
{a,b}	(ab), (ba)
{a,b,c}	(abc), (bca), (cab)
{a,b,c,d}	(abcd), (acbd), (bcda), (bdac), (cdab), (dabc)
{a,b,c,d,e}	(abcde), (bcdea), (cdeab), (deabc), (eabcd), (acdbe), (adbce), (bdeac), (becad), (ceabd)

The proof of the theorem does not provide an efficient algorithm to construct a permutation cover. Finding such an algorithm is an interesting problem that we will address in a later entry.