doctorow reading sterling

cory doctorow is now reading bruce sterling's the hacker crackdown.

This book changed my life — and the lives of countless others. It inspired me politically, artistically and socially. Last week, I saw Bruce at his home in Serbia and asked him if he minded my reading this aloud for the next 20 weeks or so. He gave me his blessing — so here it is.

registering way low: orlowski

the register's andrew orlowski [who made a career by writing hack pieces on sun at every available opportunity] recently wrote a piece on a lessig debate on the value of copyright in the 21st century. alas, orlowski's usual rat-tat-tat innuendo and sound-effects reportage is completely dismantled by lessig's corrections. [as a side effect of this register piece, lessig posted a disclosure statement that is well worth reading.]

[orlowski's drivel on sun was the reason i stopped reading the drooling feather-bag a few years ago...]

markcc on behe's new old book

markCC has a detailed review focusing on the mathematics of behe's new old book: "the edge of evolution" [sorry no links to junk; i have skimmed the book long before this review, and decided it was an obnoxious re-thread of his earlier fiction, "darwin's black box"]:

... the new book is based on what comes down to a mathematical argument - a mathematical argument that I've specifically refuted on this blog numerous times. I'm not mentioning that because I expect Behe to read GM/BM and consider it as a serious source for his research; even if I were an expert in the subject (which I'm not), a blog is not a citable source for real research. But I mention it because the error is so simple, so fundamental, and so bleeding obvious that even a non-expert can explain what's wrong with it in a spare five minutes - but Behe, who apparently spent several years writing this book still can't see the problem. (In fact, one of the papers that he cites as support for this ridiculous theory contains the refutation!)

implementing the luhn checksum, differently

recently i came across some discussion and implementations of luhn's mod 10 checksum algorithm in comp.lang.scheme that puzzled me and piqued my interest. wikipedia has a useful entry including a straight-forward c# implementation based on an informal description, and pointers to other implementations.

alas, this description seems to have encouraged everyone to implement the algorithm more or less the same way, with minor variations: mostly right-to-left scan with a toggle to decide digit processing, but sometimes the string is reversed, or processed from left-to-right with a toggle. [some schemers have done the usual: convert string to a list of digits, reverse it and scan it with a toggle. cool!] wikipedia entry helpfully includes the pre-computed table to eliminate the unnecessary multiply/compare/subtract, but evidently this has gone unnoticed.

lunh checking again

here are some rather basic [for me anyway] observations on implementing the algorithm:

• if we know the size of the string, we know enough to scan the string left to right, without a toggle, without reversing or backwards [right to left] scanning.
• if the size of the string is even [eg. most credit card numbers] we can scan normally from left to right, two digits at a time, first one transformed, and next one untransformed.
• if the size of the string is odd, the first digit is always an untransformed digit. initialize the sum with this digit, and process the rest of the string normally [as above]
• if we do not have the size of the string, we can still check the string in a single left-to-right pass.

here is an implementation that uses the pre-calculated numeric transformation table, and a toggle-free left-to-right scan. [for simplicity, i excluded the isdigit check but assumed string length is not known in advance.]

static int ltab[] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

int
luhn(char *str) {
        int sum = 0;

        if (!str || !*str || !*(str + 1))
                return 0;   /* less than minimum */
        /*
         * if the length is odd, add the value of the
         * first digit and skip
         */
        if (strlen(str) & 1)
                sum = *str++ - '0';

        while (*str) {
                sum += ltab[*str++ - '0'];
                sum += *str++ - '0';
        }

        return (sum % 10) == 0;
}

even with isdigit check implemented as a first pass (during which we can also calculate the length of the string) this runs almost twice as fast as most naive implementations seen around.

suppose we do not know the string length in advance, and maybe it is costly to do multiple scans [assume many long strings or list of digits as some lispers would have it]. we want to see if a given string is (a) all numeric, and (b) passes the luhn checksum, all in a single pass. since we cannot decide if we have to perform the luhn transform for the first digit or not, we do it both ways and calculate two sums:

static int ltab[] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

/*
 * luhn without prior pass for string length
 */
int
luhn(const char *str) {
        int sum[2] = {0,0};
        int flip = 0;
        char c;

        if (!str || !*str || !*(str + 1))
                return 0;
        /*
         * calculate two alternating sums. we do not know
         * which one we will end up using until the end
         */
        while (c = *str++) {
                if (!isdigit(c))
                     return 0;
                int n = c - '0';
                sum[flip] += ltab[n];
                sum[flip = !flip] += n;
        }

        return (sum[flip] % 10) == 0;
}

luhn checking in awk and python

when i first decided to implement the algorithm, i used awk to prototype several of my approaches, including the two above. here is another approach with an extended lookup table that works well with awk and python and possibly with other scripting languages i like less.

# luhn - checks if a string of digits is a valid credit card number
# unlike other right-to-left scanning toggle and calculate
# implementations, this one does less than half the work
# author: ozan s. yigit
# insert bsd copyright here

BEGIN {
# generate all two digit sequences, with appropriate
# luhn translation of the first digit.

    for (i = 0; i < 10; i++)
        for (n = 0; n < 10; n++) {
        t = i * 2;
        if (t > 9)
            t = t - 9
        pairmap[i n] = t + n
    }
}

function luhn(digits,    sum, n, i)
{
    i = 1           # index
    sum = 0
    n = length(digits)
    # if the length is odd, save+skip the first char
    if ((n % 2) > 0)
        sum = substr(digits, i++, 1)

    while (i <= n) {
        pair = substr(digits, i, 2)
        ## print i ": ", pair, "->", pairmap[pair]
        sum += pairmap[pair]
        i += 2
    }
    ## print sum
    return sum % 10 == 0
}

/^[0-9]+$/ {
    if (luhn($0))
        print $0 ": ok."
    else
        print $0 ": no."
}

here is basically the same thing in python.

# author: ozan s. yigit
# insert bsd copyright here
pairmap = {
"00": 0, "01": 1, "02": 2, "03": 3, "04": 4, "05": 5, "06": 6, "07": 7,
"08": 8, "09": 9, "10": 2, "11": 3, "12": 4, "13": 5, "14": 6, "15": 7,
"16": 8, "17": 9, "18":10, "19":11, "20": 4, "21": 5, "22": 6, "23": 7,
"24": 8, "25": 9, "26":10, "27":11, "28":12, "29":13, "30": 6, "31": 7,
"32": 8, "33": 9, "34":10, "35":11, "36":12, "37":13, "38":14, "39":15,
"40": 8, "41": 9, "42":10, "43":11, "44":12, "45":13, "46":14, "47":15,
"48":16, "49":17, "50": 1, "51": 2, "52": 3, "53": 4, "54": 5, "55": 6,
"56": 7, "57": 8, "58": 9, "59":10, "60": 3, "61": 4, "62": 5, "63": 6,
"64": 7, "65": 8, "66": 9, "67":10, "68":11, "69":12, "70": 5, "71": 6,
"72": 7, "73": 8, "74": 9, "75":10, "76":11, "77":12, "78":13, "79":14,
"80": 7, "81": 8, "82": 9, "83":10, "84":11, "85":12, "86":13, "87":14,
"88":15, "89":16, "90": 9, "91":10, "92":11, "93":12, "94":13, "95":14,
"96":15, "97":16, "98":17, "99":18
}

def luhncheck(number):
    n = len(number)
    if n < 2:   # less than minimum
        return 0
    i = 0
    sum = 0
    if n & 1:   # odd length
        sum = int(number[i])
        i = 1

    while i < n:
        s = i
        i += 2
        ##      print number[s:i], "->", pairmap[number[s:i]]
        sum += pairmap[number[s:i]]

    return(sum % 10) == 0

## print luhncheck("1111")
## print luhncheck("8763")
## print luhncheck("446667651")
## print luhncheck("471036814")
## print luhncheck("23813103131311229292929228")

for fun luhn and duff

this is the fastest version of luhn checksum in C i happen to have. not surprisingly, it uses duff's device.

/*
* luhn check using duff's device
* author: ozan s. yigit
*/
static int ltab[] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

int luhn(char *str, int len)
{
        int sum = 0;
        int loop;

        if (len < 2)
                return 0;

#define LUHN    ltab[*str++ - '0']
#define NORM    *str++ - '0'

        loop = (len + 8 - 1) >> 3;

        switch (len & (8 - 1)) {
        case 0:
                do {
        sum += LUHN;
        case 7: sum += NORM;
        case 6: sum += LUHN;
        case 5: sum += NORM;
        case 4: sum += LUHN;
        case 3: sum += NORM;
        case 2: sum += LUHN;
        case 1: sum += NORM;
                } while (--loop);
        }

        return (sum % 10) == 0;
}

[notes: alas, code you see here is copyright. you can do anything you like with it so long as you give proper credit. (creative commons attribution, share alike) i usually leave trivial code of this sort in the public domain, but i am increasingly unhappy seeing public domain code being smothered with GPL that hides the original intent of its authors.
]

recently noted essays

both from peter norvig:
how to write a spelling corrector
mistakes in experimental design and interpretation

quote of the day

what would a non-fundamentalist atheist be? would he be someone who believed only somewhat that there are no supernatural entities in the universe - perhaps that there is only part of a god (a divine foot, say, or buttock)? or that gods exist only some of the time - say, wednesdays and saturdays? -- a. c. grayling [from can an atheist be fundamentalist in against all gods.]

recently noted quotes

certainly most xml i've seen makes me think i'm dyslexic. it also looks constipated, and two health problems in one standard is just too much. -- charles forsyth [9fans mailing list]

in OSS, eyeballs are very easily distracted. think of typewriting monkeys, but with more bananas and shorter attention span. -- anon [overheard in yet another "given enough eyeballs" theory discussion]

"nice try" is worthless. -- gregory house

"Playing God" is where you do absolutely nothing, take credit for other entities' work, and don't even exist — scientists don't aspire to such a useless status. Besides, creating life is mundane chemistry, no supernatural powers required. -- pz myers

it was music that went down to the feet by way of the pelvis without paying a call on mr brain. -- terry pratchett [soul music]

if there is anything worse than a movie hammered together out of pieces of bad screenplays, it's a movie made from the scraps of good ones. at least with the trash we don't have to suffer through the noble intentions. -- roger ebert [review of instinct]

nimoy can make anything sound plausible. -- philip k. dick ["introduction" to the golden man]

quick notes on mediocrities

shrek the third: alas, third time is the chasm; this movie is not just tired and unimaginative, it is actually boring; it is now the kind of movie the first shrek was gleefully making fun of. when you see your eight year old not laughing, and paying more attention to the popcorn bucket than the movie, you know you have a serious narrative flop. [with the money not wasted on this wreck, buy the animaniacs or pinky & brain dvd sets instead. your family will thank you for it.]

gray's anatomy: at one time, this used to be a guilty pleasure. now it is a classic soap that just happens to have a few good actors. they should leave the hospital, and the show should appropriately move to afternoon tea time, next to young and restless.

stephen harper [canadian prime minister, sadly]: this wooden pen pusher continues to receive accolades [especially around the pages of screamingly right wing national post] for assorted smart political feet shuffling. sort of the way we give high praise to a surgeon for the choice of music and a necktie during a heart [or a brain, in the case of canada] transplant surgery, even though he is drunk and can barely hold the blade. sigh.

macbook reg or pro: i would like to see one of those hodgman/long spots to make fun of the ridiculous power consumption and heat generation of the lovable macbooks. long could be in shorts with a sunburn, or actually spontaneously combust into flames... [oh how i miss my cooler powerbook]

recently noted quotes

gaze upon my opposable thumbs and fingers -- hugh neutron

two things every Python programmer needs to do in life: 1) Reinvent Lisp 2) Write a web framework -- Jason Huggins

Religious points of view must never be allowed to dictate public policy and limit fundamental freedoms. -- from CFI bulletin on gonzales vs carhart

If you work at IBM Global Services, ask your boss outright if you are on the list to be fired. It puts the boss in a bind, sure, but might lead to a sort of "Alice's Restaurant" effect in which hypocrisy is confronted and exposed. -- cringely [lean and mean]

You cannot, of course, gradually build a self-supporting, free-standing arch by using only the component stones, piling them up, one at a time. But if you have scaffolding – and a pile of rocks will suffice to support the growing structure – you can build the arch one stone at a time until the keystone is in place, and the structure becomes self-supporting. When this occurs, the (now redundant) scaffolding can be removed to leave the irreducibly complex, free-standing structure. -- niall shanks [God, The Devil, and Darwin: A Critique of Intelligent Design Theory]

it seems a few high school students are far smarter than the entire gang of evolution deniers at the Discovery Institute. -- pz myers [pharyngula]

Jini is a service architecture. OSGi is a service architecture. Both have ways of dealing with services written in Java. So why are there two?

This, of course, is a classic example of what I have called the Highlander Fallacy, which briefly stated is the principle that there can be only one. If any two technologies can be described using the same set of words, then there is no need for both of them, and only one will survive. I call this a fallacy because, to use a technical term, it is total crap. -- jim valdo [jini and osgi, yet again]

sharp reviews, interviews: scalpel

scalpel magazine is a sf/f/h review magazine that just launched. from its reviewerfesto:

Our purpose is to allow reviewers to utilize the rigor and tools of literary criticism in order to properly assess genre fiction, while discarding the elevated tone and reliance upon jargon that often mars academic criticism.
...
At Scalpel Magazine, we believe we are continuing a great tradition set into place by the likes of James Blish, Damon Knight, Algis Budrys and more.

i have my special integer. do you have yours?

ed felten is offering special 128-bit integers through his virtuallandgrab technology. i just picked mine, a really nice sequence with B8 and 8A...

1C FC BF 1A 62 B8 28 E1 B3 87 34 0E 4B CD 63 8A

thanks, ed.

stupidiest opening line of the day

found amongst the half-digested bits of news at the register: was gerry adams in the IRA? don't ask wikipedia

The wisdom of reliance on Wikipedia as an information source has been further questioned.

really. one can almost hear the anti-wikipedia rally outside reg offices on the matter. [what would we do without the wisdom of an information source that appropriately feeds on the rotted remains of imaginary magnitudes?]

related reading: is it worth being wise

on a leafless branch

a few years ago, i posted a fairly comprehensive collection of basho's crow haiku translations to my old blog. here is a new entry from an interesting recent collection by takafumi saito and william r. nelson, 1020 haiku in translation: the heart of basho, buson and issa

on a leafless branch
a crow -
autumn dusk.

i like the saito/nelson collection because of its excellent selection of poetry though i am a bit surprised by some of the unusual, at times ESL-like phrasing in its translations. for example:

the first snow
at a hermitage
happily i am.

march against dark ages and betrayal...

from today's toronto star, turkey split in bitter struggle:

At least 700,000 people marched against Foreign Minister Abdullah Gul's candidacy in Istanbul yesterday, waving the red national flag and invoking Turkey's long secular tradition. Powerful generals hinted they might step in to resolve the deadlock over Gul in parliament, which elects the president.

i wish i was at that march...

[reports from family members put the attendance numbers well over a million...]

recently noted quotes

You must not use ReiserFS v3 for your recordings. You will get corrupted recordings if you do. -- MythTV howto

my nephew kept saying he didn't want anything to do with fista. what is fista? is it a street gang thing? -- anonymous elderly

I've been using UNIX & Plan 9 for 26 years, and not once have I wanted to chop the tail off a file. -- tom duff (2000)

Many (open source) hackers are proud if they achieve large amounts of code, because they believe the more lines of code they've written, the more progress they have made. The more progress they have made, the more skilled they are. This is simply a delusion. -- suckless.org (about)

meat is food.
vegetables are what food eats.
fruits are vegetables that try to trick you by tasting good.
fish are fast moving vegetables.
mushrooms are what grows on vegetables after food is done with them.
-- source unknown [told by henry]

I asked why no recognized experts on radiometric dating were invited to participate in the conference, given that none of the speakers had any training or experience in experimental geochronology. He was candid enough to admit that they would have liked to included one on the team, but there are no young-earth geochronologists in the world. -- todd feeley [reporting from RATE (Radioisotopes and the Age of the Earth) creationist conference.]

the unfortunate and inevitable concomitant of "bring it on" is "how do you like it now?" -- david mamet [bambi vs godzilla]

recommended reading: security engineering

ross anderson's highly regarded [and somewhat expensive] book security engineering: a guide to building dependable distributed systems is now available online. there is even an audio book in progress.

some good new books in the library...

most anticipated books this month were hitchens's god is not great: how religion poisons everything, taner edis's An illusion of harmony: science and religion in islam and hofstadter's i am a strange loop. hitchens is proving to be one of the most important and stimulating reads of the year for me. edis's book is very familiar in many ways; turkey [author's and my country of birth] is a convenient and dominant source for the book, and i read some of the draft chapters last year. i thought he was pulling his punches a bit. [i like edis a lot. his previous ghost in the universe is an excellent addition to an atheist's library] alas, all this is taking my reading time away from the other 327 books on the pile... [but i shall first finish onfray's intensely sharp and entertaining Atheist Manifesto: The Case Against Christianity, Judaism, and Islam.]

recommended reading: mercurial book

a good book in progress: distributed revision control with mercurial by bryan o'sullivan. source code is in a mercurial repo at http://hg.serpentine.com/mercurial/book.

boing, boston, banned, boing, boing...

ah, of all places, this has to happen in boston...

recently noted quotes

an individual relates himself in action to his society through the use of tools that he actively masters, or by which he is passively acted upon. to the degree that he masters his tools, he can invest the world with his meaning; to the degree that he is mastered by his tools, the shape of the tool determines his own self-image. -- ivan d. illich (tools for conviviality)

you are coming to a sad realization. cancel or allowed? -- vista security guy

there is a little immaturity stuck away in the crannies of even the most judicious of us, and we should treasure it. -- roger ebert [review of the mummy]

there is music in everything, if you know how to find it. -- imp [terry pratchett, soul music]

It's always "but why do you want that" and "you don't want that" or "we can already do that" or "we tried that, it didn't work" and back to "but why do you want that". -- ron minnich (plan9 mailing list)

We all want our lenses to be tack sharp, period end period. -- bjørn rørslett

Unspeakable and unpronounceable Norwegian words, often with the odd Finnish phrase inserted, then rip apart the darkness around me. -- bjørn rørslett