Фото кредитної картки для підвищення залученості (від Openclipart, автор Jmlevick)
Чи траплялося вам помилково ввести номер кредитної картки на сайті і миттєво отримати повідомлення про помилку? Досить зручно, правда? Але ось цікава частина — сайту не потрібно перевіряти з бекендом Visa чи Mastercard, щоб зрозуміти, що ви зробили помилку. "Масова перевірка бази даних" насправді вирішується за допомогою хитрої математики з 1950-х років, яку називають алгоритмом Луна (формула Луна). Той самий принцип використовують усюди — від номерів посвідчення особи та податкових номерів до VIN-кодів автомобілів і ISBN номерів — що дозволяє виявляти прості помилки набору, не здійснюючи жодного запиту до мережі.
"Магія", яка стоїть за цим, насправді дуже проста — це, по суті, хитрий контрольний підсумок, який виявляє найпоширеніші людські помилки: помилковий набір цифри або переміщення двох цифр місцями.
Ось як це насправді працює на практиці: припустимо, ви вводите номер вашої кредитної картки: 4532 9145 6789 0123. Остання цифра 3 є контрольним числом. Щоб перевірити правильність, починаємо з крайньої правої цифри і множимо кожну другу цифру на 2. Якщо результат множення дає двоцифрове число, ми додаємо ці цифри (або віднімаємо 9 — це не має значення). Потім ми підсумовуємо всі числа. Сума повинна бути кратною 10. Якщо це не так — ми виявили помилку.
Давайте розглянемо це крок за кроком.
Кредитна картка Visa — 4532 9145 6789 0123.
- Спочатку записуємо число справа наліво:
3 2 1 0 9 8 7 6 5 4 1 9 2 3 5 4 - Множимо кожну другу цифру на 2:
3 (2×2) 1 (0×2) 9 (8×2) 7 (6×2) 5 (4×2) 1 (9×2) 2 (3×2) 5 (4×2)
↓
3 4 1 0 9 16 7 12 5 8 1 18 2 6 5 8 - Додаємо цифри двоцифрових чисел, які більше 9:
16стає1+6 = 7(або16-9 = 7).
12стає1+2 = 3(або12-9 = 3).
"18" стає "1+8 = 9" (або "18-9 = 9"). - Тепер у нас є:
4 1 0 9 7 7 3 5 8 1 9 2 6 5 8. - Підсумовуємо всі цифри:
3+4+1+0+9+7+7+3+5+8+1+9+2+6+5+8 = 78. - Перевіряємо на кратність 10:
78 ÷ 10 = 7 залишок 8. - Не ділиться на 10, отже, це буде недійсне число!
Щоб зробити це число дійсним, потрібно змінити контрольну цифру з 3 на 5. У цьому випадку сума (5+4+1+0+9+7+7+3+5+8+1+9+2+6+5+8) = 80, що ділиться на 10 (80 ÷ 10 = 8 залишок 0). Формально, щоб обчислити контрольну цифру, потрібно обчислити загальну суму "вантажу" (залишок цифр), як зазвичай. Контрольна цифра потім дорівнює:
(10 - (TotalSumOfPayload mod 10)) mod 10.
Цікаво, як ця проста схема виявляє найбільш поширені помилки, які люди роблять при введенні чисел. Звісно, це не ідеально — деякі помилки можуть пройти непоміченими (наприклад,
Цей алгоритм не виявляє помилки типу 22 ↔ 55, 33 ↔ 66 або 44 ↔ 77), але для чогось, що обчислюється за наносекунди і не потребує зовнішньої перевірки, це досить добре.
Ось приклад простої (без обробки крайніх випадків) функції на C#, яка перевіряє число:
bool IsValid(string number)
{
var sum = 0;
// Починаємо з false, оскільки перша цифра (з права) є контрольним числом
var multipleBy2 = false;
// Обробляємо з права наліво
for (var i = number.Length - 1; i >= 0; i--)
{
var symbol = number[i];
// Пропускаємо пробіли (наприклад, між групами цифр)
if (char.IsWhiteSpace(symbol))
continue;
var digit = symbol - '0';
if (multipleBy2)
{
digit *= 2;
// Якщо результат > 9, віднімаємо 9 (це еквівалент підсумовування цифр)
// Приклад: 8 * 2 = 16 -> 1 + 6 = 7 -> або 16 - 9 = 7
if (digit > 9)
digit -= 9;
}
sum += digit;
multipleBy2 = !multipleBy2;
}
// Дійсне, якщо сума ділиться на 10
return sum % 10 == 0;
}
А ось приклад простої (без обробки крайніх випадків) функції на C#, яка генерує контрольну цифру для числа "payload":
int GenerateCheckDigit(string payload)
{
var sum = 0;
// Починаємо з true, оскільки перша цифра (з права) НЕ є контрольним числом
var multipleBy2 = true;
// Обробляємо з права наліво
for (var i = payload.Length - 1; i >= 0; i--)
{
var symbol = payload[i];
// Пропускаємо пробіли (наприклад, між групами цифр)
if (char.IsWhiteSpace(symbol))
continue;
var digit = symbol - '0';
if (multipleBy2)
{
digit *= 2;
// Якщо результат > 9, віднімаємо 9 (це еквівалент підсумовування цифр)
// Приклад: 8 * 2 = 16 -> 1 + 6 = 7 -> або 16 - 9 = 7
if (digit > 9)
digit -= 9;
}
sum += digit;
multipleBy2 = !multipleBy2;
}
// Обчислюємо контрольну цифру, яка зробить загальну суму кратною 10
return (10 - sum % 10) % 10;
}
Бонус, результати бенчмарку:
+ - - - - - - - - - -+- - - - - + - - - - -+- - - - - + - - - - - +
| Метод | Середнє | Помилка | Стандартне відхилення | Виділено пам'яті |
| - - - - - - - - - -| - - - - -| - - - - -| - - - - -| - - - - - |
| IsValid | 29.27 нс | 0.608 нс | 0.791 нс | - |
| GenerateCheckDigit | 31.09 нс | 0.639 нс | 1.120 нс | - |
+ - - - - - - - - - -+- - - - - + - - - - -+- - - - - + - - - - - +
Описаний алгоритм Луна насправді є специфічним випадком більш загального алгоритму Луна, де кожна позиція може мати своє власне значення ваги.
Хоча кредитні картки використовують чергування послідовності 1,2, інші системи застосовують різні послідовності ваг для виявлення різних типів помилок або для надання більш надійної перевірки.
Наприклад, Міжнародний стандарт номерів книг (ISBN-13) використовує чергування 1,3 для обчислення контрольної цифри, а Номери ідентифікації транспортних засобів (VIN) використовують більш складну систему ваг: 8,7,6,5,4,3,2,10,0,9,8,7,6,5,4,3,2.
Давайте подивимося, як це працює в загальному випадку:
- Кожній позиції в числі присвоюється вага.
- Кожну цифру множать на її відповідну вагу.
- Якщо результат більше 9, ми складаємо цифри числа (так само, як і в версії для кредитних карток).
- Підсумовуємо всі результати.
- Перевіряємо, чи ділиться загальна сума на обраний модуль (кредитні картки використовують 10).
Це все на зараз — побачимося наступного разу, коли ми заглибимося в інші заховані перлини повсякденних обчислень, які роблять наше цифрове життя трохи зручнішим.
Оригінальне джерело статті: https://www.npiontko.pro/2024/12/23/computation-efficient-rendezvous-hashing
Перекладено з: Luhn Algorithm: Credit Card Number Validation in Nanoseconds