Blog

Euler 7

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #7 statement is —

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

A sieve finds all the primes up to a limit in one pass. For the nth prime, n(logn+loglogn)n(\log n + \log\log n) is an upper bound when n6n \ge 6, so the sieve can be sized without guessing or repeatedly growing it.

from math import ceil, isqrt, log

n = 10_001
limit = ceil(n * (log(n) + log(log(n))))
sieve = bytearray(b"\x01") * (limit + 1)
sieve[:2] = b"\x00\x00"

for prime in range(2, isqrt(limit) + 1):
    if not sieve[prime]:
        continue

    start = prime * prime
    count = (limit - start) // prime + 1
    sieve[start : limit + 1 : prime] = b"\x00" * count

primes = (number for number, is_prime in enumerate(sieve) if is_prime)
for _ in range(n - 1):
    next(primes)

print(next(primes))

Multiples below prime * prime were already crossed out by smaller primes. The answer is 104743; for sieve limit LL, it runs in O(LloglogL)O(L\log\log L) time and O(L)O(L) space.

Gob on the Wire, for Now

I needed to pass structured measurements between two copies of a test program. Text was easy to inspect but tedious to parse, and writing a private binary format felt like volunteering to maintain archaeology.

The experimental Go library includes gob, which encodes typed values as a stream. In my current snapshot the package is imported simply as gob; its location and API may change before the language settles.

The sender is pleasantly small:

type Sample struct {
    Host  string
    Load  int
    Times []int64
}

enc := gob.NewEncoder(conn)
err := enc.Encode(Sample{"buildbox", 7, times})
if err != nil {
    return err
}

The receiver creates a decoder and supplies a destination value. Gob sends type information, then values using those types. Repeated values do not need to describe the complete structure each time, which makes a long-lived stream a better fit than many one-value connections.

Exported fields are the useful ones here. Private implementation details stay private, and fields are matched by name rather than by their physical offset in memory. That gives the decoder room to tolerate some structural evolution. It is not permission to change everything and hope.

I tried adding a field to the sender while leaving the old receiver alone. The old side ignored what it did not know. I then removed a field the receiver expected and got its zero value. That behavior is convenient for rolling experiments, provided zero has a sensible meaning.

Gob is Go-specific. I would not choose it for a public protocol consumed by C, Python, or an unknown implementation five years from now. Nor would I treat bytes emitted by today’s weekly snapshot as an archival format without tests against future toolchains.

For two cooperating Go programs built from a recorded snapshot, it removes a great deal of dull code. The mechanism is type description plus streamed values, not a dump of process memory, so pointers and machine layout are not being smuggled onto the wire. That is the right abstraction for this tool. The candid caveat is in the title: I am using it now, while keeping the protocol boundary small enough to replace later.

cgo Is a Border, Not a Bridge

I have too much useful C code to pretend a new language arrives on an empty disk. My first serious Go experiment therefore needed an old image-processing library. That led directly to cgo, then to several hours learning that a foreign-function interface is a border crossing, not a transparent bridge.

The smallest call is almost suspiciously simple. In the snapshot I used, a preamble before import "C" declares the C side:

package scale

/*
#include <stdint.h>

static uint32_t clamp(uint32_t v, uint32_t limit) {
    return v < limit ? v : limit;
}
*/
import "C"

func clamp(v, limit uint32) uint32 {
    return uint32(C.clamp(C.uint32_t(v), C.uint32_t(limit)))
}

The exact generated names and build steps are tied to this weekly release. cgo is changing quickly, so this is a field note rather than a durable manual. I run cgo as part of the package build, compile its generated C, then let the normal architecture-specific tools finish the package.

Scalar conversion is the easy part. Buffers force the real questions: who owns the memory, how long does an address remain valid, and may either runtime retain it after the call? I settled on a strict rule for this experiment: Go calls C synchronously, C consumes the supplied bytes before returning, and C stores no pointer into Go-managed memory.

For output allocated by the C library, I expose a C release function and call it with defer immediately after checking the returned pointer. That keeps allocation and release in the same ownership domain. Wrapping a C allocation in a Go slice may avoid a copy, but it also makes lifetime assumptions much easier to hide. I copy unless profiling proves the copy matters.

Strings are another ownership test disguised as convenience. A Go string is not a NUL-terminated C string. Conversion may allocate. Embedded zero bytes have C semantics whether I find them philosophically agreeable or not. Passing length explicitly is better whenever the C API permits it.

Then I measured the crossing. I called a trivial C function in a loop and compared it with the same arithmetic written in Go. The absolute figures are not worth publishing because both cgo and the compiler are moving, but the shape was obvious: crossing for every pixel was disastrous; crossing once per image was lost in the actual work.

That changed my wrapper. The first version exposed the C library nearly function for function:

Go pixel loop -> cgo -> C operation -> return

The revised version sends a whole row or image:

Go request -> cgo -> C loop over image -> return

The second interface is less “complete” and much more useful. It minimizes transitions and expresses the operation at the level where ownership is clear.

Callbacks in the other direction are harder. They combine scheduler state, foreign threads, and object lifetime. I avoided them by collecting results in C and returning a batch. That is not always possible, but it is a better starting point than assuming a C callback can enter arbitrary Go code safely. The runtime is young and its constraints deserve respect, not exploratory production outages.

Failures need translation too. The C library reports integer status codes and sometimes leaves detail in a structure. My wrapper converts those into a small Go value implementing the snapshot’s os.Error convention. I do not leak C constants throughout callers. If the library returns a partial result, the wrapper states whether that result remains valid and who frees it.

The build is the least elegant part. Header search paths, linker flags, and platform differences have not vanished; they have merely moved to the package boundary. This is still better than spreading them through the program, but cgo does not make a C dependency portable by blessing it with a comment.

I keep one integration test that allocates, calls, copies, releases, and repeats. It catches ownership regressions more reliably than staring harder at the wrapper.

My conclusion is deliberately conservative. cgo is excellent for preserving a tested, substantial C implementation. It is poor as a shortcut for tiny functions that cross the boundary constantly. Design a coarse interface, keep ownership explicit, translate failures once, and benchmark the complete operation. A border can support trade. It should not run through the middle of the kitchen.

Why can’t people buy newer cars in Argentina?

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.

Citroën 3cv

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.

Installing Go Code With goinstall

The new goinstall tool removes some Makefile work from small Go packages. Given an import path on a host it recognizes, it fetches the source, builds dependencies, and installs the package in the Go tree under GOROOT. This predates the workspace layout I keep wishing into existence.

For a package hosted on GitHub I can run:

$ goinstall github.com/rselbach/lines.git

GitHub is one of the repository hosts this version knows how to fetch, provided the repository name includes the .git suffix it expects. The import path is also the package identity: source lands below $GOROOT/src/pkg/github.com/rselbach/lines.git, and the installed archive goes into the corresponding package tree below $GOROOT/pkg. There is no GOPATH here yet.

This is early machinery. Repository conventions, supported fetch methods, command flags, and even package locations are changing between weekly snapshots. I would not encode today’s behavior into a company-wide build system without pinning the toolchain and keeping the escape hatch labeled.

It also does not solve version selection. Installing the latest source from a remote location is convenient for experiments and rather less comforting for reproducing a build six months later. For serious work I still record the exact revisions of the compiler and imported code.

Even with those caveats, goinstall saves the old fetching, directory arranging, dependency chasing, and archive copying dance. The machine can have that ritual; it will invent another soon enough.