Newlib’s git repository

Because I had quite the time finding it when I wanted to submit a patch to newlib, there’s a git mirror of the canonical CVS repository for newlib, which all the patches I saw on the mailing list were based off of. Maybe somebody else looking for it will find this note useful:

git clone git://sourceware.org/git/newlib.git

See also: the original mailing list announcement of the mirror’s availability.

Matrioshka brains and IPv6: a thought experiment

Nich (one of my roommates) mentioned recently that discussion in his computer networking course this semester turned to IPv6 in a recent session, and we spent a short while coming up with interesting ways to consider the size of the IPv6 address pool.

Assuming 2128 available addresses (an overestimate since some number of them are reserved for certain uses and are not publicly routable), for example, there are more IPv6 addresses than there are (estimated) grains of sand on Earth by a factor of approximately \( 3 \times 10^{14} \) (Wolfram|Alpha says there are between 1020 and 1024 grains of sand on Earth).

A Matrioshka brain?

While Nich quickly lost interest in this diversion into math, I started venturing into cosmic scales to find numbers that compare to that very large address space. I eventually started attempting to do things with the total mass of the Solar System, at which point I made the connection to a Matrioshka brain.

“A what?” you might say. A Matrioshka brain is a megastructure composed of multiple nested Dyson spheres, themselves megastructures of orbiting solar-power satellites in density sufficient to capture most of a star’s energy output. A Matrioshka brain uses the captured energy to power computation at an incredible scale, probably to run an uploaded version of something evolved from contemporary civilization (compared to a more classical use of powering a laser death ray or something). Random note: a civilization capable of building a Dyson sphere would be at least Type II on the Kardashev scale. I find Charlie Stross’ novel Accelerando to be a particularly vivid example, beginning in a recognizable near-future sort of setting and eventually progressing into a Matrioshka brain-based civilization.

While the typical depiction of a Dyson sphere is a solid shell, it’s much more practical to build a swam of individual devices that together form a sort of soft shell, and this is how it’s approached in Accelerando, where the Solar System’s non-Solar mass is converted into “computronium”, effectively a Dyson swarm of processors with integrated thermal generators. By receiving energy from the sunward side and radiating waste heat to the next layer out, computation may be performed.

Let’s calculate

Okay, we’ve gotten definitions out of the way. Now, what I was actually pondering: how does the number of routable IPv6 addresses compare to an estimate of the number of computing devices there might be in a Matrioshka brain? That is, would IPv6 be sufficient as a routing protocol for such a network, and how many devices might that be?

A silicon wafer used for manufacturing electronics, looking into the near future, has a diameter of 450 millimeters and thickness of 925 micrometers (450mm wafers are not yet common, but mass-production processes for this size are being developed as the next standard). These wafers are effectively pure crystals of elemental (that is, monocrystalline) silicon, which are processed to become semiconductor integrated circuits. Our first target, then, will be to determine the mass of an ideal 450mm wafer.

First, we’ll need the volume of that wafer (since I was unable to find a precise number for a typical wafer’s mass):
$$ \pi \times \left( \frac{450 \;\mathrm{mm}}{2} \right)^2 \times 925 \;\mathrm{\mu m} = 147115 \;\mathrm{mm^3} $$
Given the wafer’s volume, we then need to find its density in order to calculate its mass. I’m no chemist, but I know enough to be dangerous in this instance. A little bit of research reveals that silicon crystals have the same structure as diamond, which is known as diamond cubic. It looks something like this:

Silicon crystal structure.

Now, this diagram is rather difficult to make sense of, and I struggled with a way to estimate the number of atoms in a given volume from that. A little more searching revealed a handy reference in a materials science textbook, however. The example I’ve linked here notes that there are 8 atoms per unit cell, which puts us in a useful position for further computation. Given that, the only remaining question is how large each unit cell is. That turns out to be provided by the crystal’s lattice constant.
According to the above reference, and supported by the same information from the ever-useful HyperPhysics, the lattice constant of silicon is 0.543 nanometers. With this knowledge in hand, we can compute the average volume per atom in a silicon crystal, since the crystal structure fits 8 atoms into a cube with sides 0.543 nanometers long.

$$ \frac{0.543^3 \mathrm{\frac{nm^3}{cell}}}{8 \mathrm{\frac{atoms}{cell}}} = .02001 \mathrm{\frac{nm^3}{atom}} $$

Now that we know the amount of space each atom (on average) takes up in this crystal, we can use the atomic mass of silicon to compute the density. Silicon’s atomic mass is 28.0855 atomic mass units, or about \( 4.66371 \times 10^{-23} \) grams.

$$ \frac{4.66371 \times 10^{-23} \mathrm{\frac{g}{atom}}}{.02001 \mathrm{\frac{nm^3}{atom}}} = 2.3307 \mathrm{\frac{g}{cm^3}} $$

Thus, we can easily compute the mass of a single wafer, given the volume we computed earlier.

$$ \frac{147115 \;\mathrm{mm}^3}{1000 \frac{mm^3}{cm^3}} \times 2.3307 \frac{g}{\mathrm{cm}^3} = 342.881 \;\mathrm{g} $$

Continue reading Matrioshka brains and IPv6: a thought experiment

“Four”ier transform

Today’s Saturday Morning Breakfast Cereal:
20130201
I liked the joke and am familiar enough with the math of working in unusual bases that I felt a need to implement a quick version of this in Python. Code follows.

#!/usr/bin/env python

def fourier(x, b):
    """Attempts to find a fourier version of x, working down from base b.

    Returns the fouriest base."""
    mostFours = 0
    bestBase = -1

    for base in range(b, 1, -1):
        fours = 0
        t = x
        while t != 0:
            if (t % base) == 4:
                fours += 1
            t //= base

        # Prefer lower bases
        if fours >= mostFours:
            print(baseconvert(x, base) + "_{0}".format(base))
            mostFours = fours
            bestBase = base

    return bestBase

BASE_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def baseconvert(x, base):
    s = ""
    while x != 0:
        s += BASE_CHARS[x % base]
        x //= base
    return ''.join(reversed(s))

if __name__ == '__main__':
    from sys import argv, exit
    if len(argv) < 2:
        print("""Usage: {0} number

Computes the "four"ier transform of , printing the optimizations to
reach the "fouriest" form.""".format(argv[0]))
        exit(1)

    x = int(argv[1])
    # Base 36 is the largest sensible base to use
    base = fourier(x, 36)

    if base == -1:
        print("{0} is four-prime!".format(x))

This is Python 3.x code, using explicit integer division. It should work under the 2.x series if you change line 34 to use “/=” rather than “//=”. It can only go up to base 36, because I didn’t want to deal with bases that are hard to represent in reasonable ways. Up to base 64 is an option, but in that case I would have wanted to use MIME base 64, which puts digits at positions 52 through 61, which would be confusing to read. Thus it only supports up to base 36, but could be adjusted with relative east to do larger bases.

Running a few examples:

$ python fourier.py 624
HC_36
HT_35
IC_34
IU_33
JG_32
K4_31
143_23
1B4_20
440_12
4444_5

$ python fourier.py 65535
1EKF_36
1IHF_35
1MNH_34
1R5U_33
1VVV_32
2661_31
2COF_30
2JQO_29
2RGF_28
38O6_27
3IOF_26
44LA_25
B44F_18
14640_15
4044120_5

$ python fourier.py 3
3 is four-prime!

A few quirks: it prefers lower bases, so bases that match earlier attempts in fouriness will be printed, despite having equal fouriness. I’ve decided to call values that have no representations containing a ‘4’ character “four-prime”, which is probably going to be a rare occurrence, but the program handles it okay.

Generalization of the algorithm is certainly possible, and basically requires changing the condition on line 14 to match different digit values. For example, a hypothetical “Three”ier transform would replace the ‘4’ on line 14 with a ‘3’.

Further reading

There’s a rather interesting discussion of the topic over on Reddit, as well as a few other implementations. (Thanks to Merth for pointing those out to me.)