10_binary_counter.html

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<title>10. Balanced binary reduction</title>
<link rel="stylesheet" href="template/style.css">
</head>
<body>


<span style="float: right">
[
<a href="09_iterators.html">previous</a>, 
<a href="index.html">contents</a>, 
<a href="11_min_1_2.html">next</a>
]
</span>


<a name="L10.-Balanced-binary-reduction"></a>
<h1>10. Balanced binary reduction</h1>

<a name="Alice-in-wonderland"></a>
<h2>Alice in wonderland</h2>

<p>Let us introduce the problem of finding not just the smallest
of <code>n</code> elements, but the smallest and second smallest.
The problem has a very distinguished pedigree, it was first addressed by a well-known British mathematician
<a href="https://en.wikipedia.org/wiki/Lewis_Carroll">Charles Dodgson</a> (Lewis Carroll).
If you haven&rsquo;t heard of him, you should.
There is a very important book which he wrote, not the <a href="https://www.gutenberg.org/ebooks/28696">mathematical book</a>,
but the book called <a href="https://en.wikipedia.org/wiki/Alice%27s_Adventures_in_Wonderland">&ldquo;Alice&rsquo;s Adventures in Wonderland&rdquo;</a>.
If you haven&rsquo;t read it, do<sup id="fnref:1"><a href="#fn:1" rel="footnote">1</a></sup>.
No person should be hired ever unless they read &ldquo;Alice in Wonderland&rdquo;.
In any case, he was also a mathematician.
He also dabbled in all kind of games.
Apparently he invented Scrabble and a bunch of other games<sup id="fnref:2"><a href="#fn:2" rel="footnote">2</a></sup>.</p>

<p>At some point he decided that there is a clear problem with lawn tennis tournaments.
He observed that with a very high probability,
if you have say a tournament with 64
players, the guy who gets the second prize is actually not the second strongest.
He observed that the strongest and
second strongest could be paired in the first round.
Therefore the second strongest guy gets eliminated and doesn&rsquo;t get the second prize,
in spite of his prowess.
This is why they now use a technique known as <a href="https://en.wikipedia.org/wiki/Seed_(sports)">seeding</a> to assure
that people of similar ability are spread out to different parts of the tree.
But he wanted to come up with an algorithm
which assures that the second-placed guy is truly the second best player.
He published it in 1883<sup id="fnref:3"><a href="#fn:3" rel="footnote">3</a></sup>.
The algorithm wasn&rsquo;t quite an algorithm<sup id="fnref:4"><a href="#fn:4" rel="footnote">4</a></sup> and it was clearly not optimal.
It took 50 more years before the problem was stated correctly.
People realized that you could talk about the minimum
number of comparisons but it took another thirty years, until 1964 when a
Russian mathematician <a href="http://www.mathnet.ru/eng/person27000">Sergei S. Kislitsyn</a> published a paper which
proved there is an optimal algorithm and described it.</p>

<p>By the way, all of this information is available in a
book called <a href="https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming">&ldquo;The Art of Computer Programming&rdquo;</a> by <a href="https://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</a><sup id="fnref:5"><a href="#fn:5" rel="footnote">5</a></sup>.
You really should buy it.
You make a certain commitment.
You spend $150 saying that you really care about programming.
This is not a book which is &ldquo;useful&rdquo;, meaning it&rsquo;s not &ldquo;programming in Python for idiots&rdquo;,
or &ldquo;information retrieval for 21st century&rdquo; or something like that.
This is one of the fundamental books which you buy and then spend your
lifetime getting the information out of it.
You get beautiful things which you then could use for programming in Python or information retrieval or other things.
I&rsquo;m going to be mentioning Knuth throughout the course.
It&rsquo;s not a perfect book, it is just the greatest book we&rsquo;ve got.
Some people think it&rsquo;s a good reference book.
No, it&rsquo;s not, because you have to
basically do linear search to find what you&rsquo;re interested in.
Another important thing; do not spend too much time solving problems.
Read the solutions.
They are right at the end.
Lots of very important algorithms are described in the solutions to his problems.
Reading Knuth has to become a lifelong activity.</p>

<a name="Smallest-and-second-smallest-element"></a>
<h2>Smallest and second smallest element</h2>

<p>The problem of finding the smallest and second smallest element
is described fully in &ldquo;The Art of Computer Programming&rdquo;, but somehow Knuth does not implement it.
As we shall see it&rsquo;s actually a little tricky.</p>

<p>How many comparisons do you need to solve this problem?
Same as <code>minmax_element</code> from last time?
No.
You can do it in fewer.
Let us try to use some logic.
How many comparisons do we need to find the winner of the tournament? <code>n - 1</code>
because it is necessary to find the winner in order to find the second place guy.
We could sketch a proof of this.
Let us assume there are two potential guys greater than the second place guy.
If neither are greater than him, he is first place, not second place.
If both of them are, he isn&rsquo;t second place.</p>

<p>What do we know about the second place guy, specifically about the games he lost?
<em>He only lost one game, and it was to the winner</em>.
This is a very important property which tells us why we don&rsquo;t need to do many comparisons.
If the winner remembers all the games he won, and who he played how do we find second place?
We determine the best from the subset of players he beat.</p>

<p>How many people does the winner beat to win?
For example, <a href="https://en.wikipedia.org/wiki/The_Championships,_Wimbledon">Wimbledon</a> has 64 players who are admitted.
The winner doesn&rsquo;t play 63 games.
The tournament is structured as a <a href="https://en.wikipedia.org/wiki/Binary_tree">binary tree</a>.
This tree is how deep?
If you have <code>n</code> elements? It&rsquo;s <code>ceil(log_2(n))</code>.
We could somehow arrange our tournament so that the
winner will defeat this many people.</p>

<pre><code> winner: d
 second place: a or c

     d 
    /  \
   a    d
  /\    /\
 /  \  /  \
a   b c    d    ceil(log_2(4)) = 2
</code></pre>

<p>Now that we have a list of the <code>ceil(log_2(n))</code> people who played the winner,
we just find the best out of them which is <code>ceil(log_2(n)) - 1</code> comparisons.</p>

<p>To review, we have <code>n - 1</code> comparisons to get the winner.
<code>ceil(log_2(n)) - 1</code> to get the second best, from the list he played.
So an upper bound on the comparisons for the algorithm is:</p>

<pre><code>n + ceil(log_2(n)) - 2
</code></pre>

<p>Actually implementing this algorithm effectively
will require us to create several components.</p>

<a name="What-about-divide-and-conquer-3f-"></a>
<h3>What about divide and conquer?</h3>

<p>It might appear you could use divide and conquer.
First split the list of elements in two,
find the min and second min of the first half,
and the second half, and then merge them together doing two comparisons.
It sounds very elegant because it&rsquo;s all recursive.
But, let us think about how many comparisons it&rsquo;s going to do
using simple mathematics.</p>

<ol>
<li><p>We start with <code>n</code>. We need to pair and compare them,
so the first round is <code>n/2</code> comparisons.</p></li>
<li><p>In the second round we pair up the results,
so we need <code>n/4</code> &ldquo;games&rdquo;.
But, each game requires two comparisons (to find min and max).
So we have another <code>n/2</code> comparisons.</p></li>
<li><p>And so on&hellip;</p></li>
</ol>


<p>So the total number of comparisons would be:</p>

<pre><code>  n/2 + (n/2 + n/4 + n/8 + ...)
= n/2 + n-1
= 3n/2 - 1
</code></pre>

<p>That&rsquo;s not what we&rsquo;re trying to accomplish, so divide and conquer doesn&rsquo;t always do what we think.</p>

<a name="Tournament-tree-shapes"></a>
<h3>Tournament tree shapes</h3>

<p>To get the number of comparisons that we want, we need to rearrange the tournament we play.
Right now <code>min_element</code> plays a tree structure that looks like this:</p>

<pre><code>unbalanced tree

/\
  /\
    /\
      ... 
       /\
</code></pre>

<p>It has <code>n - 1</code> internal nodes.
But we don&rsquo;t want the winning element to be compared <code>n - 1</code> times.
We need to transform that into the way they play tennis tournaments.
We need to balance the tree.</p>

<pre><code>balanced tree

    / \
   /\ /\
    ...
  /\ /\ /\
</code></pre>

<p>How do we do it?
One way is to just pair up elements and build up.
But then we need lots of memory to save the intermediate results<sup id="fnref:6"><a href="#fn:6" rel="footnote">6</a></sup>.
Note that once a bottom-level round has been played, they are ready to move up.
Our goal is basically to become eager.
Whenever elements are ready to be paired together, we want to pair and compare them.</p>

<p>So if we store only the winner at each level, we only need to store <code>log(n)</code> things.
We can define the <strong>power</strong> of each element
to be the number of games they have played.</p>

<p>Realize that suddenly we see something which has nothing to do with our problem.
<em>The foundation of our algorithm is the ability to take a tree, like
the linear (unbalanced) tree, and transform it into a balanced tree</em>.
What mathematical property allows us to do such a transformation?
Why can we convert one kind of computation to the other?
<strong>Associativity</strong><sup id="fnref:7"><a href="#fn:7" rel="footnote">7</a></sup>.
As long as our operation is associative,
what property don&rsquo;t we need? <strong>Commutativity</strong><sup id="fnref:8"><a href="#fn:8" rel="footnote">8</a></sup>.
We keep the elements in the same order,
we&rsquo;re just rebalancing parentheses<sup id="fnref:9"><a href="#fn:9" rel="footnote">9</a></sup>.</p>

<a name="Binary-counting-and-reduction"></a>
<h2>Binary counting and reduction</h2>

<p>Here we come to the amazing idea of how to do this transformation.
This is one of the most beautiful ideas which they kept secret from you.
They should have taught it in high school.
But, they want to publish papers themselves and not tell you the general mechanism.</p>

<p>Let us assume we have elements of type <code>T</code> that need to be paired or combined in some way,
whether with <code>min</code>, <code>+</code>, <code>merge</code>, or any other assocative operation on <code>T</code>.
What we can do is create an array called a &ldquo;counter&rdquo;.</p>

<pre><code>   index: 0  1  ...   31
contents: x1 x2  ...  x32
</code></pre>

<p>The <code>nth</code> slot of the counter will store the element that has had <code>n</code> &ldquo;victories&rdquo; so far.
So if there is a guy in slot 0 he hasn&rsquo;t played any games yet.
If there is a guy in slot 2 he has won 2 games, and so on.
This structure will help us to only pair up elements that have the same power.</p>

<p>The following example using <code>min</code> as the operation should make this clear.
Initially the counter has zero in every entry:</p>

<pre><code>initial counter

   index: 0 1  ...   31
contents: 0 0  ...   0
</code></pre>

<p>Take a new guy <code>x</code> who has never played any games,
and look at the guy in the first slot of the counter.
The existing guy is either zero or not.
If it&rsquo;s zero, put the new guy <code>x</code> in the counter at index <code>0</code> (he has not played any games).</p>

<pre><code>0 1  ...   31           0 1  ...   31
0 0  ...   0     --&gt;    x 0  ...   0
</code></pre>

<p>Now take another guy <code>y</code>. Since <code>x</code> is in the first slot of the counter, we must pair them up.
The winner moves on up to the next slot in the counter,
as they have now won a game.
So if <code>y</code> wins:</p>

<pre><code>0 1  ...   31           0 1  ...   31
x 0  ...   0     --&gt;    0 y  ...   0
</code></pre>

<p>Otherwise <code>x</code> wins:</p>

<pre><code>0 1  ...   31           0 1  ...   31
x 0  ...   0     --&gt;    0 x  ...   0
</code></pre>

<p>What if the index <code>1</code> slot was non-zero, after comparing <code>x</code> and <code>y</code>?
Then the guy there already won one game.
So, we must <strong>carry propogate</strong><sup id="fnref:10"><a href="#fn:10" rel="footnote">10</a></sup>.
Repeat the same process all the way up the counter, until we find a slot which is zero.
What if the counter is full, and has no zero slots?
That&rsquo;s called an <strong>overflow</strong>.</p>

<p>We borrow terminology from binary integer arithemtic because
our counter works just like a binary integer counting up:</p>

<pre><code>0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1
</code></pre>

<p>But instead of 0 and 1 in each slot or &ldquo;bit&rdquo; we have arbitary elements that are combined with an associative operation.</p>

<a name="Handling-overflow"></a>
<h3>Handling overflow</h3>

<p>What do we do if the counter overflows?
Whenever we don&rsquo;t know how to proceed,
do something sensible and let whomever uses it figure out what is a sensible thing to do.
Return the carry.
If the return is non-zero the programmer who called the counter will know
it overflowed and can decide what to do.
Maybe they will extend the counter or throw an error.
It&rsquo;s his business not ours.</p>

<p>Let us be lazy.
The great success in programming comes because there are lazy people who say,
&ldquo;I don&rsquo;t want to know now,
I&rsquo;ll find out later.&rdquo;
Right now we are solving this problem.
We have an associative binary operation of some kind
on type <code>T</code> and what we discovered is if we have associativity,
we can make this counter and it will work for us.</p>

<a name="Implementation"></a>
<h3>Implementation</h3>

<p>Now we have to write the code.
The first function will add an element to the counter
using the process we just described.</p>

<pre><code>template &lt;typename T, typename I, typename Op&gt;
// requires Op is BinaryOperation(T)
// and Op is associative 
// and I is ForwardIterator and ValueType(I) == T
T add_to_counter(I first, I last, Op op, const T&amp; zero, T carry) {
    // precondition: carry != zero
    while (first != last) {
        if (*first == zero) {
            *first = carry;
            return zero;
        }
        carry = op(*first, carry);
        *first = zero;
        ++first;
    }
    return carry;
}
</code></pre>

<p><code>op</code> is not commutative, so we need to be careful about the order
it is evaluated in.
Elements in the counter got there before, so they were to the left of the
element we are inserting.</p>

<p>Notice that zero is <code>const T&amp;</code> reference because we don&rsquo;t plan to modify it,
but we do modify carry,
so it should be passed by value.</p>

<a name="Reduction"></a>
<h3>Reduction</h3>

<p>After we finish adding all our elements to the counter, they might not all be reduced to one element.
There may be several elements left sitting at various levels of the counter.
We need to do one more pass of the operation to combine them into the final result.</p>

<p>This second function does that. It applies the operation,
in the same manner to the elements left sitting in the counter.</p>

<pre><code>template &lt;typename T, typename I, typename Op&gt;
// requires Op is BinaryOperation(T)
// and Op is associative 
// and I is ForwardIterator and ValueType(I) == T
T reduce_counter(I first, I last, Op op, const T&amp; zero) {
    while (first != last &amp;&amp; *first == zero) {
        ++first;
    }
    if (first == last) return zero;

    T result = *first;
    while (++first != last) {
        if (*first != zero) {
            result = op(*first, result);
        }
    }
    return result;
}
</code></pre>

<p>We have to be careful with zero.
Sometimes it will work with the operation so apply <code>op(x, zero)</code>
gives you <code>x</code>, but sometimes that won&rsquo;t happen.
So we can&rsquo;t really initialize to zero.</p>

<a name="Binary-counter-class"></a>
<h2>Binary counter class</h2>

<a name="Start-with-algorithms"></a>
<h3>Start with algorithms</h3>

<p>We want to take
these two algorithms and combine them into an object.
We have two beautiful algorithms but they&rsquo;re stateless.
Everything is outside, and this is what we should always do,
no matter what we have been taught in software engineering classes by very wise
object-oriented professors.
You start with algorithms.
You don&rsquo;t start with objects.
Figure out what you&rsquo;re going to do first.
But you don&rsquo;t have to stop there.
Because you can then put things together into an object.</p>

<p>It&rsquo;s very easy when you write an algorithm to have a minimal iterator interface.
In this case, the iterators externalize the counter.
We say, &ldquo;we don&rsquo;t want to know about him,
we&rsquo;re just algorithms people&rdquo;.
We assume the principle that we will have no state for about
five minutes, and stay very functional, but then
turn around and deal with state.
We look at the whole thing.</p>

<a name="Counter-storage"></a>
<h3>Counter storage</h3>

<p>So what do we think is the state of this counter?
How should we store the counter?
Don&rsquo;t we have millions of elements to reduce?
The counter is size <code>log(n)</code> which will
never be greater than <code>64</code>.
So, it&rsquo;s actually a small fixed size.
We will store it in a <code>std::vector</code>.</p>

<pre><code>template &lt;typename Op, typename T = typename Op::argument_type&gt;
class binary_counter
{
private:
  std::vector&lt;T&gt; counter;
  Op op;
  T zero;

public:
  binary_counter(const Op&amp; op, const T&amp; zero) :
    op(op), zero(zero) {}

  void reserve(size_t n) { counter.reserve(n); }

  void add(T x) {
    x = add_to_counter(counter.begin(), counter.end(), op, zero, x);
    if (x != zero) counter.push_back(x);
  }

  // returns: value of the counter
  T reduce() {
    return reduce_counter(counter.begin(), counter.end(), op, zero);
  }
};
</code></pre>

<p><code>counter</code> is private, we don&rsquo;t
want people to muck up our counter.
Same with our operation.</p>

<p>Using initializer lists instead of assignment in constructor is important.
If you initialize in the body, it will first call default constructors
for members, then you overwrite all the work with an assignment.</p>

<p>I think it is very beautiful.
We could compete with Steve Jobs for elegance of our design<sup id="fnref:11"><a href="#fn:11" rel="footnote">11</a></sup>.</p>

<p><strong>Exercise:</strong> In <a href="https://en.wikipedia.org/wiki/Numerical_analysis">numerical analysis</a>,
    whenever you sum up large number you don&rsquo;t really want to
    add small quantities to big quantities.
    Bad things happen to the errors<sup id="fnref:12"><a href="#fn:12" rel="footnote">12</a></sup>.
    Use this code to write a function which sums arrays of <code>double</code>.</p>

<p><strong>Exercise:</strong> Rewrite <code>min_element</code> using this code (just <code>min_element</code>, don&rsquo;t worry about second best).</p>

<p><strong>Exercise:</strong>  If you want to implement <a href="https://en.wikipedia.org/wiki/Merge_sort">merge sort</a> you can use exactly the same device, since merge is associative. The idea with merge sort, is you only want to merge lists if they are roughly the same length and this helps you do it (see Chapter 12).
    Write the associtative binary operation <code>merge</code> which can combine two sorted arrays into a sorted array.</p>

<p><strong>Exercise:</strong> When we become grownups we learn about advanced data structures, such as <a href="https://en.wikipedia.org/wiki/Binomial_heap">binomial forest</a>. They use the same idea. Learn about this data structure and try to figure out where
    the counter could be used.</p>

<a name="What-is-in-2d-place-memory-usage-3f-"></a>
<h3>What is in-place memory usage?</h3>

<p>How significant is the storage of our counter?
We use the term <a href="https://en.wikipedia.org/wiki/In-place_algorithm"><strong>in-place</strong></a> to indicate the memory
usage of an algorithm is not significant.
A long time ago people thought
algorithms were in-place if they didn&rsquo;t require any extra memory.
Then they decided constant memory was enough.
But, then they said it doesn&rsquo;t quite work because our favorite algorithm
doesn&rsquo;t work. Of course the most important algorithm is <a href="https://en.wikipedia.org/wiki/Quicksort">quicksort</a>.
It&rsquo;s not in-place because it&rsquo;s recursive.
Recursive algorithms tend to require <code>O(log(n))</code>.
Quicksort splits roughly in the middle let&rsquo;s assume on average.</p>

<p>So people say <code>log(n)</code> is good so that will count as in-place.
Then they said, &ldquo;what if we have nested things?&rdquo;
So is <code>log(n)^2</code> ok?
In our universe <code>log(n) &lt;= 64</code> so this is 4096.
Then theoreticians said it&rsquo;s really alright if we have &ldquo;poly-logarithmic&rdquo; storage
Basically as long as the memory requirement is <code>O(p(log(n)))</code>
where <code>p</code> is a polynomial, it&rsquo;s alright.
Polynomials get a lot bigger than square,
but let&rsquo;s go with &ldquo;poly-logarithmic&rdquo; being &ldquo;in-place&rdquo;.</p>

<a name="Code"></a>
<h2>Code</h2>

<ul>
<li><a href="code/binary_counter.h">binary_counter.h</a></li>
<li><a href="code/test_binary_counter.cpp">test_binary_counter.cpp</a></li>
</ul>

<div class="footnotes">
<hr/>
<ol>
<li id="fn:1">
The book is freely available from <a href="https://www.gutenberg.org/ebooks/11">Project Gutenberg</a>.<a href="#fnref:1" rev="footnote">&#8617;</a></li>
<li id="fn:2">
<p>The invention of Scrabble is attributed to Lewis Carroll&rsquo;s brief journal entry:
&ldquo;A game might be made of letters, to be moved about on a chess board till they form words&rdquo; (Dec 19th,
<a href="http://www.fullbooks.com/The-Life-and-Letters-of-Lewis-Carroll3.html">&ldquo;The Life and Letters of Lewis Carroll&rdquo;</a> ).
See also <a href="https://scrabbledaily.blogspot.com/2008/05/history-of-scrabble.html">&ldquo;History of Scrabble&rdquo;</a>
and <a href="http://www.bananagrammer.com/2009/10/games-of-lewis-carroll.html">&ldquo;The games of Lewis Carroll&rdquo;</a>.</p>

<p>His book <a href="https://en.wikipedia.org/wiki/The_Game_of_Logic">&ldquo;The Game of Logic&rdquo;</a> teaches formal logic
using a board game. It is also available from <a href="https://www.gutenberg.org/ebooks/4763">Project Gutenberg</a>.</p><a href="#fnref:2" rev="footnote">&#8617;</a></li>
<li id="fn:3">
&ldquo;Lawn tennis tournaments; the true method of assigning prizes with a proof of
the fallacy of the present method&rdquo;. London, Macmillan and co., 1883.<a href="#fnref:3" rev="footnote">&#8617;</a></li>
<li id="fn:4">
Knuth: it is not formulated precisely enough to qualify as an algorithm.<a href="#fnref:4" rev="footnote">&#8617;</a></li>
<li id="fn:5">
See chapter 5.3.3 in Volume 3 of &ldquo;The Art of Computer Programming&rdquo;.<a href="#fnref:5" rev="footnote">&#8617;</a></li>
<li id="fn:6">
Alex: What do we mean when we say lots of memory?
<code>O(n)</code> is bad, <code>O(sqrt(n))</code> is pretty bad.
See the definition of &ldquo;in-place memory usage&rdquo; at the end of the chapter.<a href="#fnref:6" rev="footnote">&#8617;</a></li>
<li id="fn:7">
<p>A binary function <code>f</code> is <a href="https://en.wikipedia.org/wiki/Associative_property">associative</a>
if the the following holds for all <code>a, b, c</code> in its domain:</p>

<pre><code>f(f(a, b), c)) = f(a, f(b, c))
</code></pre>

<p>Informally, <code>f</code> can be applied in any order.
For example, addition of integers is associative:</p>

<pre><code>(a + b) + c = a + (b + c)
</code></pre>

<p>Subtraction of integers is not associative:</p>

<pre><code>(3 - 2) - 1 != 3 - (2 - 1)
</code></pre>

<p>You can see why associativity is often referred to as being
able to &ldquo;re-parenthesize&rdquo; expressions.</p><a href="#fnref:7" rev="footnote">&#8617;</a></li>
<li id="fn:8">
<p>A binary function <code>f</code> is <a href="https://en.wikipedia.org/wiki/Commutative_property">commutative</a>
if for all <code>a, b</code> in its domain:</p>

<pre><code>f(a, b) = f(b, a)
</code></pre>

<p>Informally, <code>f</code> gets the same result, regardless of the order of the inputs.
For example, multiplication of integers is commutative:</p>

<pre><code>a * b = b * a
</code></pre>

<p>In Chapter 9.1 of &ldquo;From Mathematics to Generic Programming&rdquo;, Alex gives
a neat visual proof of this fact for integer multiplication:</p>

<pre><code>              * * *
* * * * *     * * *
* * * * *  =  * * *
* * * * *     * * *
              * * *
</code></pre>

<p>Or as <a href="https://en.wikipedia.org/wiki/Peter_Gustav_Lejeune_Dirichlet)">Dirchlet</a> put it: &ldquo;Whether you arrange soldiers in rows or columns, you still have the same number of soldiers&rdquo;.</p>

<p>An example of an operation which is not commutative is string concatenation.</p>

<pre><code>"Hello, " + "World!" != "World!" + "Hello, "
</code></pre><a href="#fnref:8" rev="footnote">&#8617;</a></li>
<li id="fn:9">
Alex: If you think about it,
our <code>min</code> is not quite commutative.
In mathematics <code>min</code> is commutative.
But because we want to preserve stability, it is not.
We distinguish between the left and right argument.<a href="#fnref:9" rev="footnote">&#8617;</a></li>
<li id="fn:10">
<p>The terms <strong>carry</strong> and <strong>overflow</strong>
are closely associated the implementation of binary counting
or addition as an electrical circuit, called an <a href="https://en.wikipedia.org/wiki/Adder_(electronics)">adder</a>.</p>

<p>A single bit adder has two inputs <code>a</code> and <code>b</code> for
the two digits to add together.
It outputs a digit <code>s</code> which is the digit
to display for this place value.
There is a supplementary output called the carry,
which is the amount that needs to move to the
higher place value.</p>

<p>The circuit behavior is determined by the following input/output table:</p>

<pre><code>a  b   c  s
----------
1  0 | 0  1
0  1 | 0  1
1  1 | 1  0
</code></pre>

<p>This adds a single digit, but we want to add entire numbers.
To, do so we add an additional input <code>l</code> for carried digits
from lower place values.</p>

<pre><code>a  b  l    c  s
----------------
1  0  0  | 0  1
0  1  0  | 0  1
1  1  0  | 1  0
1  0  1  | 1  0
0  1  1  | 1  0
1  1  1  | 1  1
</code></pre>

<p>Now we can chain <code>n</code> of them together to be able to add <code>n</code> digits</p>

<pre><code>    s_1 c_1-----|      s_2 c_2----  ...
    |   |       |      |   |
 -----------    |   ------------
 |    |    |    |   |    |    |
l_1  a_1  b_1   |_ l_2   a_2  b_2
</code></pre>

<p>An <strong>overflow</strong> is when the last adder has a non-zero carry.</p><a href="#fnref:10" rev="footnote">&#8617;</a></li>
<li id="fn:11">
Alex: Maybe we should make it in China.
That&rsquo;s a necessary prerequisite for beautiful design.
<a href="https://signalvnoise.com/posts/2710-designed-by-apple-in-california">Designed in Cupertino</a>, assembled in China.
So let&rsquo;s try to assemble our machine in Palo Alto.<a href="#fnref:11" rev="footnote">&#8617;</a></li>
<li id="fn:12">
<p>Floating point arithemetic can involve many tricky details,
but the basic issue Alex is referring to is straightforward.
We often use scientific notation to write larger numbers as a decimal to a power,
when they would otherwise be very long to write out.
For example <code>1,450,000,000 == 1.45 * 10^9</code>.
However, adding two numbers in this form can only be done accurately if they are roughly of the same power,
otherwise the larger of the two is still the best representation:
<code>1.45 * 10^9 + 1 ~= 1.45 * 10^9</code>.</p>

<p><code>float</code> and <code>double</code> have very similar limitations, and give the best results
when operations are applied to values of similar magnitudes.
To try for yourself, compare these two expressions in a program:</p>

<pre><code>double x = (152500.0 * 5000.0);
double y = (152500.0 * 5000.0) + 0.01;
</code></pre><a href="#fnref:12" rev="footnote">&#8617;</a></li>
</ol>
</div>


<span style="float: right">
[
<a href="09_iterators.html">previous</a>, 
<a href="index.html">contents</a>, 
<a href="11_min_1_2.html">next</a>
]
</span>


</body>
</html>