-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy path10_binary_counter.html
673 lines (546 loc) · 27.7 KB
/
10_binary_counter.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
<!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’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">“Alice’s Adventures in Wonderland”</a>.
If you haven’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 “Alice in Wonderland”.
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’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’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">“The Art of Computer Programming”</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 “useful”, meaning it’s not “programming in Python for idiots”,
or “information retrieval for 21st century” 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’m going to be mentioning Knuth throughout the course.
It’s not a perfect book, it is just the greatest book we’ve got.
Some people think it’s a good reference book.
No, it’s not, because you have to
basically do linear search to find what you’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 “The Art of Computer Programming”, but somehow Knuth does not implement it.
As we shall see it’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’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’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’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’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’s all recursive.
But, let us think about how many comparisons it’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> “games”.
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…</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’s not what we’re trying to accomplish, so divide and conquer doesn’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’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’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’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 associative operation on <code>T</code>.
What we can do is create an array called a “counter”.</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> “victories” so far.
So if there is a guy in slot 0 he hasn’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’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 --> 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 --> 0 y ... 0
</code></pre>
<p>Otherwise <code>x</code> wins:</p>
<pre><code>0 1 ... 31 0 1 ... 31
x 0 ... 0 --> 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 propagate</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’s called an <strong>overflow</strong>.</p>
<p>We borrow terminology from binary integer arithmetic 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 “bit” we have arbitrary 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’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’s his business not ours.</p>
<p>Let us be lazy.
The great success in programming comes because there are lazy people who say,
“I don’t want to know now,
I’ll find out later.”
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 <typename T, typename I, typename Op>
// 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& 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&</code> reference because we don’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 <typename T, typename I, typename Op>
// 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& zero) {
while (first != last && *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’t happen.
So we can’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’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’t start with objects.
Figure out what you’re going to do first.
But you don’t have to stop there.
Because you can then put things together into an object.</p>
<p>It’s very easy when you write an algorithm to have a minimal iterator interface.
In this case, the iterators externalize the counter.
We say, “we don’t want to know about him,
we’re just algorithms people”.
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’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’s actually a small fixed size.
We will store it in a <code>std::vector</code>.</p>
<pre><code>template <typename Op, typename T = typename Op::argument_type>
class binary_counter
{
private:
std::vector<T> counter;
Op op;
T zero;
public:
binary_counter(const Op& op, const T& 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’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 numerical analysis, whenever you sum up large numbers you don’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’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 associative 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’t require any extra memory.
Then they decided constant memory was enough.
But, then they said it doesn’t quite work because our favorite algorithm
doesn’t work. Of course the most important algorithm is <a href="https://en.wikipedia.org/wiki/Quicksort">quicksort</a>.
It’s not in-place because it’s recursive.
Recursive algorithms tend to require <code>O(log(n))</code>.
Quicksort splits roughly in the middle let’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, “what if we have nested things?”
So is <code>log(n)^2</code> ok?
In our universe <code>log(n) <= 64</code> so this is 4096.
Then theoreticians said it’s really alright if we have “poly-logarithmic” storage
Basically as long as the memory requirement is <code>O(p(log(n)))</code>
where <code>p</code> is a polynomial, it’s alright.
Polynomials get a lot bigger than square,
but let’s go with “poly-logarithmic” being “in-place”.</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">↩</a></li>
<li id="fn:2">
<p>The invention of Scrabble is attributed to Lewis Carroll’s brief journal entry:
“A game might be made of letters, to be moved about on a chess board till they form words” (Dec 19th,
<a href="http://www.fullbooks.com/The-Life-and-Letters-of-Lewis-Carroll3.html">“The Life and Letters of Lewis Carroll”</a> ).
See also <a href="https://scrabbledaily.blogspot.com/2008/05/history-of-scrabble.html">“History of Scrabble”</a>
and <a href="http://www.bananagrammer.com/2009/10/games-of-lewis-carroll.html">“The games of Lewis Carroll”</a>.</p>
<p>His book <a href="https://en.wikipedia.org/wiki/The_Game_of_Logic">“The Game of Logic”</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">↩</a></li>
<li id="fn:3">
“Lawn tennis tournaments; the true method of assigning prizes with a proof of
the fallacy of the present method”. London, Macmillan and co., 1883.<a href="#fnref:3" rev="footnote">↩</a></li>
<li id="fn:4">
Knuth: it is not formulated precisely enough to qualify as an algorithm.<a href="#fnref:4" rev="footnote">↩</a></li>
<li id="fn:5">
See chapter 5.3.3 in Volume 3 of “The Art of Computer Programming”.<a href="#fnref:5" rev="footnote">↩</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 “in-place memory usage” at the end of the chapter.<a href="#fnref:6" rev="footnote">↩</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 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 “re-parenthesize” expressions.</p><a href="#fnref:7" rev="footnote">↩</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 “From Mathematics to Generic Programming”, 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">Dirichlet</a> put it: “Whether you arrange soldiers in rows or columns, you still have the same number of soldiers”.</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">↩</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">↩</a></li>
<li id="fn:10">
<p>The terms <strong>carry</strong> and <strong>overflow</strong>
are closely associated with 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">↩</a></li>
<li id="fn:11">
Alex: Maybe we should make it in China.
That’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’s try to assemble our machine in Palo Alto.<a href="#fnref:11" rev="footnote">↩</a></li>
<li id="fn:12">
<p>Alex is referring to the following issue:
When floating point numbers become very large they can no longer represent small nearby increments.
So if many small numbers are accumulated in order, the sum may grow large enough to ignore the contribution of any particular element.
To see for yourself, observe that:</p>
<pre><code>double x = 1.45 * pow(2, 60);
assert(x == x + 1.0);
</code></pre>
<p>This is because floats are represented as a base and exponent, and the magnitude of the exponent constrains the precision.</p>
<p>If we forget about computers, and think about science or engineeing, it’s natural to consider:</p>
<pre><code>1.45 * 2^60 + 1 ~= 1.45 * 2^60
</code></pre>
<p>because the <code>1</code> is not very significant to the overall magnitutde.</p><a href="#fnref:12" rev="footnote">↩</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>