[Snippets] Calculer le PGCD de plusieurs nombres

Publié le par

Une internaute a récemment demandé comment on pouvait calculer le PGCD de plusieurs nombres en utilisant T-SQL.
Amateur d’arithmétique, je me réjouissais de ce problème à résoudre.
Voici donc une implémentation de l’arithmétique nécessaire au calcul du PGCD de plusieurs nombres …

Il faut d’abord se rappeler comment on calcule le PGCD de deux nombres : c’est le dernier reste entier de la division euclidienne du plus grand par le plus petit des deux nombres, c’est à dire le modulo (a % b en SQL)

Mais aussi : (*)

- PGCD(a, b, …, n) = PGCD(PGCD(PGCD(a, b), …), n)
– PGCD(n, 0) = n

Dès lors implémentons une première fonction scalaire pour calculer le PGCD de deux nombres :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-------------------------------------------------------------------
-- Nicolas SOUQUET - 19/12/2008 - Calcule le PGCD de deux nombres -
-------------------------------------------------------------------
CREATE FUNCTION [dbo].[udf_Calcule_PGCD](@a INT, @b INT)
  RETURNS INT
AS
BEGIN
  DECLARE @pgcd INT
 
  IF @b = 0
    SET @pgcd = @a
  ELSE
  BEGIN
    DECLARE @r INT
    SET @r = @a % @b
    SELECT @pgcd = dbo.udf_Calcule_PGCD(@b, @r)
  END
 
  RETURN @pgcd
END
GO

Vérifions :

SELECT dbo.udf_Calcule_PGCD (1820, 1176) AS PGCD

Retourne :

PGCD
———–
28

Comment faire maintenant pour calculer le PGCD de plusieurs nombres ?
Nous allons combiner la récursivité proposée par les expressions de table commuunes, introduites par la norme SQL:2003 dans SQL Server 2005, et les propriétés de calcul du PGCD que j’ai marquées plus haut d’un astérisque.

Supposons la table suivante :

1
2
3
4
5
CREATE TABLE Tb_Test_PGCD
(
  Nombre INT
)
GO

Voici une procédure stockée permettant de calculer le PGCD de nombres qui seront stockés dans cette table :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
---------------------------------------------------------------------------------------------
-- Nicolas SOUQUET - 19/12/2008 - Calcule le PGCD des nombres stockés dans dbo.Tb_Test_PGCD -
---------------------------------------------------------------------------------------------
CREATE PROCEDURE usp_Calcule_PGCD
AS
BEGIN
  WITH
    -- Calcule un indice pour tous les nombres stockés
    -- dans la colonne "Nombre" de la table dbo.Tb_Test_PGCD
    CTE_Nombres AS
    (
      SELECT Nombre,
          ROW_NUMBER() OVER(ORDER BY Nombre DESC) Ordre
      FROM dbo.Tb_Test_PGCD
    ),
    -- Calcule récursivement le PGCD de tous les nombres stockés
    -- dans la colonne "Nombre" de la table dbo.Tb_Test_PGCD
    CTE_PGCD AS
    (
        -- Recherche du premier élément
        -- PGCD(n, 0 = n)
        SELECT dbo.udf_Calcule_PGCD(Nombre, 0) AS PGCD,
            1 AS Indice
        FROM CTE_Nombres
        WHERE Ordre = 1
      UNION ALL
        -- Parcours des autres valeurs de la colonne
        -- "Nombre" de la table dbo.Tb_Test_PGCD
        SELECT dbo.udf_Calcule_PGCD(PGCD, Nombre),
            Indice + 1
        FROM CTE_Nombres, CTE_PGCD
        WHERE Ordre = Indice
    ),
    CTE_MAX AS
    (
      -- Recherche de l'indice du dernier calcul
      -- Celui-ci a été incrémenté à chaque calcul de PGCD dans CTE_PGCD
      SELECT MAX(Indice) Indice
      FROM CTE_PGCD
    )
  -- Recherche du dernier calcul de PGCD dans CTE_PGCD => résultat
  SELECT CTE_PGCD.PGCD
  FROM CTE_PGCD
  JOIN CTE_MAX ON CTE_MAX.Indice = CTE_PGCD.Indice
END
GO

Effectuons quelques tests :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
------------------------------  
- Nicolas SOUQUET - 19/12/2008  
------------------------------  
SET NOCOUNT ON
GO
 
TRUNCATE TABLE dbo.Tb_Test_PGCD
GO
 
INSERT INTO dbo.Tb_Test_PGCD VALUES(1820)
INSERT INTO dbo.Tb_Test_PGCD VALUES(1176)
INSERT INTO dbo.Tb_Test_PGCD VALUES(700)
INSERT INTO dbo.Tb_Test_PGCD VALUES(9100)
GO
 
EXEC dbo.usp_Calcule_PGCD
GO
 
TRUNCATE TABLE dbo.Tb_Test_PGCD
GO
 
INSERT INTO dbo.Tb_Test_PGCD VALUES(18)
INSERT INTO dbo.Tb_Test_PGCD VALUES(15)
INSERT INTO dbo.Tb_Test_PGCD VALUES(21)
INSERT INTO dbo.Tb_Test_PGCD VALUES(36)
GO
 
EXEC dbo.usp_Calcule_PGCD
GO

Retourne successivement:

PGCD
———–
28

PGCD
———–
3

Une fois encore les expressions de table commune se sont montrées d’une redoutable efficacité.

Merci à Soazig pour ce problème ;)

ElSuket

Laisser un commentaire