?

Log in

Fast Luhn-digit generation algorithm - Journal new. [entries|archive|friends|userinfo]
microcoder

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Fast Luhn-digit generation algorithm [okt. 16-a, 2005|12:48 pm]
microcoder
[Tags|, ]
[Nuna humoro |relaxedrelaxed]
[Nuna muziko |Comalies (Lacuna Coil)]

I referenced the Luhn mod-10 check for credit card numbers in my last post.

The fastest implementation I'd encountered so far was my dad's, which was also pleasantly simple.

The weird part about the Luhn algorithm, from the point of view of a modern binary computer, is that it's oriented toward base-10 digits. One step of the algorithm doubles each second digit, and adds the digits of the result together until one digit remains. Popular with numerologists, but semi-complex if your data is in binary.

My dad simply built a table of 10 integers, containing the result of doubling-and-adding each possible digit — in other words, { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }. In hindsight, this is a pretty obvious optimization, but boy, does it speed things up.

I've taken it a step farther. Here's mine in pseudocode.

deltas := { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 }.
sum := the sum of all digits in the input.
for every other digit d in the input:
sum := sum + deltas[d].

check := 10 - (sum mod 10).


The deltas array contains the correction for doubling the digits — the difference between adding the digit straight, and adding it with the double-and-add algorithm.

In C, this is 150% faster than the original (already fast) implementations. It also lends itself reasonably well to Altivec optimization, not that it really matters, since the input data sets are so small.

The strange thing? I've seen a lot of Luhn implementations. I've never seen anyone do this. Weird.
LigiloRespondu al ĉi tiu

Comments:
From: (Anonymous)
2009-08-08 07:05 pm (UTC)

Cool algorithm

I tested quite a few, this was by far the fastest I found. I implemented it in C# here if anyone wants it:

http://orb-of-knowledge.blogspot.com/2009/08/extremely-fast-luhn-function-for-c.html
(Respondu al ĉi tiu) (Thread)
From: (Anonymous)
2011-01-23 04:22 am (UTC)

Clifton storage

Found your post exactly when it wasreally needed. Thanks to you. It's been recently extremely useful
(Respondu al ĉi tiu) (Thread)
From: (Anonymous)
2011-02-11 12:19 pm (UTC)

Google Sniper 2.0 Review

Hi dee hi! I am just fulfilled I finally located this fabulous website mainly because I really have been interested in it for a while as this is an immensely illuminating site. So I am planning to introduce myself right now. Now I am thirty-nine yrs. old in addition I'm working as some sort of astronomer. I really desire to experience video games including Legendary Axe II plus participate in sporting activities as soccer. My current activity is all about google sniper 2.0 Review. I browsed through a fascinating paper concerning this that says: A Search engines Sniper Only two method is the revolutionary type from the first The search engines colossal supplement the industry simple and very practical clear and understandable list of information only for an amateur and the Google Fantastic Only two technique is a simple realistic clear to see group of guidance after only any Novice web marketer. If you can't prefer to look at e-book you can view your video clips alternatively. Yahoo Killer A couple of technique is pertaining to taking relatively simple key phrases in order that you probably would not must hold out months in advance of finding any improvements. Search engines Mindblowing Couple of is solution to make money online, and it is a powerful way to start off. Is it the very best web marketing technique out there. I don't know whether this information is precise nevertheless it really reduced the problem with [url=http://www.squidoo.com/google-sniper-20-review]Google Sniper 2.0 review[/url].

So I'm most likely to devote lots of time here and I also wish I could locate a great number of interesting guidance. I am hoping I can even contribute to the information seen on this site. Many thanks for checking this out, enjoy yourself all!

(Respondu al ĉi tiu) (Thread)