Paper: “Bitcoin: A Peer-to-Peer Electronic Cash System”

The fundamental paper of crypto-currency bitcoin (PDF) was written by Satoshi Nakamoto. Who is Satoshi Nakamoto? We just don’t know. Nakamoto’s bitcoins currently yield a value of $4.2 billion USD, but he is not using that money for any purpose. He is not involved in Bitcoin anymore and the paper itself is a wonderful read. It is nice to see that people can still truely hide their identity. But people wonder about the motivation for this technology to this day. For now, let us focus on the paper and technical details.

The paper lays out the design of bitcoin based on the ideas of asymmetric cryptography, hashing and probability theory. The sections are named as follows:

  1. Introduction
  2. Transactions
  3. Timestamp server
  4. Proof-of-Work
  5. Network
  6. Incentive
  7. Reclaiming Disk Space
  8. Simplified Payment Verification
  9. Combining and Splitting Value
  10. Privacy
  11. Calculations
  12. Conclusions

The rationale for the cryptocurrency is given with decentralization; there is no central trusted party.

An electronic coin is defined “as a chain of digital signatures” (section 2). Coins are mined/created. And every coin is basically the set of signatures of how it was transmitted between parties. The author does not explain existing technology. He published the paper in 2008 in the mids of his development of Bitcoin Core 1.0, which took him at least 2 years. And most technical details are left out. The paper is reduced to the theoretical fundamentals and how certain threats are mitigated. For example, the Proof of work technology (section 4) was known since 1993 and he simply points out that he uses it with the number of leading zero bits of SHA-256 hashes to define a certain difficulty.

Reclaiming Disk Space (section 7) is solved by reducing a Merkle tree to its root hash. This way the block information is reduced. Only on demand the full information will be retrieved and verification can be done. This proves, that Nakamoto was well aware of the problem of an ever-growing global transaction log. I still consider it as one of the weak points of Bitcoin’s scalability. But we have to admit that many blockchain technologies emerged and are accessible to the mainstream these days. And blockchains solve the major problem of double spending, which I consider as the real innovation of the paper. In the final sections, he justifies that a malicious takeover of the network is unlikely or difficult if the honest blocks progress as usual. The more the malicious transaction branch diverges, the more difficult it will get to convince other users of its correctness. I have to admit, that so far, I don’t grasp his assumption of a Poisson distribution at page 7.

If you don’t fully understand the details, the bitcoin community maintains a bitcoin wiki covering topics such as Bitcoin Myths. And personally speaking, I understood Bitcoin much better back in 2012, when I listened to Chaosradio Express, episode 182 (German podcast). The paper gives an academic approach (references existing papers and just parameterizes existing ideas), but the podcast gives a step-by-step introduction for all cryptographic ideas implemented in bitcoin.

In conclusion, I am not convinced of Bitcoin. It has many issues, that seem to be ignored. But decentralized money is interesting and Nakamoto’s paper is a masterpiece of academic work. Still residing in Japan and struggling with the language barrier every day, I would like to conclude with the following quote from Wikipedia: “[…] but some speculated he was unlikely to be Japanese due to his use of perfect English and his bitcoin software not being documented or labelled in Japanese”. Indeed, the English in the paper is exceptionally well-written.

Paper: “Bitcoin: A Peer-to-Peer Electronic Cash System”

An empty clause represents a contradiction

The problem

I have just gone through many CNF files and come across the following file:

p cnf  150  400
     -3      -2      -1 0
      3       2      -1 0
      2       1      -3 0
[...]
    150     149      98 0
    150    -149     -98 0
    149    -150     -98 0
     98    -150    -149 0
0

available as pret150_25.cnf and originally authored by Daniel Pretolani.

To those unfamiliar with DIMACS CNF files, this file represents the boolean formula defined as

f(x1, x2, …, x150) =
(-x3 ∨ -x2 ∨ -x1) ∧
(x3 ∨ x2 ∨ -x1) ∧
(x2 ∨ x1 ∨ -x3) ∧

(x150 ∨ x149 ∨ x98) ∧
(x150 ∨ -x149 ∨ -x98) ∧
(x149 ∨ -x150 ∨ -x98) ∧
(x98 ∨ -x150 ∨ -x149)

So 0 terminates clauses which are disjunctions (denoted with ) of literals.
However, the trailing 0 triggers the question whether the boolean function actually ends with

∧ (x98 ∨ -x150 ∨ -x149) ∧ ()

or as before:

∧ (x98 ∨ -x150 ∨ -x149)

Rationale

If the former is satisfied, the question is raised, what an empty clause means. Considering that

(x98 ∨ -x150 ∨ -x149)
= (x98 ∨ -x150 ∨ -x149 ∨ ⊥)
= (x98 ∨ -x150 ∨ -x149 ∨ ⊥ ∨ ⊥ ∨ ⊥)

where ⊥ denotes boolean value false, this should apparently mean

()
= (⊥)
= (⊥ ∨ ⊥ ∨ ⊥)

This is the rationale why an empty clause should represent the boolean value false (in my humble opinion). Thus rendering the CNF file above with the former notation and specifically the problem unsatisfiable.

An empty clause represents a contradiction

Paper: “Engineering a Sort Function”

“Engineering a Sort Function” by John L. Bentley and M. Douglas McIlroy gives a nice insight how theoretical algorithm design is applied in software engineering. I think I came across the paper, because Go’s sort function implementation is based on the described algorithm.

The paper outlines how the unstable sort algorithm has evolved over several iterations during development. It is based on Quicksort, but uses insertion sort for arrays of size ≤7. The solution to Dijkstra’s Dutch national flag problem gives the partition method for QuickSort. Pivot elements are selected with the median of 3 (array size >40) or median of 9 (array size ≤40). You can also see how cost models are applied such that asymptotic behavior becomes less important compared to the expense of particular operations. I think it is interesting, because cost models are not taught here at University of Technology, Graz, whereas asymptotic behavior is focused. However, this model fails where the comparison function can be arbitrary according to the interface and so the actual expense of comparison cannot be estimated.

In the end, I think it is a nice read for 2 hours assuming you are familiar with basic algorithm design.

“[…] This algorithm is easy to describe, and also easy to get wrong—Knuth tells horror stories about inefficient partitioning algorithms.”

“The key to performance is elegance, not battalions of special cases.”

Paper: “Engineering a Sort Function”

Using namespaces with lxml.etree

I need to admit, when I initiated and released ruledxml for the first time, I didn’t care much about namespaces. The usecase was not prevalent in my setting. This changed now.

Time to implement it properly and so I need to look at handling XML namespaces with python’s lxml.etree in more detail. In the following you can see a cheatsheet how you achieve a certain XML namespaced output with lxml.etree.Element instances.

The following table always shows a desired result following by the python source code to generate it.

<a><b/></a>
>>> a = lxml.etree.Element('a')
>>> b = lxml.etree.Element('b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a><b/></a>'
<a xmlns="http://example.org/">
  <b/>
</a>
>>> a = lxml.etree.Element('a', nsmap={None: 'http://example.org/'})
>>> b = lxml.etree.Element('b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns="http://example.org/"><b/></a>'
<a xmlns:ex="http://example.org/">
  <ex:b/>
</a>
>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> b = e('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/"><ex:b/></a>'
<ex:a xmlns:ex="http://example.org/">
  <ex:b/>
</ex:a>
>>> a = lxml.etree.Element('{http://example.org/}a',
...   nsmap={'ex': 'http://example.org/'})
>>> b = e('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/"><ex:b/></ex:a>'
<ex:a xmlns:ex="http://example.org/" ex:attr="value">
  <ex:b/>
</ex:a>
>>> a = lxml.etree.Element('{http://example.org/}a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib['{http://example.org/}attr'] = 'value'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/"
   ex:attr="value"><ex:b/></ex:a>'
<ex:a xmlns:ex="http://example.org/example"
      xmlns:org="http://example.org/organization"
      ex:attr="value">
  <org:b ex:example="value1" org:example="value2"/>
</ex:a>
>>> a = lxml.etree.Element('{http://example.org/example}a',
...   nsmap={'ex': 'http://example.org/example',
...          'org': 'http://example.org/organization'})
>>> a.attrib['{http://example.org/example}attr'] = 'value'
>>> b = lxml.etree.Element('{http://example.org/organization}b')
>>> b.attrib['{http://example.org/example}example'] = 'value1'
>>> b.attrib['{http://example.org/organization}example'] = 'value2'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<ex:a xmlns:ex="http://example.org/example"
        xmlns:org="http://example.org/organization"
        ex:attr="value">
    <org:b ex:example="value1" org:example="value2"/></ex:a>'
<a xmlns:ex="http://example.org/" xml:lang="ja">
  <ex:b/>
</a>
>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'ja'
>>> b = lxml.etree.Element('{http://example.org/}b')
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/" xml:lang="ja"><ex:b/></a>'
<a xmlns:ex="http://example.org/" xml:lang="ja">
  <ex:b xml:lang="en"/>
</a>
>>> a = lxml.etree.Element('a',
...   nsmap={'ex': 'http://example.org/'})
>>> a.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'ja'
>>> b = lxml.etree.Element('{http://example.org/}b')
>>> b.attrib["{http://www.w3.org/XML/1998/namespace}lang"] = 'en'
>>> a.append(b)
>>> lxml.etree.tostring(a)
b'<a xmlns:ex="http://example.org/" xml:lang="ja"><ex:b
  xml:lang="en"/></a>'
Using namespaces with lxml.etree

Boston Key Party: Graph 3-coloring with SAT solvers

The Boston Key Party was held between 4th and 6th of March 2016. A few colleagues of mine attended this event and asked for help with one particular problem:

Given a graph with 683 vertices and 1253 edges. Assign one of three colors to each vertex. No edge must connect two vertices of the same color.

Graph 3-coloring is a classic example of an NP-complete problem. So a SAT solver might be suitable for it as far as more efficient algorithms are not known.

Let’s solve this problem with an approach similar to an implementation I use in my master thesis: Generate the CNF using python, let a SAT solver do the hard work and parse the solver’s result back to python and print the assignment of colors to vertices.

The boolean logic is really simple: Every vertex gets assigned three boolean variables. We add the following constraints:

  • Only one of three variables can be true.
  • For every edge (s, t) we look up the corresponding colors for s and t: r1,g1,b1 and r2,g2,b2. We claim not both r1 and r2 can be true. Not both g1 and g2 can be true. Not both b1 and b2 can be true.

In code it looks like this:

def oneof3(w, a, b, c):
    w.add_clause(a, b, c)
    w.add_clause(-a, -b, c)
    w.add_clause(-a, b, -c)
    w.add_clause(a, -b, -c)
    w.add_clause(-a, -b, -c)

def notboth(w, a, b):
    w.add_clause(-a, -b)

def add_constraints(graph, w):
    # constraints for colors of one vertex
    for v, (red, green, blue) in graph.vertices.items():
        oneof3(w, red, green, blue)

    # constraint for edges
    for (src, dst) in graph.edges:
        r1, g1, b1 = graph.vertices[src]
        r2, g2, b2 = graph.vertices[dst]
        notboth(w, r1, r2)
        notboth(w, g1, g2)
        notboth(w, b1, b2)

The final source code looked like this (you need to adjust the path to the SAT solver executable; you should use lingeling):

#!/usr/bin/env python3

import re
import os
import sys
import logging
import tempfile
import itertools
import subprocess


# the output format is expected to be compatible with lingeling
SATSOLVER_EXECUTABLE = '/opt/lingeling-bal-2293bef-151109/lingeling'
SATSOLVER_TIMEOUT = None  # or specify an integer in seconds
VERTICES = 683


class Graph:
    def __init__(self, nb_vertices):
        self.edges = set()
        self.nb_vertices = nb_vertices
        self.vertices = {k: (3 * k + 1, 3 * k + 2, 3 * k + 3)
                         for k in range(nb_vertices)}

    def read_edges(self, filepath: str):
        """Read edges from a file containing '{src} {dest}' lines"""
        with open(filepath) as fd:
            for line in fd:
                if line.startswith('#'):
                    continue
                src, dst = [int(v) for v in line.split()]
                assert 0 <= src < self.nb_vertices \
                    and 0 <= dst < self.nb_vertices, "vertex number invalid"
                self.edges.add((src, dst))

    def get_assignment(self, model: set):
        """Given a set of positive or negative boolean variables,
        return a dictionary assigning 1, 2 or 3 to every vertex
        """
        ass = {}
        for v, (r, g, b) in self.vertices.items():
            assert (r in model) ^ (g in model) ^ (b in model)
            assert (r not in model) | (g not in model) | (b not in model)
            ass[v] = {r in model: 1, g in model: 2, b in model: 3}[True]
        return ass


# storage/writer for CNF data

class CnfStorage:
    def __init__(self, fd):
        self.fd = fd
        self.clauses = set()
        self.nbvars = 0

    def add_clause(self, *ints):
        self.nbvars = max(self.nbvars, max([abs(v) for v in ints]))
        self.clauses.add(tuple(ints))

    def finish(self):
        self.fd.write('p cnf {} {}\n'.format(self.nbvars, len(self.clauses)))
        for clause in self.clauses:
            self.fd.write(' '.join([str(i) for i in clause]) + ' 0\n')
            self.fd.flush()


# CNF primitives
#   Related: http://lukas-prokop.at/tools/truthtable/

def oneof3(w, a, b, c):
    w.add_clause(a, b, c)
    w.add_clause(-a, -b, c)
    w.add_clause(-a, b, -c)
    w.add_clause(a, -b, -c)
    w.add_clause(-a, -b, -c)


def notboth(w, a, b):
    w.add_clause(-a, -b)


def add_constraints(graph, w):
    # constraints for colors of one vertex
    for v, (red, green, blue) in graph.vertices.items():
        oneof3(w, red, green, blue)

    # constraint for edges
    for (src, dst) in graph.edges:
        r1, g1, b1 = graph.vertices[src]
        r2, g2, b2 = graph.vertices[dst]
        notboth(w, r1, r2)
        notboth(w, g1, g2)
        notboth(w, b1, b2)


# run the SAT solver

def run_solver(filepath):
    """Run SAT solver as subprocess. Return stdout"""
    proc = subprocess.Popen(
        [SATSOLVER_EXECUTABLE, filepath],
        stdout=subprocess.PIPE, stderr=subprocess.PIPE)

    try:
        outs, errs = proc.communicate(timeout=SATSOLVER_TIMEOUT)
        out = outs.decode('ascii')
    except subprocess.TimeoutExpired:
        proc.kill()
        outs, errs = proc.communicate()
        out = errs.decode('ascii')

    if proc.returncode == 20:
        raise RuntimeError('SAT solver returned UNSATisfiability')
    if proc.returncode != 10:
        errmsg = 'SAT solver returned error code {}: {}'
        raise RuntimeError(errmsg.format(proc.returncode, errs))
    return out


def interpret_output(out):
    """Read a model (set of positive/negative integers) from stdout"""
    model = []
    logging.debug(out)

    something = False
    for line in out.splitlines():
        if line.startswith("v "):
            matches = map(int, re.findall(" (-?\d+)", line))
            something = True
            for match in matches:
                if match == 0:
                    # trailing zero
                    continue
                assert -match not in model
                model.append(match)

    if not something:
        raise RuntimeError("Model empty - most likely the SAT solver " +
                           "output is incompatible with lingeling")

    return tuple(model)


if __name__ == '__main__':
    if len(sys.argv) != 2:
        print('usage: ./graph-3-coloring.py <edges.txt>')
        sys.exit(1)

    fd, filepath = tempfile.mkstemp(prefix='graph-3-coloring')

    try:
        # generate graph
        graph = Graph(VERTICES)
        graph.read_edges(sys.argv[1])
        logging.info("{} read".format(sys.argv[1]))

        # store CNF
        w = CnfStorage(os.fdopen(fd, mode='w', encoding='ascii'))
        add_constraints(graph, w)
        w.finish()
        logging.info("Finished generating CNF file")

        # run SAT solver
        out = run_solver(filepath)
        model = interpret_output(out)
        assignment = graph.get_assignment(model)

        # print result
        for vertex, color in assignment.items():
            print('{}: {}'.format(vertex, color))
    finally:
        os.unlink(filepath)

And how long did it take to run it? 0.9 seconds 😎
Thank you lingeling!

Boston Key Party: Graph 3-coloring with SAT solvers

Paper: “Mastering the game of Go with deep neural networks and tree search”

Most recently, a paper “Mastering the game of Go with deep neural networks and tree search” was published in Nature. It describes a neural network architecture which for the first time won against a 2-dan professional Go player (Fan Hui) without handicaps achieving the title of the strongest Go engine existing. Between 5th and 15th of March 2016 a match between the engine – namely AlphaGo – and Lee Se-dol is scheduled. AlphaGo is pushed by Google.

It was difficult to me to follow the formal details lacking experience in machine learning. Here I would just like to cite the most interesting quotes:

[…] These games may be solved by recursively computing the optimal value function in a search tree containing approximately bd possible sequences of moves, where b is the game’s breadth (number of legal moves per position) and d is its depth (game length). In large games, such as chess (b ≈ 35, d ≈ 80) and especially Go (b ≈ 250, d ≈ 150), exhaustive search is infeasible, but the effective search space can be reduced by two general principles. First, […] position evaluation […] Second […] sampling actions from a policy p(a|s) that is a probability distribution over possible moves a in position s.

[…] evaluating positions using a value network, and sampling actions using a policy network.

We trained a 13-layer policy network […] from 30 million positions from the KGS Go Server.

We also tested against the strongest open-source Go program, Pachi.

The final version of AlphaGo used 40 search threads, 48 CPUs, and 8 GPUs. We also implemented a distributed version of AlphaGo that exploited multiple machines, 40 search threads, 1202 CPUs and 176 GPUs. […] The distributed version of AlphaGo was significantly stronger, winning 75% of games against single-machine AlphaGo and 100% of its games against other programs.

A policy p(a|s) is a probability distribution over legal actions a ∈ (s). A value function is the expected outcome if all actions for both players are selected according to policy p, that is, vP(s) = [zt|st = s, at…T ~ p].

Our rollout policy pΠ(a|s) contains less handcrafted knowledge than state-of-the-art Go programs.

Time controls for formal games were 1h main time plus three periods of 30s byoyomi.

The neural network architecture itself is described in the Methods Appendix. The (formal and informal) game results are provided as Data sheet. And in Methods/Evaluation a closing parenthesis is missing in the denominator of the logistic function 😉

Paper: “Mastering the game of Go with deep neural networks and tree search”

I computed M74207281

On 7th of January 2016, GIMPS found Mersenne prime number M74207281. GIMPS is a project combining efforts of a large crowd of volunteers contributing computing power and a university server combining the result – maintained by Curtis Cooper. If a number can be found satisfying the conditions of a Mersenne prime number, the number will be checked with primality tests; according to the article it took 31 days to do so.

M74207281 is specified 2274 207 281-1 and a friend of mine at GoGraz wondered how to compute this number in decimal representation. I suggested square and multiply, but wasn’t sure how long it might take.

So I implemented the exp-by-squaring-iterative algorithm on Wikipedia (didn’t thoroughly check whether it is the most efficient algorithm for this kind of problem):

package main

import (
	"log"
	"math/big"
	"os"
	"strconv"
)

var zero *big.Int
var one *big.Int
var two *big.Int
var hundred *big.Int

func init() {
	// initialize global values
	zero = big.NewInt(0)
	one = big.NewInt(1)
	two = big.NewInt(2)
	hundred = big.NewInt(100)
}

// ExpBySquaringIterative exponentiates by squaring meaning it computes x^n
// in logarithmic time in size of n
func ExpBySquaringIterative(x, n *big.Int) *big.Int {
	switch n.Cmp(zero) {
	case -1:
		x.Div(one, x)
		n.Neg(n)
	case 0:
		c := big.NewInt(1)
		return c
	}

	y := big.NewInt(1)
	for n.Cmp(one) > 0 {
		x2 := big.NewInt(0)
		x2.Set(x)

		nm := big.NewInt(0)
		if n.Bit(0) == 0 {
			x.Mul(x2, x2)
			n.Div(n, two)
		} else {
			y.Mul(x2, y)
			x.Mul(x2, x2)
			nm.Sub(n, one)
			n.Div(nm, two)
		}
	}
	return x.Mul(x, y)
}

func main() {
	if len(os.Args) == 1 {
		log.Println("usage: go run num_2n1.go <exponent>")
		log.Println("  M74207281 is given by exponent 74207281")
		os.Exit(1)
	}

	expstr := os.Args[1]
	exponent, err := strconv.Atoi(expstr)
	if err != nil {
		log.Fatal(err)
	}

	log.Println("TBD   ExpBySquaringIterative")
	result := ExpBySquaringIterative(big.NewInt(2), big.NewInt(int64(exponent)))
	result.Sub(result, one)
	log.Println("DONE  ExpBySquaringIterative")
	log.Println("TBD   computing decimal representation")
	log.Printf("2^%d - 1 = ", exponent)
	log.Println(result)
	log.Println("DONE  computing decimal representation")
}

And how long does it take to compute this number?

Computation of M74207281

Figure 1. Computation of M74207281

Was there anything interesting about it?

  • The decimal representation uses 22.4 MB memory.
  • It took 1 hour 27 minutes to compute the decimal representation. But it only takes 4 seconds to actually compute the number in binary. By far most of the hours are spent on computing the decimal string representation.
  • The builtin function Exp (you need to set m to nil) takes 1 hour 17 minutes; so it takes a little bit less time.
  • For reference, the first digits are 300376418084… and the last digits are …073391086436351 as can be seen on lcns2’s page.
I computed M74207281

Running Donald Knuth’s CWEB programs

I just realized that no-one documented how to quickly run Donald Knuth’s programs he publishes in his WEB system.

Suppose you want to compile a program like commafree; a program he wrote between September and December 2015 for his Annual Christmas tree lecture in 2015 about Universal Commafree Codes.

  1. Download the webfile which comprises documentation and source code.

    wget http://www-cs-faculty.stanford.edu/~uno/programs/commafree-eastman.w
  2. Recognize that the programming language used is C. Hence we need to use cweave and ctangle; not the original weave and tangle designed for Pascal.
    All those programs come bundled with TeX distributions like TeXLive. Once you have them installed and your system can find executables like pdflatex, it will also find cweave, etc.
  3. First, we generate the documentation.
    1. We run

      cweave commafree-eastman.w

      On my system this gives the output

      This is CWEAVE, Version 3.64 (TeX Live 2015/dev/Debian)
      *1*3*8
      Writing the output file...*1*3*8
      Writing the index...
      Done.
      (No errors were found.)
    2. Three files are generated, namely commafree-eastman.idx, commafree-eastman.scn and commafree-eastman.tex.
    3. As a small remark, the TeX file uses the cwebmac definitions. So it is a file full of definitions and this file is also provided with your TeX distribution:
      % head -n 1 commafree-eastman.tex
      \input cwebmac
      % locate cwebmac
      /usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfXcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfdcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdffcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdficwebmac.tex
    4. Then we run the original tex program to build a dvi file.

      tex commafree-eastman.tex

      This gives me the output:

      This is TeX, Version 3.14159265 (TeX Live 2015/dev/Debian) (preloaded format=tex)
      (./commafree-eastman.tex
      (/usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex) *1 [1] *3 [2]
      [3] *8 Index: (./commafree-eastman.idx) [4] Section names:
      (./commafree-eastman.scn) [5] Table of contents: (./commafree-eastman.toc)
      [0] )
      Output written on commafree-eastman.dvi (6 pages, 16116 bytes).
      Transcript written on commafree-eastman.log.
    5. Followingly, a file commafree-eastman.dvi is written as the output states. Opening it directly with evince 3.14.2 shows the output with some errors (the typical font encoding problems of TeX like < in #include statements is replaced by ¡). With okular 0.21.3 I can view the document without any problems.
    6. We convert the DVI file using the utility dvipdfm provided with your TeX distribution:
      dvipdfm commafree-eastman.dvi

      For me, this gives:

      commafree-eastman.dvi -> commafree-eastman.pdf
      [1][2][3][4][5][6]
      45807 bytes written

      Then we have a PDF output file commafree-eastman.pdf containing the documentation.
      I think this is the usual way to view documents, you were looking for.

  4. We generate the source code:

    1. First we run ctangle:
      ctangle commafree-eastman.w

      which gives me:

      This is CTANGLE, Version 3.64 (TeX Live 2015/dev/Debian)
      *1*3*8
      Writing the output file (commafree-eastman.c):
      Done.
      (No errors were found.)
    2. Nice! So we got a commafree-eastman.c file.
    3. We compile the C file with a C compile like the GCC:
      gcc -Wall -o commafree-eastman commafree-eastman.c

      This gives me:

      ./commafree-eastman.w:38:1: warning: return type defaults to ‘int’ [-Wreturn-type]
       main (int argc,char*argv[]) {
       ^
      ./commafree-eastman.w: In function ‘main’:
      ./commafree-eastman.w:42:1: warning: control reaches end of non-void function [-Wreturn-type]
       }
       ^
    4. We run this new executable program:
      ./commafree-eastman
      Usage: ./commafree-eastman x1 x2 ... xn

      This gives the same output as in the video.

So we got a commafree-eastman.pdf and commafree-eastman.c file which was what we were going for.
I will also refer here to my Literate programming talk at PyGraz back then.

Running Donald Knuth’s CWEB programs

LaTeX math cheatsheets

My girlfriend asked for LaTeX cheatsheets. There are many of them online, but she was specifically looking for notational commands for algebra and number theory. You need to be aware that notation is very specific for your teacher. So standardization has not been successful to raise mathematical symbols from a representational to a semantical level. In US/UK/AU (in my experience), there is little information encoded in notation and information is provided in short, concise sentences. In Europe, this is different and every teacher has his/her own notation.

But let’s get back to the point: I recommend the following cheatsheets, but evaluate yourself whether it fits your field.

If you need a more comprehensive reference, the LaTeX wikibook is a nice start. For a german audience, LaTeX@TUGraz also does a good job IMHO.

And as always: If you look for a symbol and have internet connection, detexify makes your life much easier!

LaTeX math cheatsheets