Blog de Bernard Opic

Algorithme de Luhn - Implémentation C++

24 July 2006 | Programmation

L’algorithme de Luhn permet de calculer la clé de contrôle d’un nombre à valider, ce qui s’avère très utile pour vérifier la cohérence de nombres tels que des numéros de cartes de crédits.

La procédure consiste à dérouler les phases suivantes :

1. doubler la valeur d’un chiffre sur deux en commençant par le premier à gauche
2. calculer la somme des chiffres composant la séquence ainsi obtenue
3. complémenter à 10 le chiffre des unités de la somme pour obtenir la clé

Prenons par exemple, une carte de crédit dont le numéro est 497010000030052 et calculons sa clé.

Phases	4	9		7				0		1		0		0		0		0		0		3		0		0		5		2
1	8	9		14				0		2		0		0		0		0		0		6		0		0		0		4
2	8	+	9	+	1	+	4	+	0	+	2	+	0	+	0	+	0	+	0	+	0	+	6	+	0	+	0	+	5	+	4	=	3	9
3																																		1

On complète ensuite le numéro de la carte de crédit avec la clé, ce qui donne le numéro 4970100000300521.

Voyons maintenant ce que peut donner le codage en C++ d’une fonction ‘luhn’ définie comme suit :

• un argument qui est un numéro de carte de crédit à vérifier, codé dans une chaîne de 16 caractères
• une valeur de renvoi qui vaut 1 si le numéro de carte de crédit est cohérent et 0 s’il ne l’est pas

Le but du jeu d’écrire le corps de la fonction en utilisant le moins de caractères significatifs possible, en privilégiant la compacité et la rapidité.

Dans la solution que je propose ci-dessous, je suis arrivé au résultat suivant :

• le code comptabilisé est constitué des 68 caractères significatifs de la suite d’instructions :
  int s=0,i=16,v;while(i–)v=*l++-’0′<9);return s%10<1;
• le temps d’exécution mesuré pour 1000000 d’itérations est de 0,09 secondes sur un AMD Athlon 2600+ sous Windows XP

Si vous avez des commentaires, des suggestions ou si vous avez une solution plus compacte ou plus rapide, n’hésitez pas à m’en faire part.

#include "stdafx.h"
#include <ctime>   

int luhn( char* l )   

{
    // début du code comptabilisé 

    int s=0, i=16, v; 

    while ( i-- )
         v = *l++ - '0' << i % 2,
         s += v - 9 * ( v > 9 ); 

    return s % 10 < 1; 

    // fin du code comptabilisé
}   

int _tmain(int argc, _TCHAR* argv[])
{
    clock_t start = clock();

    // début du temps d'exécution mesuré

    unsigned long l = 1000000L; 

    while ( l-- )
        luhn( "4970100000300521" );

    // fin du temps d'exécution mesuré   

    clock_t end = clock(); 

    printf( "Le temps d'exécution de la fonction est de %.2f secondes.\n", (float) ( end - start ) / (float) CLOCKS_PER_SEC ); 

    return 0;
}