Jasmine pour des tests en JavaScript

Copyright : Archia Oryix

Les tests unitaires sont des méthodes permettant de tester de façon unitaire des éléments d’un code source. Leur principal objectif est de vérifier le bon fonctionnement de sous-ensembles de code tels que les fonctions, les procédures, les classes, etc.. Les tests unitaires garantissent que ces éléments de base fonctionnent comme souhaité et préviennent des potentiels bugs.

Jasmine est un framework de tests open-source pour JavaScript. Il possède une syntaxe assez facile à prendre en main, finalement assez proche de RSpec pour Ruby, un framework dit Behaviour-Driven Development.

Appréhender la syntaxe de Jasmine

Une suite de tests Jasmine débute avec un appel à describe, une fonction globale de Jasmine qui prend en considération deux paramètres : une chaîne de caractères et une fonction. La chaîne de caractères représente un titre pour la suite, rappelant généralement ce qui va être testé. La fonction, quant à elle, est un bloc de code qui implémente la suite.

Les spécifications, appelées simplement specs, sont définies par l’appel de la fonction globale it de Jasmine, qui elle aussi prend en paramètre une chaîne de caractères et une fonction. La chaîne de caractères définit le test et la fonction est, à proprement parler, le test. Une spec peut contenir une à plusieurs attentes – expectations. En Jasmine, une expectation est une assertion pouvant être vraie ou fausse. Un test qui passe est un test possédant toutes ses expectations à true. Un test qui échoue possède au moins une expectation à false.

describe("My first suite", function() {
  it("contains spec with an expectation", function() {
    expect(true).toBe(true);
  });
});

Les blocs describe et it sont des fonctions. Celles-ci peuvent donc contenir tout le code nécessaire à l’exécution des tests. Les règles classiques de scope en JavaScript s’y appliquent ; ce qui signifie que toutes les variables déclarées dans un bloc describe seront disponibles dans chacun des blocs it que possède la suite.

describe("My first suite", function() {
  var a = true;

  it("contains spec with an expectation", function() {
    expect(a).toBe(true);
  });
});

Les expectations sont construites à partir de la fonction expect qui prend en argument une valeur, appelée la valeur réelle. Le tout est suivi d’une fonction dite matcher qui prend en argument la valeur attendue.

Before et After

Il est possible d’exécuter du code avant ou après chacune des specs écrites, respectivement grâce aux fonctionnalités beforeEach et afterEach. Cela peut devenir très pratique si l’on veut factoriser du code, ou si l’on utilise des variables globales que l’on soit réinitialiser après un test.

describe("My first suite with 'beforeEach' and 'afterEach'", function() {
  var a = 0;

  beforeEach(function() {
    a += 1;
  });

  afterEach(function() {
    a = 0;
  });

  it("checks the value of a", function() {
    expect(a).toEqual(1);
    a += 1;
  });

  it("expects a to still be equal to 1", function() {
    expect(a).toEqual(1);
  });
});

Il est également possible d’exécuter du code avant ou après toutes les specs contenues dans une suite. Comme le suggère son nom, la fonction beforeAll est appelée avant l’exécution de toutes les specs, et afterAll est appelée après l’exécution de toutes les specs.

describe("My first suite with 'beforeAll' and 'afterAll'", function() {
  var a;

  beforeAll(function() {
    a += 1;
  });

  afterAll(function() {
    a = 0;
  });

  it("checks the value of a", function() {
    expect(a).toEqual(1);
    a += 1;
  });

  it("does not reset a between specs", function() {
    expect(a).toEqual(2);
  });
});

Les matchers

Un matcher produit une comparaison booléenne entre la valeur réelle d’un élément et sa valeur attendue. Si ces deux valeurs sont divergentes, l’expectation est considérée comme fausse, et Jasmine fait échouer la spec.

Un matcher peut aussi être évalué avec une assertion négative. Il suffit pour cela d’ajouter le mot clé not avant l’utilisation du matcher.

describe("My first suite", function() {
  var a = true;

  it("contains spec with an expectation", function() {
    expect(a).not.toBe(false);
  });
});

Un grand nombre de matchers sont disponibles nativement dans Jasmine.

toBe

Le matcher toBe compare deux valeurs entre elles grâce à l’opérateur === en JavaScript.

describe("The 'toBe' matcher", function() {
  var a = 1,
      b = 2;

  it("compares with ===", function() {
    expect(a + b).toBe(3);
    expect(a).not.toBe(b);
  });
});

toEqual

Le matcher toEqual permet de vérifier l’équivalence de deux valeurs. toBe est donc plus strict que toEqual.

describe("The 'toEqual' matcher", function() {
  it("works with simple variables", function() {
    var a = 4;
    expect(a).toEqual(4);
  });

  it("works also well with arrays", function() {
    var b = new Array('1', '2'),
        c = new Array('1', '2');
    expect(b).toEqual(c);
  });
});

toMatch

Le matcher toMatch permet la comparaison avec les expressions régulières. Il permet de tester la bonne structure d’une valeur selon un pattern bien défini.

toMatch fonctionne également avec les chaînes de caractères, qui seront ensuite analysées comme des expressions régulières.

describe("The 'toMatch' matcher", function() {
  var message = "hello world!";

  it("compares with RegExp", function() {
    expect(message).toMatch(/^hello/);
    expect(message).toMatch("hello");
    expect(message).toMatch(/world!$/);
    expect(message).not.toMatch(/boy/);
  });
});

toBeNull

toBeNull permet de tester la nullité d’un élément. Si cet élément possède une valeur dite null, alors l’expectation sera considérée true. Le cas échéant, Jasmine fait échouer la spec.

describe("The 'toBeNull' matcher", function() {
  var a = null,
      b = "test";

  it("compares with null", function() {
    expect(a).toBeNull();
    expect(b).not.toBeNull();
  });
});

toContain

toContain permet de vérifier la présence d’un élément dans un tableau.

describe("The 'toContain' matcher", function() {
  var a = ["banana", "pineapple", "coconut"];

  it("finds an item in an Array", function() {
    expect(a).toContain("banana");
    expect(a).not.toContain("strawberry");
  });
});

toContain fonctionne également avec les chaînes de caractères : la fonction permet alors de vérifier si un ensemble de caractères figurent dans la chaîne globale.

describe("The 'toContain' matcher", function() {
  var a = "The quick brown fox jumps over the lazy dog";

  it("finds a substring in an String", function() {
    expect(a).toContain("fox");
    expect(a).not.toContain("foxy");
  });
});

toBeTruthy et toBeFalsy

Les matchers toBeTruthy et toBeFalsy permettent de tester de manière booléenne des valeurs. En JavaScript, tous types de valeurs peuvent être utilisés pour obtenir une valeur booléenne, par exemple lors de l’utilisation de la déclaration conditionnelle if.

Les valeurs suivantes seront interprétées comme étant false : undefined, null, false, 0, NaN et la chaîne de caractères vide "". Toutes les autres valeurs – objets et tableaux compris – sont considérées comme true. Les valeurs interprétées comme false sont appelées falsy, et les valeurs interprétées comme true sont appelées truthy.

Boolean(), appelé en tant que fonction, convertit son paramètre en booléen. Vous pouvez utiliser cette fonction pour savoir comment une valeur sera interprétée.

describe("The 'toBeTruthy' and 'toBeFalsy' matchers", function() {
  var a,
      b = false,
      c = 15;

  it("is for boolean casting testing", function() {
    expect(a).toBeFalsy();
    expect(a).not.toBeTruthy();
  });

  it("is for boolean casting testing", function() {
    expect(b).toBeFalsy();
    expect(b).not.toBeTruthy();
  });

  it("is for boolean casting testing", function() {
    expect(c).toBeTruthy();
    expect(c).not.toBeFalsy();
  });
});

toBeDefined et toBeUndefined

toBeDefined et toBeUndefined permettent de vérifier l’existence ou non d’une valeur. À noter une nouvelle fois que la valeur de type undefined est aussi considérée comme étant false.

En JavaScript, les variables non-initialisées ne possèdent pas de valeur, elles sont undefined. Une propriété inexistante pour un objet renvoie également une valeur dite undefined. Une fonction qui ne possède pas de return, ou une fonction possédant un return vide, est une fonction qui retourne undefined.

describe("The 'toBeDefined' and 'toBeUndefined' matchers", function() {
  var a,
      b = 3,
      c = (function() {})();

  it("compares against `defined`", function() {
    expect(a).not.toBeDefined();
    expect(b).toBeDefined();
    expect(c).not.toBeDefined();
  });

  it("compares against `undefined`", function() {
    expect(a).toBeUndefined();
    expect(b).not.toBeUndefined();
    expect(c).toBeUndefined();
  });
});

toBeLessThan et toBeGreaterThan

toBeGreaterThan et toBeLessThan permettent de vérifier si un élément est plus grand, ou s’il est plus petit, qu’un autre.

describe("The 'toBeLessThan' and 'toBeGreaterThan' matchers", function() {
  var a = 1,
      b = 2,
      c = 3;

  it("is for mathematical comparisons", function() {
    expect(a).toBeLessThan(b);
    expect(b).not.toBeGreaterThan(c);
    expect(c).not.toBeLessThan(a);
  });
});

toBeCloseTo

toBeCloseTo permet de vérifier si un nombre est proche d’un nombre, selon un certain nombre de décimales, donné en deuxième argument du matcher.

describe("The 'toBeCloseTo' matcher", function() {
  var a = 1.2,
      b = 1.25;

  it("is for precision math comparison", function() {
    expect(b).toBeCloseTo(a, 1);
    expect(b).not.toBeCloseTo(a, 2);
  });
});

En utilisant deux décimales dans l’exemple ci-dessous, toBeCloseTo considère que le deuxième chiffre décimal diffère pour les deux nombres choisis. Mettre le deuxième argument à 0 arrondit les nombres aux entiers.

toBeCloseTo est assez difficile à prendre en main. Je vous recommande de bien tester son comportement avant de le mettre en œuvre dans plusieurs de vos tests.

toThrow et toThrowError

toThrow permet de tester les erreurs. En utilisant ce matcher, Jasmine s’attend à recevoir une erreur, et c’est donc seulement en présence de celle-ci que la spec passera.

toThrowError permet de tester spécifiquement des erreurs. Ce matcher autorise en argument une expression régulière, une chaîne de caractères ou un type d’erreurs.

describe("The 'toThrow' matcher", function() {
  var f = function(){ throw new Error(); },
      g = function(){ throw new TypeError("I failed!"); };

  it("tests if a function throws an exception", function() {
    expect(f).toThrow();
  });

  it("tests a specific thrown exception", function() {
    expect(g).toThrowError(/fail/);
    expect(g).toThrowError("I");
    expect(g).toThrowError(TypeError);
  });
});

Des matchers personnalisés

Il est également possible de créer ses propres matchers. Il faut ajouter son matcher au sein du fichier contenant les specs qui doivent l’utiliser. Pour cela, il est possible d’utiliser beforeEach ou beforeAll.

Dans les versions de Jasmine supérieures à la 2.0, la fonction compare reçoit la valeur passée à la fonction expect comme étant son premier argument, la valeur réelle, et la valeur (si celle-ci existe) donnée au matcher comme étant son deuxième argument, la valeur attendue. Les matchers personnalisés prennent en argument deux paramètres : util, qui est un set de fonctions utiles pour les matchers, voir matchersUtil.js pour une liste détaillée ; et customEqualityTesters, qui a besoin d’être appelé si util.equals est utilisé.

Dans le cas présent ci-dessous, je crée un matcher ne prenant en considérant que la valeur réelle, actual, et je vérifie si celle-ci est paire grâce à util.equals. Cette fonction prend en paramètre la valeur réelle, la valeur attendue, et l’objet customEqualityTesters. La valeur réelle est ici, une opération avec modulo 2 qui consiste à vérifier si mon nombre est pair, et la valeur attendue est true. Si jamais cette opération donne un résultat égal à false, le matcher toBeEven me renvoie le message « Expected <number> to be even » et la spec échoue.

describe("The 'toBeEven' matcher", function() {
  beforeAll(function() {
    jasmine.addMatchers({
      toBeEven: function(util, customEqualityTesters) {
        return {
          compare: function(actual){
            return { pass: util.equals(actual%2==0, true, customEqualityTesters) }
          }
        }
        this.message = function() {
          return "Expected " + actual + " to be even";
        };
      }
    });
  });

  if('expects numbers to be even or not', function(){
    expect(2).toBeEven();
    expect(6857).not.toBeEven();
  });
});

Un peu de pratique est nécessaire pour bien comprendre comment mettre en place ses propres matchers. Mais vous verrez que les possibilités sont énormes, et que cela peut vous permettre d’avoir un code plus lisible si vos suites possèdent beaucoup de specs.

Écrire un premier test Jasmine

Ainsi, il est, par exemple, très simple de vérifier à l’aide de Jasmine, le bon comportement de la fonction du crible d’Eratosthenes présente ci-dessous. Cette fonction est censée retourner un tableau de tous les nombres premiers inférieurs à n.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();

  detectprimes[0] = false;
  detectprimes[1] = false;

  for(var i=2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  for(var p=2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      for(var j = p*p; j < n; j+= p)
        detectprimes[j] = false;
    }
  }

  for (var i = 0; i < n; i++)
    if(detectprimes[i]) primes.push(i);

  return primes;
}

Dans la suite créée, on souhaite obtenir un tableau de tous les nombres premiers en-dessous de 100. Pour cela, on utilise la fonction eratosthenes avec en paramètre le nombre 100.

Le test doit effectuer les vérifications suivantes. Ce tableau doit contenir 25 éléments. Parmi eux doivent figurer les nombres 5, 11, 43 et 97, choisis de façon totalement arbitraire. Mais les nombres 28, 60 et 99 ne doivent pas appartenir à ce tableau, car ils ne sont pas premiers.

describe('Prime numbers under 100 array', function(){
  var primes = eratosthenes(100);

  it('is truthy', function(){
    expect(primes).toBeTruthy();
  });

  it('is really an array', function(){
    expect(Array.isArray(primes)).toBe(true);
  });

  it('has 25 primes under 100', function(){
    expect(primes.length).toEqual(25);
  });

  it('contains 5, 11, 43, 97 as primes', function(){
    expect(primes).toContain(5);
    expect(primes).toContain(11);
    expect(primes).toContain(43);
    expect(primes).toContain(97);
  });

  it('does not contain 28, 60, 99', function(){
    expect(primes).not.toContain(28);
    expect(primes).not.toContain(60);
    expect(primes).not.toContain(99);
  });
});

Problème #3 du project Euler

Copyright : geir tønnessen

« The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ? »

Le troisième problème du projet Euler reprend les notions mathématiques de nombres premiers et de facteurs premiers. Un nombre premier est un nombre entier supérieur à 1 qui n’a pour diviseurs que 1 et lui-même.

Les facteurs premiers d’un nombre entier, quant à eux, sont l’ensemble des nombres premiers qui divisent entièrement cet entier. Par exemple, les facteurs premiers du nombre 70 sont 2, 5 et 7. Comme le décrit l’énoncé de ce problème, les facteurs premiers de 13 195 sont 5, 7, 13 et 29.

La factorisation en nombres premiers d’un entier peut également être exprimée à l’aide de puissances. En guise d’illustration, le nombre 300 peut se décomposer de la manière suivante : 2 x 2 x 3 x 5 x 5. Pour simplifier cette écriture, le carré est souvent utilisé : 2² x 3 x 5².

Algorithme de la solution

Pour trouver le plus grand des facteurs premiers d’un nombre entier x, on considère comme probable diviseur de ce nombre tous les entiers supérieurs à 1, 2 étant le premier des nombres premiers.

Si l’entier considéré divise entièrement x, on divise successivement x par ce nombre, jusqu’à que ce nombre ne soit plus un facteur de x. Cette opération garantit la primalité du nombre considéré car tous les plus petits facteurs de x auront d’ores-et-déjà été traités.

Une première écriture de cet algorithme donnerait le résultat suivant. La fonction obtenue s’exécute en 12.57 millisecondes sur mon ordinateur.

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 2;
  while(x > 1){
    // If k is a factor of x
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k++;
  }
  // Give the largest prime factor of x
  return largest;
}

Une première évolution de ce code serait de traiter le nombre 2 à part, car 2 est le seul nombre premier de valeur paire. Cela nous permet par la suite d’utiliser la même boucle, en incrémentant de 2 chaque potentiel candidat à être facteur. On testera donc de manière successive les nombres 3, 5, 7, etc..

Ce nouvel algorithme s’exécute en 3.22 millisecondes sur mon ordinateur.

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 3;
  // If 2 is a factor of x, we treat it separately...
  if(x % 2 == 0){
    x = x / 2;
    largest = 2;
    while(x % 2 == 0) x = x / 2;
  }
  // ... so we can increase factor with 2 every iteration
  while(x > 1){
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k += 2;
  }
  // Give the largest prime factor of x
  return largest;
}

Il est encore possible d’améliorer l’efficacité de cette fonction en considérant que chaque entier x ne peut avoir au maximum qu’un seul nombre premier supérieur à sa racine carrée.

Après avoir divisé de manière successive un des nombres premiers trouvés, on calcule la racine carré de la valeur restante de x. Si le facteur considéré est supérieur à la racine carrée de x, alors la valeur restante de x est le plus des grands des nombres premiers de x.

Cette nouvelle version s’exécute cette fois en 1.84 milliseconde chez moi !

function problem3(){
  var x = 600851475143,
      largest = 1,
      k = 3;
  // If 2 is a factor of x, we treat it separately...
  if(x % 2 == 0){
    x = x / 2;
    largest = 2;
    while(x % 2 == 0) x = x / 2;
  }
  // ... so we can increase factor with 2 every iteration
  // This loop runs only if k is not bigger than the square
  // root of the remaining x
  while(x > 1 && k<= Math.sqrt(x)){
    if(x % k == 0){
      largest = k;
      x = x / k;
      while(x % k == 0) x = x / k;
    }
    k += 2;
  }
  // Give the largest prime factor of x
  if(x == 1) return largest;
  else return x;
}

L’algorithme du sieve of Eratosthenes

Copyright : Fraser Mummery

Eratosthenes of Cyrene est un mathématicien, géographe, poète, astronome et théoricien de la musique né en Grèce antique. Il a été un grand penseur, à l’origine notamment des premières cartes représentatives du monde, tel que celui-ci était connu à l’époque. C’est à lui que l’on doit entre autres, le jour bissextile (le 29 février), de nombreuses découvertes en matière de géographie dont une approximation raisonnable du diamètre de la Terre, et le fameux crible d’Ératosthène.

Cet algorithme est une manière efficace de retrouver tous les nombres premiers. Celui-ci consiste à tester la primalité des nombres de 2 à n selon la méthode décrite ci-après.

L’algorithme du crible d’Ératosthène décrypté

Considérons une liste de nombres entiers de 2 à n, 2 étant le premier des nombres premiers. On récupère tous les multiples de 2 appartenant à cette liste, et on les marque comme étant non premiers : par définition, tout multiple de 2 est divisible par 2. Le multiple d’un nombre ne peut donc pas être premier.

On cherche ensuite le premier des nombres supérieurs à 2 n’étant pas marqué dans la liste, et on répète la précédente instruction, à savoir marquer comme étant non premiers tous les multiples de ce nombre. On récupère ainsi le nombre 3 et on parcourt ses multiples afin de les marquer comme nombre non premier.

Chacune de ces opérations est répétée jusqu’à ce que l’on arrive à la limite de cette liste, le nombre n. Quand l’algorithme se termine, tous les nombres qui n’auront pas été marqués dans la liste constituent la séquence de nombres premiers inférieurs à n.

Animation of the Sieve of Eratosthenes

Chacun des nombres restants une fois l’algorithme terminé est nécessairement nombre premier, car tous les multiples des nombres inférieurs auront déjà été marqués. Il se peut, par ailleurs, qu’un multiple ait déjà été marqué : c’est le cas du nombre 6 par exemple. Ce nombre est marqué originellement comme étant non premier car il est multiple de 2. 6 étant également multiple de 3, il pourrait éventuellement être marqué une deuxième fois.

Une évolution de l’algorithme énoncé ci-dessus serait de commencer à marquer tous les multiples d’un nombre premier à partir du carré de celui-ci, car tous les plus petits multiples de celui-ci auront d’ores-et-déjà été marqués. Cela signifie aussi que l’algorithme peut se terminer lorsque le carré d’un des nombres premiers trouvés est supérieurs à n.

…en JavaScript

Ci-dessous, une des écritures possibles de cet algorithme en JavaScript, permettant d’obtenir tous les nombres premiers inférieurs à n. detectprimes est un tableau de n booléens. On attribue la valeur true à l’ensemble des nombres de 2 à n, 0 et 1 ne faisant pas partie de cet ensemble sont initialisés avec la valeur false.

Une boucle for est mise en place, avec une limite de √n. À chaque nouvelle itération sur le tableau de n nombres, on vérifie si p est premier – si p est égal à true – et seulement à cette condition, on évalue tous les multiples de p supérieurs au carré de p, afin de les marquer à false, comme étant non premiers donc.

Il ne reste ensuite qu’à parcourir les éléments du tableau detectprimes, afin de récupérer tous les nombres premiers inférieurs à n.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      for(var j = p*p; j < n; j += p)
        detectprimes[j] = false;
    }
  }

  // Get all the prime numbers
  for (var i = 0; i < n; i++)
    if(detectprimes[i]) primes.push(i);
  return primes;
}

Pour vérifier le bon comportement de la fonction que je vous propose, voici une représentation textuelle de l'image qui schématise l'algorithme proposé par Ératosthène.

En exécutant le code présent ci-après, vous pourrez mieux appréhender le déroulement du crible d'Ératosthène. Cette nouvelle version, proposant des commentaires, à l'aide de console.log est bien évidemment moins efficace en terme de performance, mais vous permettra de suivre chacun des tests effectués à chacune des itérations de la boucle.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();
  console.log('I want to know which numbers below ' + n + ' are primes.');

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      console.log(p + ' is a prime, let\'s mark all its multiples below ' + n + '.');
      for(var j = p*p; j < n; j += p){
        console.log(j + ' is a multiple of '+p+', so ' + j + ' is not a prime.');
        detectprimes[j] = false;
      }
    }else{
      console.log(p + ' is not a prime, so the loop continues.');     
    }
  }
  console.log(p + ' is not smaller than ' + Math.sqrt(n) + ': end of the loop.');

  // Get all the prime numbers
  var _text = 'The primes below ' + n + ' are: ';
  for (var k = 0; k < n; k++) {
    if (detectprimes[k]) {
      primes.push(k);
      if (primes.length == 1) _text += k;
      else _text += ', ' + k;
    }
  }
  console.info(_text + '.');
  return primes;
}
eratosthenes(121);

Vous aurez dans votre console la sortie suivante :

I want to know which numbers below 121 are primes.

2 is a prime, let’s mark all its multiples below 121.
4 is a multiple of 2, so 4 is not a prime.
6 is a multiple of 2, so 6 is not a prime.
8 is a multiple of 2, so 8 is not a prime.
10 is a multiple of 2, so 10 is not a prime.
12 is a multiple of 2, so 12 is not a prime.
14 is a multiple of 2, so 14 is not a prime.
16 is a multiple of 2, so 16 is not a prime.
18 is a multiple of 2, so 18 is not a prime.
20 is a multiple of 2, so 20 is not a prime.
22 is a multiple of 2, so 22 is not a prime.
24 is a multiple of 2, so 24 is not a prime.
26 is a multiple of 2, so 26 is not a prime.
28 is a multiple of 2, so 28 is not a prime.
30 is a multiple of 2, so 30 is not a prime.
32 is a multiple of 2, so 32 is not a prime.
34 is a multiple of 2, so 34 is not a prime.
36 is a multiple of 2, so 36 is not a prime.
38 is a multiple of 2, so 38 is not a prime.
40 is a multiple of 2, so 40 is not a prime.
42 is a multiple of 2, so 42 is not a prime.
44 is a multiple of 2, so 44 is not a prime.
46 is a multiple of 2, so 46 is not a prime.
48 is a multiple of 2, so 48 is not a prime.
50 is a multiple of 2, so 50 is not a prime.
52 is a multiple of 2, so 52 is not a prime.
54 is a multiple of 2, so 54 is not a prime.
56 is a multiple of 2, so 56 is not a prime.
58 is a multiple of 2, so 58 is not a prime.
60 is a multiple of 2, so 60 is not a prime.
62 is a multiple of 2, so 62 is not a prime.
64 is a multiple of 2, so 64 is not a prime.
66 is a multiple of 2, so 66 is not a prime.
68 is a multiple of 2, so 68 is not a prime.
70 is a multiple of 2, so 70 is not a prime.
72 is a multiple of 2, so 72 is not a prime.
74 is a multiple of 2, so 74 is not a prime.
76 is a multiple of 2, so 76 is not a prime.
78 is a multiple of 2, so 78 is not a prime.
80 is a multiple of 2, so 80 is not a prime.
82 is a multiple of 2, so 82 is not a prime.
84 is a multiple of 2, so 84 is not a prime.
86 is a multiple of 2, so 86 is not a prime.
88 is a multiple of 2, so 88 is not a prime.
90 is a multiple of 2, so 90 is not a prime.
92 is a multiple of 2, so 92 is not a prime.
94 is a multiple of 2, so 94 is not a prime.
96 is a multiple of 2, so 96 is not a prime.
98 is a multiple of 2, so 98 is not a prime.
100 is a multiple of 2, so 100 is not a prime.
102 is a multiple of 2, so 102 is not a prime.
104 is a multiple of 2, so 104 is not a prime.
106 is a multiple of 2, so 106 is not a prime.
108 is a multiple of 2, so 108 is not a prime.
110 is a multiple of 2, so 110 is not a prime.
112 is a multiple of 2, so 112 is not a prime.
114 is a multiple of 2, so 114 is not a prime.
116 is a multiple of 2, so 116 is not a prime.
118 is a multiple of 2, so 118 is not a prime.
120 is a multiple of 2, so 120 is not a prime.

3 is a prime, let’s mark all its multiples below 121.
9 is a multiple of 3, so 9 is not a prime.
12 is a multiple of 3, so 12 is not a prime.
15 is a multiple of 3, so 15 is not a prime.
18 is a multiple of 3, so 18 is not a prime.
21 is a multiple of 3, so 21 is not a prime.
24 is a multiple of 3, so 24 is not a prime.
27 is a multiple of 3, so 27 is not a prime.
30 is a multiple of 3, so 30 is not a prime.
33 is a multiple of 3, so 33 is not a prime.
36 is a multiple of 3, so 36 is not a prime.
39 is a multiple of 3, so 39 is not a prime.
42 is a multiple of 3, so 42 is not a prime.
45 is a multiple of 3, so 45 is not a prime.
48 is a multiple of 3, so 48 is not a prime.
51 is a multiple of 3, so 51 is not a prime.
54 is a multiple of 3, so 54 is not a prime.
57 is a multiple of 3, so 57 is not a prime.
60 is a multiple of 3, so 60 is not a prime.
63 is a multiple of 3, so 63 is not a prime.
66 is a multiple of 3, so 66 is not a prime.
69 is a multiple of 3, so 69 is not a prime.
72 is a multiple of 3, so 72 is not a prime.
75 is a multiple of 3, so 75 is not a prime.
78 is a multiple of 3, so 78 is not a prime.
81 is a multiple of 3, so 81 is not a prime.
84 is a multiple of 3, so 84 is not a prime.
87 is a multiple of 3, so 87 is not a prime.
90 is a multiple of 3, so 90 is not a prime.
93 is a multiple of 3, so 93 is not a prime.
96 is a multiple of 3, so 96 is not a prime.
99 is a multiple of 3, so 99 is not a prime.
102 is a multiple of 3, so 102 is not a prime.
105 is a multiple of 3, so 105 is not a prime.
108 is a multiple of 3, so 108 is not a prime.
111 is a multiple of 3, so 111 is not a prime.
114 is a multiple of 3, so 114 is not a prime.
117 is a multiple of 3, so 117 is not a prime.
120 is a multiple of 3, so 120 is not a prime.

4 is not a prime, so the loop continues.

5 is a prime, let’s mark all its multiples below 121
25 is a multiple of 5, so 25 is not a prime.
30 is a multiple of 5, so 30 is not a prime.
35 is a multiple of 5, so 35 is not a prime.
40 is a multiple of 5, so 40 is not a prime.
45 is a multiple of 5, so 45 is not a prime.
50 is a multiple of 5, so 50 is not a prime.
55 is a multiple of 5, so 55 is not a prime.
60 is a multiple of 5, so 60 is not a prime.
65 is a multiple of 5, so 65 is not a prime.
70 is a multiple of 5, so 70 is not a prime.
75 is a multiple of 5, so 75 is not a prime.
80 is a multiple of 5, so 80 is not a prime.
85 is a multiple of 5, so 85 is not a prime.

90 is a multiple of 5, so 90 is not a prime.
95 is a multiple of 5, so 95 is not a prime.
100 is a multiple of 5, so 100 is not a prime.
105 is a multiple of 5, so 105 is not a prime.
110 is a multiple of 5, so 110 is not a prime.
115 is a multiple of 5, so 115 is not a prime.
120 is a multiple of 5, so 120 is not a prime.

6 is not a prime, so the loop continues.

7 is a prime, let’s mark all its multiples below 121.
49 is a multiple of 7, so 49 is not a prime.
56 is a multiple of 7, so 56 is not a prime.
63 is a multiple of 7, so 63 is not a prime.
70 is a multiple of 7, so 70 is not a prime.
77 is a multiple of 7, so 77 is not a prime.
84 is a multiple of 7, so 84 is not a prime.
91 is a multiple of 7, so 91 is not a prime.
98 is a multiple of 7, so 98 is not a prime.
105 is a multiple of 7, so 105 is not a prime.
112 is a multiple of 7, so 112 is not a prime.
119 is a multiple of 7, so 119 is not a prime.

8 is not a prime, so the loop continues.

9 is not a prime, so the loop continues.

10 is not a prime, so the loop continues.

11 is not smaller than 11, end of the loop.

The primes below 121 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.

Pour aller plus loin : bien d'autres algorithmes proposent de récupérer l'ensemble des nombres premiers, d'autres mêmes jugés encore plus rapides d'exécution que le crible d'Ératosthène comme le sieve of Atkins ou encore le sieve of Sundaram, pour ne citer qu'eux.

Mais le sieve of Eratosthenes que je vous propose aujourd'hui est l'un des plus simples à écrire, et il a la particularité de dater du IIIème siècle avant Jésus-Christ, une prouesse mathématique pour l'époque !

Problème #2 du project Euler

Copyright : Michæl Paukner

« Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. »

Afin de résoudre ce problème du projet Euler, il est important, dans un premier temps, de se consacrer à l’appréhension de ce que ce sont les séquences Fibonacci. En mathématiques, la séquence Fibonacci se définit comme une séquence dans laquelle chaque nombre est obtenu en effectuant la somme des deux termes précédents.

La formule mathématique associée est donc la suivante : F(n) = F(n-1) + F(n-2) avec F(0) = 0 et F(1) = 1. On appelle F(0) et F(1) les termes initiaux de cette suite logique, ceux qui permettent d’en déduire les nombres suivants. Les nombres Fibonacci constituent la séquence A000045 sur The On-line Encyclopedia of Integer Sequences. Ci-dessous sont représentés les vingt premiers termes de la séquence Fibonacci.

F(0) F(1) F(2) F(3) F(4)
0 1 1 2 3
F(5) F(6) F(7) F(8) F(9)
5 8 13 21 34
F(10) F(11) F(12) F(13) F(14)
55 89 144 233 377
F(15) F(16) F(17) F(18) F(19)
610 987 1 597 2 584 4 181

L’énoncé du problème #2 du projet Euler nous propose de trouver la somme de toutes les valeurs paires n’excédant pas 4 000 000. Il s’agit donc de considérer la séquence Fibonacci, de telle sorte qu’à chaque nouveau terme étant pair, celui-ci est ajouté à une variable sum, dont la valeur ne cessera d’augmenter que lorsque l’on aura atteint la limite proposée, égale à 4 000 000.

Les deux termes initiaux de la séquence Fibonacci sont représentés ci-dessous par les variables x et y respectivement égales à 0 et à 1. Ces variables possèdent une valeur croissante dans le temps à la condition que la variable y, représentant systématiquement le deuxième terme à un instant t, ne dépasse jamais la limite imposée. Une variable intermédiaire temp calcule le troisième terme créé à partir de la somme de x et y. x, premier terme de la séquence à un instant t, devient alors égal à y, qui lui-même prend la valeur de temp. À chaque nouvelle itération, on ajoute à la variable sum la valeur de la variable y si celle-ci est paire.

function problem2(){
  var limit = 4000000,
      sum = 0,
      x = 0,
      y = 1;

  while(y < limit){
    if(y%2==0) sum += y;
    var temp = x + y;
    x = y;
    y = temp;
  }
  return sum;
}

problem2();

En clair, lors de la première itération de cette boucle, on a : x = F(0) et y = F(1). temp représente d'abord F(2) et est donc égal à F(0) + F(1), soit x +y. x prend ensuite la valeur de y donc x = F(1) = 1 ; y prend la valeur de temp donc y = F(2) = 1.

Lors de la deuxième itération de la boucle, on a donc : x = F(1) et y = F(2). temp va représenter F(3), et donc être égal à F(1) + F(2), soit x +y. x prend ensuite la valeur de y donc x = F(2) = 1 ; y prend la valeur de temp donc y = F(3) = 2.

À la troisième itération de cette boucle, y étant égal à 2, chiffre pair, sera ajouté à sum. Et ainsi de suite, jusqu'à ce que y dépasse 4 000 000.

La fonction présente ci-dessus s'exécute en 0.12 milliseconde.

Les fonctions récursives en JavaScript

Copyright : Dennis JArvis

To iterate is human, to recurse divine. – L. Peter Deutsch

La récursivité est un grand concept de la programmation : il s’agit d’une méthode permettant d’obtenir une solution à un problème en utilisant des instances plus petites de ce même problème. En clair, une fonction est donc dite récursive si elle s’appelle elle-même.

La récursivité est une approche de la programmation un peu complexe au premier abord, puisqu’elle s’oppose à la programmation itérative. Mais elle propose des avantages indéniables : sa grande force est de pouvoir résoudre un problème en le divisant en une collection de sous-problèmes, chacun d’entre eux étant résolu par une solution évidente.

Pour bien appréhender ce concept, le sous chapitre suivant est proposé en guise de rappel. Il vous permettra de faire un parallèle avec l’écriture récursive, que je vous explique dans un second temps.

Une boucle, des itérations

Une boucle est une séquence d’instructions qui se répétera jusqu’à ce qu’une certaine condition soit remplie. Cette condition permettant de sortir de la boucle peut être définie à l’aide d’un compteur. On peut ainsi définir une boucle comme étant un bloc de code qui sera exécuté au moins une fois. Et chacune de ces exécutions est appelée une itération.

Les boucles sont plutôt simples à écrire, faciles à comprendre, et elles permettent de gagner un temps non négligeable, qui en plus évite la répétition de code pour chacune des itérations.

En guise d’illustration, je vous propose l’implémentation de la notion mathématique suivante : la factorielle. La factorielle d’un nombre est le produit de tous les entiers de 1 à ce nombre. Ainsi, la factorielle du nombre 5 est égale au produit de 1 x 2 x 3 x 4 x 5. Elle est donc égale à 120. Je crée donc ici une fonction factorial qui va, au moyen de la boucle for, proposer le résultat de factorielle x de manière itérative.

function factorial(x) {
  var result = 1;
  for (var i = 1; i <= x; i++)
    result = result * i;
  return result;
}

factorial(5); // output : 120

Comme vous pouvez le voir, on utilise ici un compteur qui va s'incrémenter en répétant l'action de produire la multiplication entre le résultat précédemment obtenu et ce même compteur. A chaque itération de la boucle, ce compteur change donc de valeur.

Cas de base, cas de propagation

Afin que la récursivité soit effective, deux fonctionnalités clés doivent nécessairement être implémentées. Il s'agit du cas de base et du cas de propagation, aussi parfois appelé simplement le cas récursif.

Le cas de base représente l'ensemble des lignes de code qui permet l'arrêt de la récursion. Habituellement, cet ensemble débute avec une clause conditionnelle comme if. Si cette notion n'est pas mise en place, la fonction sera répétée de manière infinie et le programme plantera. Le case de base est donc la condition de fin de la fonction récursive.

Le cas de propagation représente l'ensemble des lignes de code où aura lieu la récursivité. Il s'agit, en clair, du bloc de code où la fonction fera à nouveau appel à elle-même.

Écrivons de nouveau la fonction factorial mais cette fois de manière récursive.

function factorial(x) {
  // This is the base case.
  if (x === 0) return 1;
  // This is the recursive one.
  else return x * factorial(x - 1);
}

factorial(5); // output : 120

Notre cas de base déclare que si x est égal à 0, nous retournons la valeur 1. Cette fonction factorial va donc s'arrêter au moment où x atteindra la valeur 0. Pour toute autre valeur positive de x, nous retournons, le produit de x et de factorielle x.

Décomposons factorial(5) pas à pas, pour bien comprendre le mécanisme de la récursivité.

factorial(5) = 5 * factorial(4);
factorial(4) = 4 * factorial(3);
factorial(3) = 3 * factorial(2);
factorial(2) = 2 * factorial(1);
factorial(1) = 1 * factorial(0);
factorial(0) = 1;
// Donc :
// factorial(1) = 1 * 1;
// factorial(2) = 2 * 1 * 1;
// factorial(3) = 3 * 2 * 1 * 1;
// factorial(4) = 4 * 3 * 2 * 1 * 1;
// factorial(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

Penser récursif

Mettre en place des fonctions qui utilisent le principe de la récursivité n'est absolument pas inné. Cependant, il vous permettra d'obtenir des fonctions plus élégantes découpées en de plus petites instances d'elles-même. Mais il faut nécessairement de la pratique !

Ma principale recommandation est de penser en premier lieu au cas de base. C'est grâce à cette condition de fin essentielle que votre programme ne plantera pas et ne tournera pas de manière infinie. Prenez une feuille, posez cette condition et essayez systématiquement de réduire votre problème à une solution simple. Vous pouvez continuer cette réflexion autour de cet article de Santosh Rajan par exemple.

Problème #1 du Project Euler

Copyright : Pedro Ribeiro Simões

Avez-vous déjà entendu parler du fameux Project Euler ? Non, jamais ?! Vraiment ? Et pourtant, il rapproche plus de 440 000 utilisateurs dans le monde entier !

La popularité du projet Euler ne cesse de croître au fil des années auprès notamment des développeurs, des étudiants des filières scientifiques, ou simplement des adultes passionnés en mathématiques. Et pour cause…

Le project Euler

Le projet Euler commence le 5 octobre 2001 en tant que rubrique sur le site MathsChallenge.net. Cette initiative née du clavier de Colin Hughes est aussi une manière de rendre hommage au travail du mathématicien et physicien d’origine suisse Leonhard Euler.

Il consiste en une multitude de problèmes plus ou moins faciles à résoudre : il en existe plus de 500 aujourd’hui. L’objectif de tout développeur qui accepte de relever le défi est de proposer un algorithme simple et efficace en termes de performance pour parvenir à une réponse, correcte bien évidemment. Et vous verrez que plus vous avancerez dans le compte des problèmes proposés, plus difficile il sera pour vous de développer des mini programmes ultra rapides pour obtenir les solutions.

Bon, ça y’est : vous êtes convaincus de tenter l’expérience ?! Je vous propose ci-dessous la résolution du premier problème de cette longue liste du projet Euler. Le code que vous retrouverez ci-dessous est ma propre interprétation de ces énoncés en JavaScript. Mais libre à vous de me proposer votre manière de les résoudre, avec d’autres langages, ou d’améliorer mon code en le rendant plus rapide par exemple. J’accepte volontiers vos remarques ou suggestions !

Le problème #1

« If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000. »

Le problème 1 est probablement le plus simple à résoudre du projet Euler. Il s’agit de déterminer la somme des nombres inférieurs à 1000 qui sont des multiples de 3 ou de 5. Par définition, si le nombre b est un multiple du nombre a, cela signifie que a est un diviseur du nombre b. Et que donc, la division b/a n’admet pas de reste.

D’après cette formule, la solution à implémenter paraît évidente. Et qu’importe le langage choisi, les programmes écrits pour parvenir à la solution de ce problème ont tendance à se ressembler. Pour ma part, j’ai donc créé en JavaScript une boucle for testant successivement tous les nombres inférieurs à 1000 et vérifiant si le reste de la division de ce nombre par 3 ou de ce nombre par 5 est nul. Si l’une de ces conditions est vraie, alors j’ajoute ce nombre à la somme totale.

function problem1(){
  var sum = 0;
  for (var i = 3; i < 1000; i++){
    if(i%3==0 || i%5==0) sum += i;
  }
  return sum;
}
problem1();

Ce petit programme s'exécute en 17 millisecondes sur mon ordinateur. Ça vous semble convenable, n'est-ce-pas ? Il existe pourtant une façon bien plus efficace de parvenir à la solution de ce problème !

Vous pouvez décider de calculer de manière indépendante la somme des nombres divisibles par 3 inférieurs à 1000 et la somme des nombres divisibles par 5 inférieurs également à 1000. De l'addition de ces deux sommes, il suffit de retirer la somme des nombres divisibles par 15, pour ne pas comptabiliser en double les multiples de 15, 15 représentant le produit de 3 par 5.

Observons de près ces deux sommes : si on additionne tous les multiples de 3 inférieurs à 1000, on a : 3 + 6 + 9 + ... + 999 soit le produit 3 x (1 + 2 + 3 + ... + 333). Et si nous additionnons tous les multiples de 5 inférieurs à 1000, nous obtenons : 5 + 10 + 15 + ... + 995 soit 5 x (1 + 2 + 3 + ... + 199).

Sachant que la somme de tous les nombres de 1 à n est égale à la formule n*(n+1)/2, il ne manque plus qu'à déterminer le plus grand des multiples du nombre souhaité en dessous de 1000 pour pouvoir effectuer le bon produit. Pour le chiffre 5, le plus grand des multiples en dessous de 1000 est 995, soit l'équivalent de la soustraction de ce nombre par le reste de la division 999/5. Je divise ensuite ce nombre par 5, pour obtenir le fameux 199. La somme des nombres de 1 à 199 est égale à (199x200)/2 soit 19 900. Je multiple ce nombre par 5 est le tour est joué !

function sumdivisibleby(x){
  var target = 999 - (999%x),
      n = target/x;
  return x*(n*(n+1))/2;
}

function problem1(){
  return sumdivisibleby(3) + sumdivisibleby(5) - sumdivisibleby(15);
}

Ce nouveau programme s'exécute en 6 millisecondes ! La différence peut vous sembler infime... Mais testez à nouveau ces deux fonctions, cette fois, pour trouver les multiples de 3 et 5 en dessous de 10 000 000 : la deuxième fonction s'exécute, chez moi, en 5 millisecondes, tandis que la première possède une durée d'exécution de 85.04 millisecondes. Une différence de plus en plus conséquente !

Comme vous le démontre l'exemple précédent, les possibilités sont grandes, et tous les moyens sont bons pour arriver au résultat tant convoité d'un problème. Certains algorithmes seront par contre plus efficaces que d'autres, et le projet Euler est une bonne manière de réfléchir aux enjeux de la performance lors du développement d'une fonctionnalité, et ce, quelque soit le langage que vous utilisez au quotidien.