6.29.2007

pencil marks

inimitable cosma shalizi, in different voices and those voices again
Q: So the analogy suggests that IQ scores are...?
A: A proxy for the skills and habits encouraged by a bureaucratic society; skills and habits which can be at once highly heritable (because of strong transmission through family and neighbors) and highly learned (within the scope of what it is biologically possible for humans to learn and internalize). Innate ability needn't enter into it at all. The implications for democracy would be nearly nil.

rolling stone, record industry's decline (part 1)
While there are factors outside of the labels' control -- from the rise of the Internet to the popularity of video games and DVDs -- many in the industry see the last seven years as a series of botched opportunities. And among the biggest, they say, was the labels' failure to address online piracy at the beginning by making peace with the first file-sharing service, Napster.

mark danner, a study in the rhetoric of george w. bush
What we can say is that if torture today remains a “scandal,” a “crisis,” it is a crisis in that same peculiar way that crime or AIDS or global warming are crises: that is, they are all things we have learned to live with.

6.28.2007

notes found in a recycling bin

recycled the text of the very, very strange larry wall talk titled perl, the first postmodern computer language, but not before reading the crunchy bits one last time. this quote seemed to jump at me:
recall that the essence of modernism is to take one cool idea and drive it into the ground.

reflecting on this in light of the once and future perl, it dawns on me that the essence of post/perl-modernism is to take many ideas, cool or not, and drive all of them into the ground, until a colorless puddle is formed.

recycled assorted past versions of suse documentation and media. once a favored now fading distro: so unwelcomed, so embarrassing. [my one machine that ran suse [briefly] is now running debian etch, and will soon run freebsd.]

o'reilly's cvs book. (poof!) i have no idea what this was doing on my bookshelf. it looks like i actually paid for it, which is sad.

recycled a b/w printout of a paul haeberli page on paper folding. this is from a very interesting [but now decade-old] graphics notebook called graphica obscura that used to be at sgi.com somewhere. it disappeared briefly and now re-appeared in its own site.

hmm, there goes some java program listings from my previous job. ah, here is the code i wrote to do [relatively trivial] application configuration using xml. [yep, some think this is a really good idea. i hated, hated, hated it.] i guess this needs to be shredded to tiny little pieces. this incidentally reminds me of a good essay by terence parr, titled humans should not have to grok XML.

6.27.2007

thom's compact camera challenge

thom hogan has an excellent note on the poverty of current compact camera designs and how it can be remedied. yes, nikon [or canon, or olympus or panasonic]: i would pay $450 for a compact that meets thom's design specifications.
Simply put: larger sensor, high-quality lens, and user control. Virtually every specification I list basically falls into those three categories, which tells you something about just how miserably the current crop of more than 60 million cameras being sold a year fails. The one thing that isn’t in those categories is a dedicated autofocus system (rather than double-purposing the imaging sensor as almost all current designs do), and this requirement basically points to the other failing of all current compact digital cameras: they aren’t responsive enough.

6.26.2007

recently noted quotes


along the way she mistook a cramped sense of of personal grievance for a coherent philosophy: a common error. -- mark kingwell on ayn rand [nearest thing to heaven]

a reasonable theist is a theist in violation of reason. -- david eller [natural atheism]

sitting in her own backyard in her bathrobe was one of those things that seemed worth the risk. not that she would have tried it unarmed - she wasn't that stupid. --p. j. tracy [monkeewrench]
[ps: this backyard is located in merriam park, st. paul]

I don't want to know what you think. I want you to think what I know. -- tom duff

idealists who begin sentences with, "can't we all just..." should have their guitars smashed and their flowers trampled. i don't want to buy the world a coke and live in perfect harmony; harmony means unanimity, and history shows unanimity is a scary thing. -- jay heinrichs [thank you for arguing]

Excuse my while I mop up the sake that I sputtered all over my keyboard… -- geoff arnold

I never recommend as policy a position that I have been paid, either directly or indirectly, to recommend. -- lawrence lessig [disclosure statement]

  • Most exciting ideas are not important,
  • Most important ideas are not exciting,
  • Not every problem has a good solution, and
  • Every solution has side effects.
  • -- dan geer [1994 usenix conference]

all idioms must be learned; good idioms need to be learned only once. -- alan cooper [about face: the essentials of interaction design]

6.25.2007

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...]

6.22.2007

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!)

6.21.2007

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.
]

6.11.2007

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.]

6.03.2007

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]