Avec le récent dénigrement de Python , voici une tentative pour montrer les points forts de Python. Votre défi est d'écrire un programme qui calcule la factorielle d'un nombre aussi élevé que possible en 10 secondes.n

Votre score sera (highest n for your program on your machine)/(highest n for my program on your machine)

Règles

• Vous devez calculer une solution entière exacte. Étant donné que la factorielle serait beaucoup plus élevée que ce qui peut tenir dans un entier non signé 64 bits, vous pouvez utiliser des chaînes si votre langue ne prend pas en charge les grands entiers
• Les failles standard sont interdites. En particulier, vous ne pouvez utiliser aucune ressource externe.
• Seule la partie calcul (qui inclut le temps pour toutes les solutions de contournement utilisant des chaînes) s'ajoute au temps total qui doit être inférieur à 10 secondes en moyenne.
• Programmes à thread unique uniquement.
• Vous devez stocker la sortie sous une forme facilement imprimable (car l'impression prend du temps) (voir mon programme ci-dessous), chaîne, variable, tableau de caractères, etc.

ÉDITER:

• Votre programme doit donner la sortie correcte pour tous n:1 <= n <= (your highest n)

EDIT2:

• Je déteste le dire explicitement, mais l'utilisation des fonctions factorielles intégrées de votre langage relève des lacunes standard http://meta.codegolf.stackexchange.com/a/1078/8766 Désolé Mathematica et Sage

Mon programme

from __future__ import print_function
import time


def factorial( n ):
    return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )

start = time.clock()
answer = factorial( 90000 )
end = time.clock()

print ( answer )
print ( "Time:" , end - start , "sec" )

Le score le plus élevé l'emporte. Pour mémoire, mon code peut se gérer n = 90000en 9.89quelques secondes sur un Pentium 4 3.0 GHz

EDIT: Tout le monde peut-il s'il vous plaît ajouter le score plutôt que le n le plus élevé . Le plus haut nn'a aucune signification en soi car il dépend de votre matériel. Sinon, il est impossible d'avoir un critère de gain objectif. La réponse de ali0sha le fait correctement.

Nous avons un gagnant. Je n'ai pas accepté la réponse java /codegolf//a/26974/8766 car il s'agit de jupes proches de http://meta.codegolf.stackexchange.com/a/1080/8766

C ++ avec GMP, score = 55,55 (10 000 000/180 000)

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <queue>
#include <gmpxx.h>

int main(int argc, char *argv[]) {
  uint64_t n = atoi(argv[1]);

  // Iterate through 1..n.  Strip off powers of 2.  Multiply
  // remainders together into <= 64 bit chunks.
  uint64_t twos = 0;
  std::vector<uint64_t> terms;
  uint64_t m = 1;
  for(uint64_t i = 1; i <= n; i++) {
    uint64_t j = __builtin_ctzll(i);
    twos += j;
    uint64_t k = i >> j;
    if(__builtin_clzll(m) + __builtin_clzll(k) >= 64) {
      m *= k;
    } else {
      terms.push_back(m);
      m = k;
    }
  }
  if(m != 1) terms.push_back(m);

  // convert to gmp
  // why isn't there a 64-bit constructor?
  std::queue<mpz_class> gmpterms;
  for(int i = 0; i < terms.size(); i++) {
    mpz_class x = (uint32_t)(terms[i] >> 32);
    x <<= 32;
    x += (uint32_t)terms[i];
    gmpterms.push(x);
  }

  // pop two from the bottom, multiply them, push on the end.
  while(gmpterms.size() > 1) {
    mpz_class a = gmpterms.front();
    gmpterms.pop();
    mpz_class b = gmpterms.front();
    gmpterms.pop();
    gmpterms.push(a * b);
  }

  mpz_class r = gmpterms.front();
  r <<= twos;
  //std::cout << r << std::endl;
}

Python 2.7

42.575 = (6.812.000 / 160.000) environ

Code:

import gmpy2

def fac1(n):
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,xrange(1,n+1))
    Number = (len(L)-1).bit_length()
    while Number:Number-=1;L=m(L)
    return L[0]

def fac2(n):
    global E; E=0
    def f(i):
        global E; E+=i//2
        return[]if i==1 else f(i//2)+range(3,i,2)+[[1,i][i%2]]
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,f(n))
    N=(len(L)-1).bit_length()
    while N: N-=1;L=m(L)
    return L[0]<<E

Tester:

import time

start = time.time()
baseline(160000)
print time.time()-start

start = time.time()
fac1(6811000)
print time.time()-start

start = time.time()
fac2(6812000)
print time.time()-start

start = time.time()
gmpy2.fac(26000000)
print time.time()-start

Production:

10.0069999695
10.0729999542
10.0360000134
9.98699998856

Comment ça fonctionne:

De plus grandes multiplications prennent plus de temps, nous voulons donc faire autant de petites multiplications que possible. Cela est particulièrement vrai en Python où pour des nombres inférieurs, 2^64nous utilisons l'arithmétique matérielle, et surtout que nous utilisons des logiciels. Donc, dans m(L), nous commençons par une liste L; si c'est une longueur impaire, nous supprimons un nombre de considération pour le rendre encore une fois. Ensuite, nous multiplions élément 1par élément -2, élément 3avec -4, etc., de sorte que

m([1,2,3,4,5,6,7,8]) = [2*7, 4*5, 6*3, 8*1] = [14, 20, 18, 8]
m([10,12,6]) = [360,112]
m([120,6]) = [40320]

Cette approche garantit que nous utilisons l'arithmétique matérielle aussi longtemps que possible, après quoi nous basculons sur la bibliothèque arithmétique gmc efficace.

Dans fac2, nous adoptons également une approche de division et de conquête plus classique, où nous séparons chaque multiple de 2 et les décalons à la fin pour une amélioration des performances triviale. Je l'ai inclus ici car il est généralement environ 0,5% plus rapide que fac1.

Version golfée de fac1(parce que je peux), 220B

import gmpy2
def f(n):
    m=lambda(L):([]if len(L)%2==0 else[L.pop()])+map(lambda(l):l[0]*l[1],zip(L[1::2],L[-2::-2]))
    L=map(gmpy2.mpz,xrange(1,n+1));N=(len(L)-1).bit_length()
    while N:N-=1;L=m(L)
return L[0]

Java - 125,15 (21 400 000/ 171 000)

Également copié sans vergogne à partir du référentiel Github de Peter Luschny (merci @ semi-extrinsèque) et autorisé sous la licence MIT, il utilise l'algorithme de "quadrillage imbriqué à factorisation principale" tel que proposé par Albert Schönhage et al. (selon la page de description des algorithmes factoriels de Luschny ).

J'ai légèrement adapté l'algorithme pour utiliser BigInteger de Java et pour ne pas utiliser de table de recherche pour n <20.

Compilé avec gcj, qui utilise GMP pour son implémentation BigInteger, et exécuté sur Linux 3.12.4 (Gentoo), sur un Core i7 4700MQ à 2,40 GHz

import java.math.BigInteger;

public class PrimeSieveFactorialSchoenhage {

    private static int[] primeList, multiList;

    public static BigInteger factorial(int n) {
        int log2n = 31 - Integer.numberOfLeadingZeros(n);
        int piN = log2n < 2 ? 1 : 2 + (15 * n) / (8 * (log2n - 1));

        primeList = new int[piN];
        multiList = new int[piN];

        int len = primeFactors(n);
        return nestedSquare(len).shiftLeft(n - Integer.bitCount(n));
    }

    private static BigInteger nestedSquare(int len) {
        if (len == 0) {
            return BigInteger.ONE;
        }

        int i = 0, mult = multiList[0];

        while (mult > 1) {
            if ((mult & 1) == 1) { // is mult odd ?
                primeList[len++] = primeList[i];
            }

            multiList[i++] = mult / 2;
            mult = multiList[i];
        }
        BigInteger ns = nestedSquare(i);
        if (len <= i) {
            return ns.multiply(ns);
        }

        return product(primeList, i, len - i).multiply(ns.multiply(ns));
    }

    private static BigInteger product(int[] a, int start, int length) {
        if (length == 0) {
            return BigInteger.ONE;
        }

        int len = (length + 1) / 2;
        long[] b = new long[len];

        int i, j, k;

        for (k = 0, i = start, j = start + length - 1; i < j; i++, k++, j--) {
            b[k] = a[i] * (long) a[j];
        }

        if (i == j) {
            b[k++] = a[j];
        }

        return recProduct(b, 0, k - 1);
    }

    private static BigInteger recProduct(long[] s, int n, int m) {
        if (n > m) {
            return BigInteger.ONE;
        }
        if (n == m) {
            return BigInteger.valueOf(s[n]);
        }
        int k = (n + m) >> 1;
        return recProduct(s, n, k).multiply(recProduct(s, k + 1, m));
    }

    private static int primeFactors(int n) {
        int[] primes = new int[n < 17 ? 6 : (int) Math.floor(n / (Math.log(n) - 1.5))];
        int numPrimes = makePrimeList(n, primes);

        int maxBound = n / 2, count = 0;

        int start = indexOf(primes, 2, 0, numPrimes - 1);
        int end = indexOf(primes, n, start, numPrimes);

        for (int i = start; i < end; i++) {
            int prime = primes[i];
            int m = prime > maxBound ? 1 : 0;

            if (prime <= maxBound) {
                int q = n;
                while (q >= prime) {
                    m += q /= prime;
                }
            }

            primeList[count] = prime;
            multiList[count++] = m;
        }
        return count;
    }

    private static int indexOf(final int[] data, int value, int low, int high) {
        while (low < high) {
            int mid = (low + high) >>> 1;

            if (data[mid] < value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        if (low >= data.length) {
            return low;
        }

        if (data[low] == value) {
            low++;
        }

        return low;
    }

    private static int makePrimeList(int n, int[] prime) {
        boolean[] composite = new boolean[n / 3];

        sieveOfEratosthenes(composite);

        boolean toggle = false;
        int p = 5, i = 0, j = 2;

        prime[0] = 2;
        prime[1] = 3;

        while (p <= n) {
            if (!composite[i++]) {
                prime[j++] = p;
            }
            // -- never mind, it's ok.
            p += (toggle = !toggle) ? 2 : 4;
        }

        return j; // number of primes
    }

    private static void sieveOfEratosthenes(final boolean[] composite) {
        int d1 = 8;
        int d2 = 8;
        int p1 = 3;
        int p2 = 7;
        int s1 = 7;
        int s2 = 3;
        int n = 0;
        int len = composite.length;
        boolean toggle = false;

        while (s1 < len) { // -- scan sieve
            if (!composite[n++]) { // -- if a prime is found, cancel its multiples
                int inc = p1 + p2;

                for (int k = s1; k < len; k += inc) {
                    composite[k] = true;
                }

                for (int k = s1 + s2; k < len; k += inc) {
                    composite[k] = true;
                }
            }

            if (toggle = !toggle) { // Never mind, it's ok.
                s1 += d2;
                d1 += 16;
                p1 += 2;
                p2 += 2;
                s2 = p2;
            } else {
                s1 += d1;
                d2 += 8;
                p1 += 2;
                p2 += 6;
                s2 = p1;
            }
        }
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        long nanos = System.nanoTime();
        BigInteger fact = factorial(n);
        nanos = System.nanoTime() - nanos;
        // Commented out because it takes ages to print
        //System.out.println(fact);
        System.out.println(nanos / 1e9);
    }
}

Python 3, n = 100000

Un simple changement d'algorithme était tout ce qui était nécessaire pour augmenter l'exemple de code de 10000.

import time

def factorial(n):
    result = 1
    while n > 0:
        result *= n
        n = n - 1
    return result

start = time.clock()
answer = factorial(100000)
end = time.clock()

print(answer)
print("Time:", end - start, "sec")

Évidemment, ce n'est pas la réponse la plus créative, mais il n'y a vraiment qu'une seule façon de faire une factorielle ...

Perl + C, n = environ 3 millions

Ici, j'utilise la bibliothèque Math :: BigInt :: GMP disponible sur CPAN, qui fournit une augmentation de vitesse massive pour les principaux objets Math :: BigInt de Perl.

use v5.14;
use Time::HiRes 'time';
use Math::BigInt only => 'GMP';

sub factorial { Math::BigInt::->new(@_)->bfac }

my $start  = time;
my $answer = factorial( 3_000_000 );
my $end    = time;

say $answer;
say "Time: ", $end - $start, " sec";

Gardez à l'esprit que mon ordinateur est probablement un peu plus lent que le vôtre. En utilisant votre script Python d'origine, je ne peux calculer factorial(40000)qu'en 10 secondes; factorial(90000)prend beaucoup plus de temps. (J'appuie sur Ctrl + C après une minute.) Sur votre matériel, en utilisant Math :: BigInt :: GMP, vous pouvez très bien calculer la factorielle de 5 millions ou plus en moins de 10 secondes.

Une chose que vous remarquerez peut-être, c'est que même si la factorielle est calculée incroyablement rapidement, l'impression du résultat est très lente, prenant environ trois fois plus longtemps que le calcul d'origine. En effet, GMP utilise en interne une représentation binaire plutôt que décimale et son impression nécessite une conversion binaire en décimale.

Python 2,7
5,94 = 1'200'000 / 202'000

def fast_fac(n):
    def prod(start, fin):
            if fin - start <= 50:
                    return reduce(lambda x,y: x*y, xrange(start, fin+1), 1)
            else:
                    mid = (start+fin) / 2
                    return prod(start, mid) * prod(mid+1, fin)
    return prod(1, n)

Utilise la facilité relative de multiplication de nombreux groupes de petits nombres, puis les multiplie par rapport à un grand nombre de multiplications impliquant un nombre énorme.

C #: 0,48 (77 000/160 000)

Je ne suis pas content de ça.

C # est-il si lent?

Mais voici quand même mon entrée.

static void Main(string[] args)
    {
        Console.WriteLine("Enter N for fatorial:");
        int n = Convert.ToInt32(Console.ReadLine());

        Stopwatch s = Stopwatch.StartNew();


        BigInteger result = 1;
        while (0 <-- n) result *= n;

        s.Stop();

        Console.WriteLine("Output: {0} ", result);

        Console.WriteLine("Completed in {0}", s.Elapsed);

    }

Lorsque n = 77000, il faut 00:00:09:8708952calculer.

J'exécute en mode Release, en dehors de Visual Studio, en utilisant un Core i3-2330M @ 2,2 GHz.

Edit: Puisque je ne fais rien d'intelligent, j'accepte ce résultat. Peut-être que le .NET Framework 4.5 ajoute des frais généraux (ou BigInteger n'est pas si rapide).

bc, score = 0,19

Que diable, voici mon candidat pour "Combien pouvez-vous multiplier lentement?"

bc est "un langage de calculatrice à précision arbitraire", mais malheureusement assez lent:

n=read()
for(f=i=1;i<=n;i++)f*=i
f
quit

En environ 10 secondes sur mon MacBook Pro mi-2012 (Intel Core i7 à 2,3 GHz), la réponse de référence en python peut calculer 122000 !, mais ce script bc ne peut calculer que 23600 !.

Inversement 10000! prend 1,5s avec le script de référence python, mais le script bc prend 50s.

Oh cher.

Bash: score = 0,001206 (181/150000)

J'ai volé les fonctions mathématiques de Rosettacode - Longue multiplication que je n'ai pas analysé ni essayé d'optimiser.
Vous êtes libre de modifier l'algorithme ou d'essayer une méthode de fractionnement de chaînes différente.

#!/bin/bash


add() { # arbitrary-precision addition
  if (( ${#1} < ${#2} )); then
    local a="$2" b="$1" sum= carry=0
  else
    local a="$1" b="$2" sum= carry=0
  fi

  while (( ${#a} )); do
    local -i d1="${a##${a%?}}" d2="10#0${b##${b%?}}" s=carry+d1+d2
    sum="${s##${s%?}}$sum"
    carry="10#0${s%?}"
    a="${a%?}" b="${b%?}"
  done
  echo "$sum"
}

multiply() { # arbitrary-precision multiplication
  if (( ${#1} < ${#2} )); then
    local a="$2" b="$1" product=0
  else
    local a="$1" b="$2" product=0
  fi

  local zeroes=
  while (( ${#b} )); do
    local m1="$a"
    local m2="${b##${b%?}}"
    local partial=$zeroes 
    local -i carry=0
    while (( ${#m1} )); do 
      local -i d="${m1##${m1%?}}"
      m1="${m1%?}"
      local -i p=d*m2+carry
      partial="${p##${p%?}}$partial"
      carry="10#0${p%?}"
    done
    partial="${carry#0}$partial"
    product="$(add "$product" "$partial")"
    zeroes=0$zeroes
    b="${b%?}"
  done
  echo "$product"
}

# 'timerun' function
trap 'echo $((i -1)) $f; exit'  USR1  
(sleep 9.9; kill -USR1 $$)&

declare -i i 
f=1
for ((i=1; i< 10000 ; i++ ))   # 10000 is verry optimistic
do
    f=$(multiply $f $i)
done 

Python 3, algo avancé de Peter Luschny: 8,25x (1 280 000/155 000)

Copie sans vergogne de Peter Luschny,
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm ,
qui fournit ce code sous la licence "Creative Commons Attribution-ShareAlike 3.0".

Il s'agit en fait d'un algorithme assez avancé, utilisant quelque chose appelé "factoriel oscillant" et une liste de nombres premiers. Je soupçonne que cela pourrait être encore plus rapide s'il aimait la plupart des autres réponses et effectuait la plupart des multiplications avec des entiers 32 bits.

#! /usr/bin/python3
import time
import bisect 

def Primes(n) : 
  primes = [2, 3] 
  lim, tog = n // 3, False 
  composite = [False for i in range(lim)] 

  d1 = 8; d2 = 8; p1 = 3; p2 = 7; s = 7; s2 = 3; m = -1 

  while s < lim :             # --  scan the sieve 
      m += 1                  # --  if a prime is found 
      if not composite[m] :   # --  cancel its multiples 
          inc = p1 + p2 
          for k in range(s,      lim, inc) : composite[k] = True 
          for k in range(s + s2, lim, inc) : composite[k] = True 

          tog = not tog 
          if tog: s += d2; d1 += 16; p1 += 2; p2 += 2; s2 = p2 
          else:   s += d1; d2 +=  8; p1 += 2; p2 += 6; s2 = p1 

  k, p, tog = 0, 5, False 
  while p <= n : 
      if not composite[k] : primes.append(p) 
      k += 1; 
      tog = not tog 
      p += 2 if tog else 4 

  return primes 

def isqrt(x): 
  ''' 
  Writing your own square root function
  ''' 
  if x < 0: raise ValueError('square root not defined for negative numbers') 
  n = int(x) 
  if n == 0: return 0 
  a, b = divmod(n.bit_length(), 2) 
  x = 2**(a + b) 
  while True: 
      y = (x + n // x) // 2 
      if y >= x: return x 
      x = y 

def product(s, n, m): 
  if n > m: return 1 
  if n == m: return s[n] 
  k = (n + m) // 2 
  return product(s, n, k) * product(s, k + 1, m) 

def factorialPS(n): 

  small_swing = [1,1,1,3,3,15,5,35,35,315,63,693,231,3003,429,6435,6435, 
          109395,12155,230945,46189,969969,88179,2028117,676039,16900975, 
          1300075,35102025,5014575,145422675,9694845,300540195,300540195] 

  def swing(m, primes): 
      if m < 33: return small_swing[m] 

      s = bisect.bisect_left(primes, 1 + isqrt(m)) 
      d = bisect.bisect_left(primes, 1 + m // 3) 
      e = bisect.bisect_left(primes, 1 + m // 2) 
      g = bisect.bisect_left(primes, 1 + m) 

      factors = primes[e:g] 
      factors += filter(lambda x: (m // x) & 1 == 1, primes[s:d]) 
      for prime in primes[1:s]:   
          p, q = 1, m 
          while True: 
              q //= prime 
              if q == 0: break 
              if q & 1 == 1: 
                  p *= prime 
          if p > 1: factors.append(p) 

      return product(factors, 0, len(factors) - 1) 

  def odd_factorial(n, primes): 
      if n < 2: return 1 
      return (odd_factorial(n // 2, primes)**2) * swing(n, primes) 

  def eval(n): 
      if n < 0: 
          raise ValueError('factorial not defined for negative numbers') 

      if n == 0: return 1 
      if n < 20: return product(range(2, n + 1), 0, n-2) 

      N, bits = n, n 
      while N != 0: 
          bits -= N & 1 
          N >>= 1 

      primes = Primes(n) 
      return odd_factorial(n, primes) * 2**bits 

  return eval(n)

start = time.time()
answer = factorialPS(1280000) 
print(time.time()-start)

Java - 10,9

n = 885000

Mergesort-y.

import java.math.BigInteger;

public class Factorials {

    public static BigInteger fac;

    public static BigInteger two = BigInteger.valueOf(2);

    static BigInteger mul(BigInteger start, BigInteger end) {
        if(start.equals(end)) {
            return start;
        } else {
            BigInteger mid = start.add(end.subtract(start).divide(Factorials.two));
            return Factorials.mul(start, mid).multiply(Factorials.mul(mid.add(BigInteger.ONE), end));
        }
    }

    public static void main(String[] args) {
        Factorials.fac = BigInteger.valueOf(Integer.parseInt(args[0]));
        long t = System.nanoTime();
        BigInteger result = mul(BigInteger.ONE, fac);
        t = System.nanoTime() - t;
        System.out.print(String.valueOf(((float) t) / 1000000000)); //result.toString()+" @ "+
    }
}

BigIntegers sont lents.

Recommandations pour les bibliothèques d'entiers Java à haute vitesse de précision arbitraire? : P

C ++ (spécifique à x86_64) - 3.0 (390000/130000)

(facilement portable sur x86-32, le portage sur d'autres architectures implique une perte de vitesse importante)

Voici ma propre micro-implémentation de longue arithmétique.
Le calcul lui-même prend 10 secondes, et bien que la sortie soit sous une forme facilement imprimable (voir la operator<<surcharge), il faut plus de temps pour l'imprimer.

#include <vector>
#include <iostream>
#include <stdint.h>
#include <ctime>

typedef uint64_t digit;
typedef std::vector<digit> number;

std::ostream &operator<<(std::ostream &s, const number &x)
{
    std::vector<char> o;
    size_t size = x.size() * 21;
    o.resize(size);
    size_t lud = 0;
    for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
    {
        digit carry = 0;
        int j;
        for(j = 0; j <= lud || carry; j++)
        {
            digit r = o[j] * (1LL << 32) + carry;
            o[j] = r % 10;
            carry = r / 10;
        }
        lud = j;
        carry = 0;
        for(j = 0; j <= lud || carry; j++)
        {
            digit r = o[j] * (1LL << 32) + carry;
            o[j] = r % 10;
            carry = r / 10;
        }
        lud = j;
        carry = *i;
        for(j = 0; carry; j++)
        {
            digit r = o[j] + (carry % 10);
            carry /= 10;
            carry += r / 10;
            o[j] = r % 10;
        }
        if(j > lud)
            lud = j;
    }
    for(int j = lud; j--;)
        s.put(o[j] + '0');
    return s;
}

inline uint64_t dmul(uint64_t x, uint64_t y, uint64_t &carry)
{
    asm("mulq %2" : "+a"(x), "=d"(carry) : "r"(y));
    return x;
}
inline digit dadd(digit x, digit y, digit &carry)
{
    asm("movq $0, %1; addq %2, %0; adcq %1, %1" : "+r"(x), "=r"(carry), "+r"(y));
    return x;
}

void multiply(number &x, digit y)
{
    x.resize(x.size() + 2);
    digit carry = 0;
    for(number::iterator i = x.begin(), end = x.end(); i != end; i++)
    {
        digit nc, res = dmul(*i, y, nc);
        *i = dadd(res, carry, carry);
        carry += nc;
    }
    size_t sz = x.size();
    for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
    {
        if(*i)
            break;
        sz--;
    }
    x.resize(sz);
}

int main()
{
    const int r = 390000;
    clock_t start = clock();
    number n;
    digit mult = 1;
    n.push_back(1);
    for(digit a = 2; a <= r; a++)
    {
        digit carry, m = dmul(mult, a, carry);
        if(carry)
        {
            multiply(n, mult);
            mult = a;
        }
        else
            mult = m;
    }
    multiply(n, mult);
    std::cout << "Took: " << (clock() - start)/((double)CLOCKS_PER_SEC) << std::endl;
    std::cout << n << std::endl;
}

Python 3: 280000/168000

Temps d'exécution de votre programme: entre 9.87585953253et 10.3046453994. Temps d'exécution de mon programme: environ 10.35296977897559.

import time

def factorial(n):
    f = 1
    while n > 1:
        hn = n >> 1
        f = f * 2**hn * double_factorial(n) #dfl[hn + (n & 1) - 1]
        n = hn
    return f
def double_factorial(n):
    #dfl = [1]
    p = 1
    l = 3
    mh = n
    while l <= n:
        p *= l
        l += 2
        #dfl.append(p)
    return p

start = time.clock()
factorial(280000)
end = time.clock()

print(end - start)

J'ai lu cette réponse sur cs.SE et j'ai décidé d'essayer de l'implémenter en Python. Cependant, j'ai accidentellement découvert cela n! = (⌊n / 2⌋)! * 2**(⌊n / 2⌋) * n!!(note: !!c'est le double factoriel ). J'ai donc converti cela en une forme non récursive.

Les commentaires montrent ma tentative pour éviter de recalculer la double factorielle, mais j'ai découvert que le stockage de chaque valeur était trop coûteux en mémoire, ce qui faisait que mon ordinateur fonctionnait encore plus lentement. Je peux améliorer cela en ne stockant que ce qui est nécessaire.

Étrangement, j'ai implémenté la multiplication droite naïve en Python 3, et elle fait mieux que votre programme: n = 169000en 10 secondes .:

def factorial(n):
    p=1
    for i in range(n):
        p*=i+1
    return p

Ruby 2.1

score = 1,80 = 176_000 / 98_000

EDIT: amélioré de 1,35 = 132_000 / 98_000

J'ai pris des idées de l' algorithme factoriel GMP . Ce programme utilise la bibliothèque standard pour générer des nombres premiers. Ruby est un mauvais choix car la multiplication semble plus lente en Ruby qu'en Python.

1. Mon programme en Ruby 2.1: score = 1,80 = 176_000 / 98_000
2. Algorithme trivial en Python 2.7: score = 1 = 98_000 / 98_000
3. Algorithme trivial dans Ruby 2.1: score = 0,878 = 86_000 / 98_000

Oui, mon binaire de ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]liens contre GMP. Ruby 2.1 a ajouté une fonctionnalité pour utiliser GMP pour une multiplication importante, mais il semble toujours plus lent que Python 2.7.

require 'benchmark'
require 'optparse'
require 'prime'

def factorial(n)
  # calculate primes up to n, drop the 2
  @odd_primes = Prime.each(n).drop(1)

  # count prime factors of factorial(n)
  @factors = Hash.new(0)
  factorial_recurse(n)

  shift = @factors.delete(2) || 0
  @factors.inject(1) {|product, (base, exp)|
    product * base**exp
  } << shift
end

def factorial_recurse(n)
  return if n < 2

  # collect prime factors of 2 * 4 * 6 * .. * n
  #  = (2 * 2 * 2 * .. * 2) * (1 * 2 * 3 * .. * exp)
  #  = 2**exp * factorial(exp) where exp = floor(n/2)
  exp = n >> 1
  factorial_recurse(exp)
  @factors[2] += exp

  # collect prime factors 3 * 5 * 7 * ... * n
  for prime in @odd_primes
    break if prime > n
    exp = 0
    # count occurences of prime, prime**2, prime**3, .. n
    prime_power = prime
    until prime_power > n
      # floor(n / prime_power) occurences in 1 * 2 * .. * n,
      # but only ceil(count / 2) occurences in 3 * 5 * .. * n
      @factors[prime] += (n / prime_power + 1) >> 1
      prime_power *= prime
    end
  end
end

# usage: factorial.rb [-ct] [number]
cflag = tflag = false
OptionParser.new {|opts|
  opts.on('-c', 'Check for bugs') { cflag = true }
  opts.on('-t', 'Use trivial algorithm') { tflag = true }
  opts.parse!
}
$*[1] and fail 'too many arguments'
n = Integer($*[0] || 176_000)

if cflag
  factorial(n) == (1..n).reduce(1, :*) or
    fail "bad program: factorial(#{n}) is wrong"
  puts "ok"
  exit
end

# measure processor time to calculate factorial
f = nil
if tflag
  time = Benchmark.measure { f = (1..n).reduce(1, :*) }
else
  time = Benchmark.measure { f = factorial(n) }
end
puts f
puts "Time #{time.total} sec"

Julia - Score = 15,194

En utilisant exactement la même approche que celle du programme de référence ... c'est-à-dire

f(n)=reduce(*,1:big(n))

Il utilise donc réduire, l'opération de multiplication binaire de base et une plage (dans ce cas, en utilisant big (n) pour forcer le calcul à être effectué dans BigInt plutôt que Int64). De cela, je reçois

julia> @time K=f(2340000);
elapsed time: 9.991324093 seconds (814552840 bytes allocated)

Sur mon ordinateur, avec un programme de référence exécuté avec une entrée de 154000, j'obtiens une Time: 10.041181 secsortie (exécutez en utilisant python ./test.py, où test.py est le nom du fichier contenant le code de référence)

tcl, 13757

Ma réponse est de vérifier les limites de tcl.

La première ligne sert uniquement à définir un paramètre d'entrée:

set n 13757

Les autres sont l'algorithme lui-même:

set r 2
for {set i 3} {$i <= $n} {incr i} {set r [expr {$r*$i}]}   
puts $r

J'ai testé mon code sur http://rextester.com/live/WEL36956 ; Si je fais n plus grand, je reçois un SIGKILL; mai n peut devenir plus grand sur un interpréteur tcl local, que je n'ai pas.