Sunday 3 November 2002

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

© Copyright 2002 Richard Allan Baruz. Last update: 12/5/02; 2:45:30 PM.