I’ve got many gripes with the internet, I’ll admit. One of those is the overuse of Godwin’s Law. Actually, it’s a double offence because not only people overuse it, but this Law is anything but.

But let’s start with the misuse. I posted a while ago to Facebook that I had finished reading The Rise and Fall of the Third Reich and I mentioned how scary it was that a place right in the heart of “civilized” Europe could have fallen to that madness so quickly. A small discussion formed with some people until one of my geek friends commented something to the effect of—

Let’s stop this because Roberto already Godwinned in the original post!

You see, us geeks are good at that: repeating some meme without thinking much about them.

But that’s how I see “Godwin” being used all over the place. A discussion killer. And the discussion did get killed, unfortunately. It’s like Godwin’s Law says “if someone mentions Nazis, the discussion is over” but that’s not what the “law” says—

As an online discussion continues, the probability of a reference or comparison to Hitler or to Nazis approaches 1.

Which is actually true. Just like—

As an online discussion continues, the probability of a reference or comparison to Snow White and the Seven Dwarves approaches 1.

Obviously, as a discussion grows, the probability of referencing anything will approach 1! Here’s Godwin himself back in 2008 about his “law”—

Although deliberately framed as if it were a law of nature or of mathematics, its purpose has always been rhetorical and pedagogical: I wanted folks who glibly compared someone else to Hitler or to Nazis to think a bit harder about the Holocaust.

I find it ironic that his little experiment for making people think harder about the Holocaust is now used as a tool to avoid mentions to it.

You see, I get where Godwin was trying to go. You see glib comparisons with the Nazi all the time and yes, they suck. But going from that to making one of the most defining moments of the last Century completely off-limits is preposterous! Nazi comparisons are often valid and should not be avoided, especially by misusing an old usenet meme.

Again, His Godwinness—

Still, I sometimes have some ambivalence about the Law, which is far beyond my control these days. Like most parents, I’m frequently startled by the unexpected turn my 18-year-old offspring takes. […] When I saw the photographs from Abu Ghraib, for example, I understood instantly the connection between the humiliations inflicted there and the ones the Nazis imposed upon death camp inmates—but I am the one person in the world least able to draw attention to that valid comparison.

Avoiding comparing things to something as defining as Nazi Germany is an arbitrary limitation that makes no sense.

That’s not to say that all Nazi comparisons are valid. There really are plenty of dishonest Nazi comparisons out there, such as this one, by an American governor—

We the people have been told there is no choice. You must buy health insurance or pay the new Gestapo — the IRS.

This because the Supreme Court of the United States had upheld a law that represented the first steps of that country in following the rest of the civilized world in providing its citizens with basic healthcare. Healthcare! Oh the evils of that Gestapo!

But it’s unreasonable to expect people to completely ignore a huge part of our history in hope that dishonest governors won’t make silly comparisons, which they’ll do anyway.

This weekend I took the family to celebrate Father’s Day away from town. We went around getting to know parts of the province we live in and never been to.

We came back yesterday and the plan today was for a nice, calm day at home (it’s a holiday of some sort here.) Then I got engaged in a game called Hanging with Friends, a mix of the traditional hangman with a bit of Scrabble.

Since English isn’t my first language, I have a limited vocabulary, which leaves me at a disadvantage against my English-speaking friends. I can handle the “hangman” part of the game where I have to guess the word my friends come up with; but when it becomes “Scrabble” and I’ve got to form words using only a given set of letters and still make them difficult enough that a native English speaker will have problems figuring them out, then it’s tough.

An itch that needed some scratching. Enter Anagramizer.

When I woke up this morning, I decided to write a little program to help me. You call it cheating, I call it having a bit of nerd fun.

Being that I’m currently in love with Go, I decided to write in that language and it was really easy and quick to do it. It took me about half an hour to write the program that did what I needed. But then…

I succumbed to the temptation and started adding bells and whistles. Admittedly it was mostly for my own amusement and trying stuff in Go, but by the time we were leaving for lunch, the program had more options than the KDE audio volume utility (see what I did just there?)

I decided to make it available to anyone who wants to play with it. It served its purpose of entertaining me for about half a day :)

It’s now available on Github and released under a BSD licence.

I decided to take on Project Euler’s problem #10. Its statement goes like this:

The sum of the primes below 10 is [pmath]2 + 3 + 5 + 7 = 17[/pmath].

Find the sum of all the primes below two million.

My first attempt used brute force and testing primality using only previously found primes:

primes = []

def is_prime(n):
        if not (n < 2 or any(n % x == 0
           for x in filter(lambda x: x < math.ceil(n ** 2), primes))):
                primes.append(n)
                return True
        return False

sum_primes = 0
n = 1
while n < 2000000:
    if (is_prime(n)):
        sum_primes += n
    n += 1
print sum_primes

It worked if you consider an execution time of over 7 minutes reasonable. Clearly a bad solution. So I decided to rethink it a bit and tried again. This time, I decided to use a little creative thinking. For every number I tested for primality, I took the time to mark its multiples as not primes (when I first test, say, 3, I already know that [pmath]6, 9, 12, … n * 3 < 2000000[/pmath] will not be a prime numbers, so I don’t have to test their primality later.)

max_primes = 2000000
numbers = [0] * max_primes

def is_prime(n):
        if n <= 2:
                return True
        if numbers[n] == 1:
                return False
        c = 2
        m = 0
        while True:
                m = n * c
                if m < max_primes:
                        numbers[m] = 1
                else:
                        break
                c+= 1

        #if any(n % x == 0 for x in xrange(2, int(n ** 0.5) + 1)):
        i = 2
        while i < int(n** 0.5 + 1):
                if n % i == 0:
                        return False
                i += 1

        numbers[n] = 1
        return True

def sum_primes():
        soma = 0
        for i in range (2, max_primes):
                if is_prime(i):
                        soma += i
        return soma

print sum_primes()

This is a much better algorithm and it gave the correct result in 54 seconds. Project Euler has a “one-minute rule”, which state that all its problems should be solvable “on a modestly powered computer in less than one minute,” which means the solution applies. Still, it’s a brute force solution and I wanted a better one.

So today I picked my copy of Concrete Mathematics and read about primes. Honestly, I’ve been reading more about primes lately than I even thought I would.

Anyways, Knuth—yes, I know the book has three authors, but I can’t help thinking of it as a Knuth book—talks about several strategies to test primality, but it also mentions sieve algorithms that are used to generate lists of prime numbers. Exactly what I wanted!

def prime_list(limit):
        if limit < 2:
                return []
        sieve_size = limit / 2
        sieve = [True] * sieve_size

        for i in range(0, int(limit ** 0.5) / 2):
                if not sieve[i]:
                        continue
                for j in range((i * (i + 3) * 2) + 3, sieve_size, (i * 2) + 3):
                        sieve[j] = False

        primes = [2]
        primes.extend([(i * 2) + 3 for i in range(0, sieve_size) if sieve[i]])

        return primes

print reduce(lambda x,y: x+y, prime_list(2000000))

Et voilà! Correct result in 0.456s! The code is based on the description of the Sieve of Eratosthenes found in Concrete Mathematics. Also interesting to note, my idea in the second algorithm above is actually the basis of this sieve algorithm, I was just thinking “backwards.”

So I recently wrote an ugly solution to Project Euler’s problem #9. It was written in Python and even though every other Project Euler solution I wrote ran in less than one second, this one took over 18 seconds to get to the answer. Obviously it’s my fault for using a purely brute force algorithm.

Anyway, boredom is a great motivator and I just rewrote the exact same algorithm in C, just to see how much faster it would be.

#include <stdio.h>

int is_triplet(int a, int b, int c)
{
        return (((a < b) && (b < c)) && ((a * a + b * b) == (c * c)));
}

int main(void)
{
        for (int a = 0; a < 1000; a++)
                for (int b = a + 1; b < 1000; b++)
                        for (int c = b + 1; c < 1000; c++)
                                if ((a + b + c == 1000) && is_triplet(a, b, c)) {
                                        printf("%d %d %d = %dn", a, b, c,
                                               a * b * c);
                                        return 0;
                                }
}

It’s the exact same algorithm, but instead of 18 seconds, it ran in 0.072s.

Update: And here’s the version suggested by Gustavo Niemeyer:

#include <stdio.h>

int is_triplet(int a, int b, int c)
{
        return ((a * a + b * b) == (c * c));
}

int main(void)
{
        for (int a = 1; a < 1000; a++)
                for (int b = a + 1; b < (1000 - a) / 2; b++) {
                        int c = 1000 - a - b;
                        if (is_triplet(a, b, c)) {
                                printf("%d %d %d = %dn", a, b, c,
                                       a * b * c);
                                return 0;
                        }
                }
}

It now runs in 0.002s :–)

This is part of a series of posts about Argentina and the City of Cordoba. These are little facts I wish I knew about before I came here as an expat.

One of the first things I noticed when I arrived in Cordoba, Argentina, was the amount of old cars going around. And I’m not talking about 10-year-old cars, I’m talking about 30 years or so!

You can really find some rarities such as the Citroën 3cv happily racing around town all the time. As a consequence of all that, you can also find a disproportionate amount of cars stalled on the streets, people trying to do something under the hood. It’s really amazing how many broken down cars you’ll see every day.

I used to wonder why that was. Now I understand.

There is no credit in Argentina. Well, technically there is, but it’s so expensive that it’s as if it doesn’t exist. That’s why people normally need to buy stuff with cash upfront. Cars, of course, happen to be expensive and most people can’t save enough to buy newer cars like that. The same is true for several other goods, but cars happen to be the most visible symptom.

From time to time, coincidently around election time, the federal government creates some credit program. These programs are temporary and limited in the number of people who can apply.

And then there’s a second problem—informality. In order to avoid taxes and benefits, most companies hire people either with no documentation or with phoney pay information, e.g. if someone’s salary is, say, $1,000, the companies would register the employee as being paid $250 instead, thus being able to pay less taxes.

And thus even with those government credit programs, most people can’t even qualify as they can’t show enough income.