Sunday 3 November 2002

[Portland, by way of Steven Frank]
11:19:42 PM  #  comment []

By the way, today is the one-year anniversary of the TiBook. Er, my TiBook.

I know because I am struggling to register its APP before the end of the one-year cutoff. No go.

:.(

On a brighter note, OmniWeb seems to be picking up the Userland control for text editing, which Navigator does not. On a not-so-bright note, OW is still much slower than Chimera.
8:57:28 PM  #  comment []

Hoofah-toofah! That must be one ferocious Real Life that has Ravenwolf in its grip, ’cause it doesn’t seem quite inclined towards letting her go! I am sure she is fighting to get back to us, though. Cheer her on.

Mike is having problems with his G3 PowerBook (WallStreet). He thinks it’s his CPU card. I had trouble with OS X running on my Lombard because of a trickily jiggered RAM slot, myself, but it also froze up my OS 9 as well at times.

Paul has changed his domain and is writing a novel. I feel like giving him some constructive criticism, but perhaps it’s too early. I am still working on the sidebar link, but clicking this one above should be no problem.

Ken’s gone fishin’, which may or may not be secret code for moving house.

Happy Tutor seems to be on a Catholic jag, no doubt brought on by All Hallow’s Vespers, Matins, Lauds, Prime, Terce, et cetera.

Pinax (pinax?) has enough time on her hands to make me throw my hands up in despair. As Joshua Halberstam points out, and Aaron Haspel has been noting, my word-envy is reserved for attainable goals, like the 25k Bookworm word Mr. Frankenstein got. I can only shake my head in wonderment and resignation. Well, that, and throw my hands up in despair, as I was saying earlier.
8:29:37 PM  #  comment []

Benchmarking these Smalltalk Luhn implementations:

a _ [ :x | x isValidLuhn] . b _ [ :x | x isValidLuhn2]. interval _ (50000000000 to: 50000010000).

Time millisecondsToRun: [interval select: a] 18071

Time millisecondsToRun: [interval select: b] 28953

After tinkering around with both algorithms, I realized that keeping a running total is much faster. An even greater speed improvement is achieved by converting the ASCII character to its corresponding integer then subtracting 48, rather than converting to a string then converting the string to a number. So instead of aDigit asString asNumber, doing aDigit asInteger - 48 does better:

Time millisecondsToRun: [interval select: f] 4768

The naive implementation is easier to read, but three to four times less efficient, as it conses up a string from a character. Using (aDigit asInteger - $0 asInteger) might be a slightly more readable compromise. It seems like using a dynamically allocated Collection of any sort seems to be very bad for performance.

Combining the mapped doubled add-the-digits approach with the accumulator approach:

Integer>>isValidLuhn8

	| stream accOdd accEven anEven doubleMap |
	accOdd _ accEven _ 0.
	stream _ ReadStream on: self asString reverse.
	doubleMap _ #(0 2 4 6 8 1 3 5 7 9 ).
	[stream atEnd]
		whileFalse: [accOdd _ accOdd + stream next asInteger - $0 asInteger.
			anEven _ stream next.
			anEven
				ifNotNil: [accEven _ accEven
								+ (doubleMap at: anEven asInteger - $0 asInteger + 1)]].
	^ accOdd + accEven \ 10 = 0

...seems to yield really good performance (3.5 to 5.5 seconds for 10001 operations) on average, while being only slightly incomprehensible.
11:01:47 AM  #  comment []

I realized that since credit card numbers are valid Luhn numbers, I could test my algorithm against them. It works for my credit and debit cards, as well as my Waldenbooks Preferred Reader card (from the eighties), but not for my Barnes and Noble card number or the Replay card.

I tested the implementation against those, then another:

Integer>>isValidLuhn2

	| str accOdd accEven anEven |
	str := ReadStream on: self asString reverse.
	accOdd := Bag new.
	accEven := Bag new.
	[str atEnd]
		whileFalse: [accOdd add: str next asString asNumber.
			anEven := str next.
			anEven
				ifNotNil: [accEven add: anEven asString asNumber]].
	^ accOdd sum
		+ (accEven
				inject: 0
				into: [:x :y | (#(0 2 4 6 8 1 3 5 7 9 ) at: y + 1)
						+ x]) \ 10 = 0

12:41:32 AM  #  comment []