tobilehman.com: a blog on computing, structure and math

Abusing Proverbs

I recently became a father, and that experience has lead to me to wonder what my son will be like when he his older. It’s also lead me remember what I was like when I was younger. I usually didn’t take things my teachers said seriously, this has lead to good things and bad.

For the bad, I didn’t try hard in math in high school, my SAT Math scores were terrible, way below average. As a result, I had to take Math 095 (Intermediate Algebra) in college, which didn’t even count for credit. It wasn’t until the end of my freshmen year that I took calculus. After that first year I was hooked, and learned the joy of mathematics, I also realized that a lot of things I liked were enriched by learning some math. Rubiks Cubes, Computers, networks, 4-dimensional spaces, money, etc. However, even though I got really into math and eventually got a degree in it after 5 years, I did a great disservice to my (then) future self by ignoring math and my teachers.

As for the good, I remember arguing with my High School literature teacher about media, he was claiming that books were better than movies because they allow the reader to imagine the characters and settings in their own personal way. They also go much deeper into character development, something that is hard to match with a 90 minute movie. Even though I agree with these advantages, I wanted to be a contrarian and disagree with the teacher. I even came up with an argument as to why:

Since ‘a picture is worth a thousand words’, we can establish that:

Then, since movies play at 24fps (frames per second), that means that for every second of movie, there are 24 pictures, or 24,000 words. Also, movies average about 90 minutes, so that means that 1 movie = (24,000*90 words) = 2,160,000 words.

Next, I looked at the books he was assigning us: Of Mice and Men (46,750 words), The Bean Trees (58,000 words), Black Like Me (48,000 words), these books have an average of 50,916 words so we can calculate exactly how much better a movie is than these books:

Therefore, 1 movie ≈ 42 books. I had fun abusing proverbs to prove a point, and the teacher was amused, recognizing the humor.

I would like to help my son avoid some of the same mistakes I made and work hard where and when it matters. What’s ironic is that I worked hard on a pseudo-mathematical proof that movies are better than books, but I completely blew off my algebra homework.

How Contract Law Could Become a Form of Computing

Since 2012, when I first heard about Bitcoin, I’ve thought it was a very cool application of cryptography and peer-to-peer networks that solves the problem of double spending and runaway inflation. Other than that, I didn’t really think it was revolutionary, but a recent article by @ThoughtInfected has changed my mind.

The most thought-provoking quotes where:

It is just such a huge game changer that a program could hold wealth in a way that is inaccessible to anyone, and then distribute said wealth based on defined and agreed mathematical rules.

and

The twin technologies of cryptocurrencies and cryptocontracts are going to turn contract law into a programming language.

The bitcoin protocol includes a non-Turing complete interpreted language that can be used to create more complex transactions, and it can be used as a basis for so called ‘Smart Property’ and self-enforcing contracts.

This idea of turning contract law into a form of computing is similar to what I’ve been wanting for a while, I’d like to see laws themselves be in a computable form, then interpretation of law would be replaced with a program that might resemble a SQL query. What bitcoin smart contracts give is a way to enforce contractual obligations without paying lawyers and police, and they take out the need for trust, since people will be incapable of breaking the terms of the contract.

A beneficial side effect of having computable laws is the ability to cross check them all for logical consistency, my ideal government would find all inconsistencies and eliminate them by vote, any pair of laws that cannot be consistently resolved would be deleted, and the territory covered by those laws would be unspecified.

An example of this is the current inconsistency between Federal and State Law regarding the recreational use of cannabis, it is illegal at the Federal Level, but legal in some states, such as Colorado and Washington. If these laws were being checked like some continuous integration server running software tests, it would fail upon seeing this contradiction, it would generate a ballot and put it to a vote. If the vote does not resolve the inconsistency, the conflicting laws are deleted. Then legislators would be forced to start anew, applying principles that are consistent with the current body of law.

But back to contract law, this not only eliminates the need for lawyers and courts in contracts, it also solves the problem that DRM attempted to solve. Musicians could create contracts that ensured people paid for the song they were listening to, and it would be enforced by the mathematical rules built into the bitcoin network, not the arbitrary whim of a company like Sony. Or ebooks could be sold by the authors themselves, and people could only pay for what they read, this would obviate the need for a middleman like Amazon. Removing middlemen would give artists a larger cut, and could reduce the prices for the consumer as well.

Cryptocontracts such as those built on Bitcoin could really be revolutionary, since they sidestep the often expensive dealings with the legal system, don’t require trust, and solve the problem of property in an age when infomation is copied freely.

Switching Away From MathJax

I am switching away from MathJax for my math blogging for a few reasons, first one being that RSS readers won’t see rendered formulas, and second one being that rendering complex formulae such as tables of aligned equations can be very slow.

Instead, I’ve decided to use this Jekyll plugin to pre-render the formulae and insert images into the generated markup.

Counting Bits in Integers

While working on the code to count the number of fifteens I had in a hand in cribbage, I found it would be useful to count the number of bits in an integer. The comment below explains why it is useful.

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
// Fifteens
//     A Fifteen is any combination of cards whose ranks sum up to 15.
//
//     To find fifteens, we need to look at all combinations of cards.
//     For example, for a hand of three cards:  5♣  10♥  5♥  we must
//     consider all 2^3 - 1 = 7 non-empty subsets:
//        Hand         | Bits | Sum
//        -------------|------|-----
//                 5♥  | 001  |  (5)
//            10♥      | 010  | (10)
//            10♥  5♥  | 011  | (15)  *
//        5♣           | 100  |  (5)
//        5♣       5♥  | 101  | (10)
//        5♣  10♥      | 110  | (15)  *
//        5♣  10♥  5♥  | 111  | (20)
//
//     There is a well known correspondence betweeen subsets and binary
//     representations of integers, illustrated in the 'Bits' column above.
//     The number of bits that are equal to 1 is the cardinality of the 
//     corresponding subset.
//     Using this correspondence, we can enumerate all 2^n subsets by looping
//     an integer from 0 to (2^n - 1) and identifying the bits that are one
//     with the subset membership relation.
//
Card* subset[count];
for(i = 0; i < 2_TO_THE(count); ++i) {
    zero_cards(subset);

    // get bits of i
}

Since subsets and the bit representations of integers are in one-to-one correspondence, I can enumerate all subsets of an n-set by simply counting from 0 to 2n-1, then I can use the bits in the loop variable to determine which element of the set is in the subset. From the example in the comment above, you can see that the bits of the row number line up with the elements in the subsets.

In order to finish this code, I wanted a way to count the number of bits in an integer. I looked around for an existing algorithm to do it, and I found this, from K&R:

1
2
3
4
5
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++) {
    v &= v - 1; // clear the least significant bit set
}

I had no idea how it worked, so I tried to figure it out. The parts that I do understand are the roles of v and c, the former is the number for which we are counting bits, and the latter is the actual number of bits.

Why does v & (v-1) clear the least significant bit?

To figure this out, I considered a general n-bit integer, represented in base 2, I thought about it as

If v is odd, then vn = 1, so v-1 simply clears the least significant bit, and since the first n-1 bits are the same, the bitwise AND of v and v-1 is just v-1, which v with the least significant bit set to zero (cleared).

Otherwise, v is even, which means vn = 0. What is v-1 in this case?

If v = 32 = 1000002 (base 2), then v-1 = 0111112, so v&v-1 = 0000002, which is v with it’s least significant bit set to zero.

So far, so good, but that is only one example, we need to prove it for a general even n-bit integer, not just 32.

Let v be an n-bit even integer, and vk=1 is the least significant bit. Then vn=0, and k < n.

We can then write v in the following way:

Then, the number vkvk-1…vn = 2n-k

We can find v-1 by considering the subproblem of vkvk+1…vn - 1 = 2n-k-1.

Now, we can see that v and v-1 have the same first k-1 bits, with the last n-k+1 bits opposite, so that the bitwise AND clears the last n-k+1 bits. Since v has the last n-k bits equal to 0 and the k-th bit equal to one, it follows that v&(v-1) clears the least significant bit. This completes the proof.

Now, looking at the code again:

1
2
3
4
5
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++) {
    v &= v - 1; // clear the least significant bit set
}

This will clear the least significant bit, increment c, then if v is nonzero, repeat. Now this makes sense.

Political Parties Are More Like Tribes Than Consistent Philosophies

Much of political opinion is rationalized groupthink, this article argues this by using a list of 5 political proposals written from a liberal viewpoint, and then re-written from a conservative viewpoint, the results are telling.

No substantive policy change occurred, but many liberals supported the liberal-flavored list, while many conservatives rejected it. When the conservative-flavored version was written (same exact policies), that divide was inverted.

The response suggests that most people judged it based on how it was framed, and in particular, whether it was their group or the other group endorsed the idea. This is a good reason that political parties should be abolished, or at least worked around.

This could be solved by sterilizing ballots. Instead of seeing a candidate’s name, party, or see who endorsed what policy, several equivalent voting ballots could be written by different people. This would require that the candidate’s name is replaced with some other unique identifier, say a CIN (Candidate Identification Number). The CIN could be paired with a list of policies, each of which have been re-written by neutral parties (perhaps a machine compiled them from some computer model). Then, people would answer a questionairre about which policies they supported the most, along with a weight, assigned by the voter. Then, a program could calculate the closest match, and that would be the person’s vote.

One obvious problem with my proposal is that if the software that calculated the closest match was closed source, it would be very easy for software developers to rig it one way or another. Two solutions come to mind:

  • Make the voting software open source and submit it to a peer-review
  • Give the voter instructions on how to calculate the closest match, so that they can do it themselves, manually.

The options of using software or going manual are not mutually exclusive either. This is how people in the United States do their taxes, some delegate the calculations to software like TaxHawk or TurboTax, and some do it themselves with a calculator.

This proposal would solve the problem of tribal thinking in politics, and make voting a more logical activity that really did reflect the needs of the public.

I wrote about a similiar idea in 2012 to solve the problem of choosing the candidate you disliked the least,

Making people register with parties and then vote only exacerbates this, because they’ve made a commitment to a tribe before they’ve made a decision.