{"id":1968,"date":"2016-02-19T13:02:33","date_gmt":"2016-02-19T18:02:33","guid":{"rendered":"http:\/\/bioinfo.iric.ca\/fr\/?p=1968"},"modified":"2017-04-29T17:06:29","modified_gmt":"2017-04-29T21:06:29","slug":"factoriel-et-log-factoriel","status":"publish","type":"post","link":"https:\/\/bioinfo.iric.ca\/fr\/factoriel-et-log-factoriel\/","title":{"rendered":"Factoriel et log factoriel"},"content":{"rendered":"

Factoriel:<\/strong><\/span><\/h2>\n

Quand vous avez besoin de calculer\u00a0n!, il existe plusieurs solutions:\u00a0<\/span><\/span><\/p>\n

    \n
  1. La solution \u00ab\u00a0rapide\u00a0\u00bb: qui utilise une boucle<\/strong> ou une fonction r\u00e9cursive<\/strong>:\u00a0<\/strong>
    \n\n\n\n
    \n
    def factorial_for(n):\r\n  r = 1\r\n  for i in range(2, n + 1):\r\n    r *= i\r\n  return(r)\r\n<\/code><\/pre>\n<\/td>\n
    		\n
    def factorial_rec(n):\r\n  if n > 1:\r\n    return(n * factorial_rec(n - 1))\r\n  else:\r\n    return(1)<\/code><\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    Ici, la multiplication s\u00e9quentielle de chaque nombre va g\u00e9n\u00e9rer un nombre tr\u00e8s grand tr\u00e8s rapidement,\u00a0ce qui n’est pas optimum. En effet, les ordinateurs sont plus rapides quand ils multiplient des petits nombres (120×30240) par rapport \u00e0 la m\u00eame multiplication avec un grand nombre (362880×10).<\/li>\n
  2. La solution \u00ab\u00a0intelligente\u00a0\u00bb: Ici, l’id\u00e9e est de s\u00e9parer une s\u00e9quence de nombres \u00e0 multiplier en deux par le milieu, de fa\u00e7on r\u00e9cursive.
    \n\n\n\n\n\n
    10!<\/td>\n= 1x2x3x4x5x6x7x8x9 x<\/strong> 10<\/td>\n= 362880 x <\/strong>10<\/td>\n(rush solution)<\/td>\n<\/tr>\n
    <\/td>\n= 1x2x3x4x5 x<\/strong> 6x7x8x9x10<\/td>\n= 120 x<\/strong> 30240<\/td>\n(1st split)<\/td>\n<\/tr>\n
    <\/td>\n= 1x2x3 x<\/strong> 4×5 x<\/strong> 6x7x8 x<\/strong> 9×10<\/td>\n= 6 x<\/strong> 20 x<\/strong> 336 x<\/strong> 90<\/td>\n(2nd split)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    def range_prod(lo, hi):\r\n  if lo + 1 < hi:\r\n    mid = (hi + lo) \/\/ 2\r\n    return(range_prod(lo, mid) * range_prod(mid + 1, hi))\r\n  if lo == hi:\r\n    return(lo)\r\n  return(lo * hi)\r\n<\/code><\/pre>\n
    def factorial_tree(n):\r\n  if n < 2:\r\n    return(1)\r\n  return(range_prod(1, n))<\/code><\/pre>\n<\/li>\n
  3. La solution \u00ab\u00a0paresseuse\u00a0\u00bb ou \u00ab\u00a0tr\u00e8s intelligente\u00a0\u00bb (tout d\u00e9pend du point de vue): consiste \u00e0 calculer une estimation du factoriel avec\u00a0l’approximation de Stirling.\u00a0<\/a>\n
    import math\r\ndef stirling(n):\r\n  return(math.sqrt(2 * math.pi * n) * (n \/ math.e) ** n)<\/code><\/pre>\n
    Cette impl\u00e9mentation est limit\u00e9e \u00e0 n<170. Toutefois, comme vous pouvez le constater plus bas, avec n=170, le r\u00e9sultat est \u00e9norme.
    \nAvec ce genre de gros nombre, nous pr\u00e9f\u00e9rons de toute fa\u00e7on travailler avec les log factoriels.<\/p>\n
    In [01]: stirling(170)\r\nOut[01]: 7.253858934542908e+306\r\nIn [02]: stirling(171)\r\nOut[02]: inf\r\n<\/code><\/pre>\n
     <\/li>\n<\/ol>\n
    Log Factorial:<\/strong><\/span><\/h2>\n
    Pour les deux premi\u00e8res solutions, vous n’avez qu’\u00e0 ajouter math.log() (en faisant import math<\/code> d’abord) :<\/p>\n\n\n\n
    \n
    def log_fact_rec(n):\r\n  return(math.log(factorial_rec(n)))<\/code><\/pre>\n<\/td>\n
    		\n
    def log_fact_tree(n):\r\n  return(mat.log(factorial_tree(n)))<\/code><\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    def log_fact_for(n):\r\n  return(math.log(factorial_for(n)))<\/code><\/pre>\n
    Le log factoriel avec l’approximation de Stirling<\/a> est impl\u00e9ment\u00e9e comme ceci :<\/p>\n
    def log_stirling(n):\r\n fn = float(n)\r\n fn = n * math.log(fn) + math.log(2 * math.pi * fn) \/ 2 - fn + \\\r\n      (fn ** -1) \/ 12 - (fn ** -3) \/ 360 + (fn ** -5) \/ 1260 - \\\r\n      (fn ** -7) \/ 1680 + (fn ** -9) \/ 1188\r\n return(fn)<\/code><\/pre>\n
    Note:<\/strong><\/span><\/p>\n
    Dans le cas o\u00f9 vous avez de multiples log factoriels \u00e0 calculer, il peut \u00eatre utile de sauvegarder et r\u00e9utiliser des r\u00e9sultats pr\u00e9c\u00e9dents et ainsi gagner du temps\u00a0(par exemple, 10! = 6!x7x8x9x10) comme ceci :<\/p>\n
    def log_fact_exact_saved(n, value_saved):\r\n  select = max((i for i in value_saved.keys() if i <= n))\r\n  if select != n:\r\n    value_saved[n] = range_prod(select + 1, n) * value_saved[select]\r\n  return(math.log(value_saved[n]))\r\n\r\ndef log_fact_approx_saved(n, value_saved):\r\n  if n not in value_saved:\r\n    value_saved[n] = log_stirling(n)\r\n  return(value_saved[n])<\/code><\/pre>\n
    Test:<\/strong><\/span><\/h2>\n
    Nous pouvons maintenant tester et comparer chacune de ces solutions en utilisant les librairies math<\/code> et scipy<\/code> pour voir laquelle est la plus rapide :<\/p>\n
    \r\nimport sys\r\nsys.setrecursionlimit(1000000) \/\/ increase the depth \r\nimport math\r\nimport scipy.special\r\ndef test_saved(saved, approx):\r\n    value = [10, 50, 100, 1000, 1000, 2000, 5000, 5000, 5000,\r\n             5000, 10000, 11000, 11000, 11000, 20000, 20000]\r\n    if approx:\r\n        if saved:\r\n            value_saved = {1: 1}\r\n            for num in value:\r\n                log_fact_approx_saved(num, value_saved)\r\n        else:\r\n            for num in value:\r\n                log_stirling(num)\r\n    else:\r\n        if saved:\r\n            value_saved = {1: 1}\r\n            for num in value:\r\n                log_fact_exact_saved(num, value_saved)\r\n        else:\r\n            for num in value:\r\n                log_fact_tree(num)\r\n\r\ndef log_fact_math(n):\r\n    return(math.log(math.factorial(n)))\r\n\r\ndef log_fact_scipy(n, exact=False):\r\n    return(math.log(scipy.special.factorial(n, exact)))\r\n\r\nimport timeit\r\nnum = 10000\r\nrep = 200\r\nprint(\"rec:\" + str(timeit.timeit(\"log_fact_rec(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_fact_rec\", number=rep)))\r\nprint(\"for:\" + str(timeit.timeit(\"log_fact_for(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_fact_for\", number=rep)))\r\nprint(\"scipy exact:\" + str(timeit.timeit(\"log_fact_scipy(\" + str(num) + \", True)\",\r\n      setup=\"from __main__ import log_fact_scipy\", number=rep)))\r\nprint(\"math:\" + str(timeit.timeit(\"log_fact_math(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_fact_math\", number=rep)))\r\nprint(\"tree:\" + str(timeit.timeit(\"log_fact_tree(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_fact_tree\", number=rep)))\r\n\r\nprint(\"scipy approx:\" + str(timeit.timeit(\"log_fact_scipy(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_fact_scipy\", number=rep)))\r\nprint(\"log_stirling:\" + str(timeit.timeit(\"log_stirling(\" + str(num) + \")\",\r\n      setup=\"from __main__ import log_stirling\", number=rep)))\r\n\r\nprint(\"value log(100!) tree:\" + str(log_fact_tree(100)))\r\nprint(\"value log(100!) scipy approx:\" + str(log_fact_scipy(100)))\r\nprint(\"value log(100!) log_stirling:\" + str(log_stirling(100)))\r\n\r\nprint(\"severals factorial:\" + str(timeit.timeit(\"test_saved(False, False)\",\r\n      setup=\"from __main__ import test_saved\", number=rep)))\r\nprint(\"severals factorial saved:\" + str(timeit.timeit(\"test_saved(True, False)\",\r\n      setup=\"from __main__ import test_saved\", number=rep)))\r\nprint(\"severals factorial approx:\" + str(timeit.timeit(\"test_saved(False, True)\",\r\n      setup=\"from __main__ import test_saved\", number=rep)))\r\nprint(\"severals factorial approx saved:\" + str(timeit.timeit(\"test_saved(True, True)\",\r\n      setup=\"from __main__ import test_saved\", number=rep)))\r\n<\/code><\/pre>\n
    En utilisant python 2.7.6<\/code> et scipy 0.17.0<\/code>, nous avons :<\/p>\n\n\n\n\n\n\n
    rec:4.52898597717
    \nfor:4.09089803696
    \nscipy exact:4.08975815773
    \nmath:4.02955198288
    \ntree:1.2138531208<\/strong><\/td>\n    		Nous pouvons voir que la solution \u00ab\u00a0intelligente\u00a0\u00bb est la plus rapide,<\/p>\n
    m\u00eame lorsque compar\u00e9e \u00e0 scipy<\/code><\/td>\n<\/tr>\n
    scipy approx:0.00166201591492
    \nlog_stirling:0.000301837921143<\/strong><\/td>\n    		\u00a0Encore ici, scipy<\/code> est le plus lent<\/td>\n<\/tr>\n
    value log(100!) tree:363.739375556
    \nvalue log(100!) scipy approx:363.739375556
    \nvalue log(100!) log_stirling:363.739375556<\/td>\n    		Dans ce cas-ci, toutes les m\u00e9thodes sont \u00e9quivalentes pour n>=100<\/td>\n<\/tr>\n
    several factorials:14.3231370449
    \nseveral factorials saved:3.51164102554<\/strong>
    \nseveral factorials approx:0.00481510162354
    \nseveral factorials approx saved:0.00360107421875<\/strong><\/td>\n    		Sauvegarder des r\u00e9sultats et les r\u00e9utiliser peut sauver beaucoup de temps,<\/p>\n
    mais prendra plus de m\u00e9moire.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    J’esp\u00e8re que cet article vous aidera \u00e0 choisir la meilleure solution (adapt\u00e9e \u00e0 vos besoins!) pour calculer des nombres factoriels et log factoriels.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Factoriel: Quand vous avez besoin de calculer\u00a0n!, il existe plusieurs solutions:\u00a0 La solution \u00ab\u00a0rapide\u00a0\u00bb: qui utilise une boucle ou une fonction r\u00e9cursive:\u00a0 def factorial_for(n): r = 1 for i in range(2, n + 1): r *= i return(r) def factorial_rec(n): if n > 1: return(n * factorial_rec(n – 1)) else: return(1) Ici, la multiplication s\u00e9quentielle de chaque nombre va g\u00e9n\u00e9rer un nombre tr\u00e8s grand tr\u00e8s rapidement,\u00a0ce qui n’est pas optimum. En effet, les ordinateurs sont plus rapides quand ils multiplient  […]<\/a><\/p>\n","protected":false},"author":9,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[32,26],"tags":[129],"class_list":["post-1968","post","type-post","status-publish","format-standard","hentry","category-performance-fr-2","category-langage-python","tag-analyse-de-donnees"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/1968","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/comments?post=1968"}],"version-history":[{"count":13,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/1968\/revisions"}],"predecessor-version":[{"id":3261,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/1968\/revisions\/3261"}],"wp:attachment":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/media?parent=1968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/categories?post=1968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/tags?post=1968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}