Skip to content

Instantly share code, notes, and snippets.

@kirked
Last active April 5, 2019 18:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kirked/3053f6c259bdd576805af8b156feb44c to your computer and use it in GitHub Desktop.
Save kirked/3053f6c259bdd576805af8b156feb44c to your computer and use it in GitHub Desktop.
Fast Luhn credit card check in Scala
final object Luhn {
/** An O(1) Map[Int, Int] of precomputed double values. */
private[this] final val doubles = Array(0, 2, 4, 6, 8, 1, 3, 5, 7, 9)
/**
* Validate a card using the Luhn algorithm with a single pass through the string,
* no other validation needed prior.
*
* Pure speed here (only 1 function call to get the byte array).
*/
final def check(card: String): Boolean = {
val bytes = card.getBytes("UTF-8")
val max = bytes.length
if (max < 10 || max > 19) false
else {
var sum = 0
var i = max - 1
var even = true
while (i >= 0) {
val n = bytes(i) - 0x30 // ASCII/UTF numeric digit range = 0x30 - 0x39
if (n < 0 || n > 9) return false // bail on non-numeric character, also range validation
else {
sum += (if (even) n else doubles(n))
even = !even
i -= 1
}
}
sum % 10 == 0
}
}
/**
* Validate a card using the Luhn algorithm with a single pass through the string,
* no other validation needed prior.
*
* Idiomatic code.
*/
final def checkIdiomatic(card: String): Boolean = {
if (card.length < 10 || card.length > 19) false
else {
val sum = card.reverseIterator.zipWithIndex.foldLeft(0) {
case (sum, (ch, i)) =>
val n = ch - 0x30 // ASCII/UTF numeric digit range = 0x30 - 0x39
if (n < 0 || n > 9) return false // bail on non-numeric character, also range validation
else sum + (if (i % 2 == 0) n else doubles(n))
}
sum % 10 == 0
}
}
}
@kirked
Copy link
Author

kirked commented Apr 5, 2019

On my Macbook Pro, JVM and code warmed-up:

time(Luhn.check("valid-card-number"), 1000)
1,000 iterations: 236,643 ns total, 236.64 avg, 178 ns min, 10,742 ns max, stddev = 384.5881

time(Luhn.check("invalid-card-number"), 1000)
1,000 iterations: 232,024 ns total, 232.02 avg, 173 ns min, 9,846 ns max, stddev = 355.2237
time(Luhn.checkIdiomatic("valid-card-number"), 1000)
1,000 iterations: 505,607 ns total, 505.61 avg, 407 ns min, 15,313 ns max, stddev = 531.7108

time(Luhn.checkIdiomatic("invalid-card-number"), 1000)
1,000 iterations: 465,138 ns total, 465.14 avg, 385 ns min, 29,142 ns max, stddev = 928.1494

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment