Confronto di velocità con Project Euler: C vs Python vs Erlang vs Haskell




9 Answers

Ci sono alcuni problemi con l'implementazione di Erlang. Come base per quanto segue, il mio tempo di esecuzione misurato per il tuo programma Erlang non modificato era di 47,6 secondi, rispetto ai 12,7 secondi del codice C.

La prima cosa che dovresti fare se vuoi eseguire un codice Erlang ad alta intensità di calcolo è usare il codice nativo. La compilazione con erlc +native euler12 ha erlc +native euler12 il tempo a 41,3 secondi. Questa è comunque una velocità molto più bassa (solo il 15%) del previsto dalla compilazione nativa su questo tipo di codice, e il problema è l'uso di -compile(export_all) . Questo è utile per la sperimentazione, ma il fatto che tutte le funzioni siano potenzialmente raggiungibili dall'esterno fa sì che il compilatore nativo sia molto conservativo. (Il normale emulatore BEAM non è molto influenzato.) Sostituzione di questa dichiarazione con -export([solve/0]). offre una velocità molto migliore: 31,5 secondi (quasi il 35% dalla linea di base).

Ma il codice stesso ha un problema: per ogni iterazione nel ciclo factorCount, si esegue questo test:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

Il codice C non lo fa. In generale, può essere complicato fare un confronto equo tra le diverse implementazioni dello stesso codice, e in particolare se l'algoritmo è numerico, perché è necessario essere sicuri che stiano facendo la stessa cosa. Un leggero errore di arrotondamento in un'implementazione a causa di qualche typecast da qualche parte può far sì che faccia molte più iterazioni rispetto all'altra, anche se entrambe alla fine raggiungono lo stesso risultato.

Per eliminare questa possibile fonte di errore (e sbarazzarmi del test aggiuntivo in ogni iterazione), ho riscritto la funzione factorCount come segue, modellata sul codice C:

factorCount (N) ->
    Sqrt = math:sqrt (N),
    ISqrt = trunc(Sqrt),
    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
       true          -> factorCount (N, ISqrt, 1, 0)
    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
    case N rem Candidate of
        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
        _ -> factorCount (N, ISqrt, Candidate + 1, Count)
    end.

Questa riscrittura, nessun export_all e la compilazione nativa mi hanno dato il seguente tempo di esecuzione:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

che non è male rispetto al codice C:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

considerando che Erlang non è affatto orientato alla scrittura di codice numerico, essendo solo il 50% più lento di C su un programma come questo è abbastanza buono.

Infine, riguardo alle tue domande:

Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Sì, un po '. In Erlang, non c'è modo di dire "usa aritmetica a 32/64 bit con wrap-around", quindi a meno che il compilatore non possa provare dei limiti sui tuoi numeri interi (e di solito non può farlo), deve controllare tutti i calcoli per vedere se possono rientrare in una singola parola con tag o se devono trasformarli in bignums allocati in heap. Anche se in pratica non vengono mai utilizzati bignum in fase di esecuzione, questi controlli dovranno essere eseguiti. D'altra parte, ciò significa che tu sai che l'algoritmo non fallirà mai a causa di un inaspettato numero intero inaspettato se improvvisamente gli dai input più grandi di prima.

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Sì, il tuo codice Erlang è corretto rispetto all'ottimizzazione dell'ultima chiamata.

python c performance haskell erlang

Ho preso il Problema # 12 da Project Euler come esercizio di programmazione e per confrontare le mie implementazioni (sicuramente non ottimali) in C, Python, Erlang e Haskell. Per ottenere tempi di esecuzione più elevati, cerco il numero del primo triangolo con più di 1000 divisori anziché 500 come indicato nel problema originale.

Il risultato è il seguente:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Pitone:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

Python con PyPy:

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

Erlang:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

Haskell:

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

Sommario:

  • C: 100%
  • Python: 692% (118% con PyPy)
  • Erlang: 436% (135% grazie a RichardC)
  • Haskell: 1421%

Suppongo che C abbia un grande vantaggio in quanto utilizza a lungo i calcoli e non gli interi di lunghezza arbitraria come gli altri tre. Inoltre non ha bisogno di caricare prima un runtime (Do gli altri?).

Domanda 1: Erlang, Python e Haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT ?

Domanda 2: Perché Haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile visto che Haskell è un libro con sette sigilli per me.)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

MODIFICARE:

Domanda 4: Le mie implementazioni funzionali consentono LCO (l'ultima ottimizzazione delle chiamate, ovvero l'eliminazione della ricorsione di coda) e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Ho davvero cercato di implementare lo stesso algoritmo il più simile possibile nelle quattro lingue, anche se devo ammettere che la mia conoscenza di Haskell ed Erlang è molto limitata.

Codici sorgente utilizzati:

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}
#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)
-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).
factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1



Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

L'implementazione C è subottimale (come suggerito da Thomas M. DuBuisson), la versione utilizza interi a 64 bit (cioè un tipo di dati lungo ). Analizzerò l'elenco di assembly in seguito, ma con un'ipotesi plausibile, ci sono alcuni accessi di memoria in corso nel codice compilato, che rendono l'utilizzo di numeri interi a 64 bit molto più lento. È quello o il codice generato (sia che sia possibile inserire meno di 64 bit in un registro SSE o arrotondare un doppio a un intero a 64 bit è più lento).

Ecco il codice modificato (semplicemente sostituisci long con int e I in modo esplicito in factorCount, anche se non penso che questo sia necessario con gcc -O3):

#include <stdio.h>
#include <math.h>

static inline int factorCount(int n)
{
    double square = sqrt (n);
    int isquare = (int)square;
    int count = isquare == square ? -1 : 0;
    int candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    int triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index++;
        triangle += index;
    }
    printf ("%d\n", triangle);
}

Running + timing dà:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Come riferimento, l'implementazione haskell di Thomas nella risposta precedente fornisce:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

Conclusione: non prendere nulla da ghc, è un ottimo compilatore, ma gcc normalmente genera codice più veloce.




L'implementazione di Haskell potrebbe essere notevolmente accelerata utilizzando alcune funzioni dei pacchetti Haskell. In questo caso ho usato i primes, che sono stati appena installati con 'cabal install primi';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

Tempi:

Il tuo programma originale:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Migliore implementazione

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Come puoi vedere, questo viene eseguito in 38 millisecondi sulla stessa macchina in cui il tuo ha funzionato in 16 secondi :)

Comandi di compilazione:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe



Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Questo è improbabile. Non posso dire molto di Erlang e Haskell (beh, forse un po 'di Haskell in basso), ma posso indicare molti altri colli di bottiglia in Python. Ogni volta che il programma tenta di eseguire un'operazione con alcuni valori in Python, dovrebbe verificare se i valori sono del tipo corretto e costa un po 'di tempo. factorCount funzione factorCount assegna solo una lista con range (1, isquare + 1) varie volte e runtime, l'allocazione della memoria con malloc è molto più lenta di iterare su un intervallo con un contatore come si fa in C. In particolare, il factorCount() è chiamato più volte e quindi assegna un sacco di liste. Inoltre, non dimentichiamo che Python è interpretato e l'interprete CPython non si concentra molto sull'ottimizzazione.

EDIT : oh, beh, noto che stai usando Python 3 quindi range() non restituisce una lista, ma un generatore. In questo caso, il mio punto sull'allocazione delle liste è metà sbagliato: la funzione alloca solo oggetti di range , che sono comunque inefficienti ma non altrettanto inefficienti quanto l'assegnazione di una lista con molti articoli.

Domanda 2: Perché haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile poichè haskell è un libro con sette sigilli per me.)

Stai usando gli Hugs ? Hugs è un interprete molto lento. Se lo stai usando, forse puoi ottenere un tempo migliore con GHC - ma io sono solo un'ipotesi incentrata sul cogit, il tipo di roba che un buon compilatore Haskell fa sotto la cappa è piuttosto affascinante e ben oltre la mia comprensione :)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

Direi che stai giocando un gioco poco divertente. La parte migliore di conoscere le varie lingue è usarle nel modo più diverso possibile :) Ma sto divagando, non ho alcuna raccomandazione per questo punto. Scusa, spero che qualcuno possa aiutarti in questo caso :)

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Per quanto mi ricordo, devi solo assicurarti che la tua chiamata ricorsiva sia l'ultimo comando prima di restituire un valore. In altre parole, una funzione come quella di seguito potrebbe utilizzare tale ottimizzazione:

def factorial(n, acc=1):
    if n > 1:
        acc = acc * n
        n = n - 1
        return factorial(n, acc)
    else:
        return acc

Tuttavia, non avresti tale ottimizzazione se la tua funzione fosse simile a quella qui sotto, perché c'è un'operazione (moltiplicazione) dopo la chiamata ricorsiva:

def factorial2(n):
    if n > 1:
        f = factorial2(n-1)
        return f*n
    else:
        return 1

Ho separato le operazioni in alcune variabili locali per chiarire quali operazioni sono state eseguite. Tuttavia, il più comune è vedere queste funzioni come sotto, ma sono equivalenti per il punto che sto facendo:

def factorial(n, acc=1):
    if n > 1:
        return factorial(n-1, acc*n)
    else:
        return acc

def factorial2(n):
    if n > 1:
        return n*factorial(n-1)
    else:
        return 1

Si noti che spetta al compilatore / interprete decidere se eseguire la ricorsione in coda. Ad esempio, l'interprete Python non lo fa se ricordo bene (ho usato Python nel mio esempio solo per la sua sintassi fluente). Ad ogni modo, se trovi cose strane come le funzioni fattoriali con due parametri (e uno dei parametri ha nomi come acc , accumulator ecc.) Ora sai perché le persone lo fanno :)




Guardando la tua implementazione di Erlang. La tempistica ha incluso l'avvio dell'intera macchina virtuale, l'esecuzione del programma e l'arresto della macchina virtuale. Sono abbastanza sicuro che l'installazione e l'interruzione dell'erlang vm richiedono del tempo.

Se il tempismo fosse stato fatto all'interno della macchina virtuale di erlang stessa, i risultati sarebbero diversi poiché in tal caso avremmo il tempo effettivo solo per il programma in questione. Altrimenti, credo che il tempo totale impiegato dal processo di avvio e caricamento di Erlang Vm più quello di interromperlo (come lo inserisci nel tuo programma) sono tutti inclusi nel tempo totale che il metodo che stai usando per cronometrare il tempo il programma sta uscendo. Prendi in considerazione l'utilizzo della temporizzazione di erlang che utilizziamo quando vogliamo temporizzare i nostri programmi all'interno della macchina virtuale stessa timer:tc/1 or timer:tc/2 or timer:tc/3. In questo modo, i risultati di erlang escluderanno il tempo impiegato per avviare e fermare / uccidere / fermare la macchina virtuale. Questo è il mio ragionamento lì, pensaci, e poi prova di nuovo il tuo benchmark.

In realtà suggerisco di provare a programmare il programma (per le lingue che hanno un runtime), nel runtime di quelle lingue per ottenere un valore preciso. Ad esempio, C non ha un sovraccarico di avvio e di arresto di un sistema runtime come fanno Erlang, Python e Haskell (il 98% ne è sicuro - sto correggendo). Quindi (basato su questo ragionamento) concludo dicendo che questo benchmark non era abbastanza preciso / corretto per le lingue che girano su un sistema runtime. Lo facciamo di nuovo con questi cambiamenti.

EDIT: inoltre, anche se tutti i linguaggi disponevano di sistemi di runtime, il sovraccarico di avvio di ciascuno e interruzione sarebbe diverso. quindi suggerisco di passare il tempo all'interno dei sistemi di runtime (per le lingue per le quali questo si applica). L'Erlang VM è noto per avere un notevole overhead all'avvio!




Domanda 1: Erlang, Python e Haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

La domanda 1 può essere risolta in senso negativo per Erlang. Si risponde all'ultima domanda usando Erlang in modo appropriato, come in:

http://bredsaal.dk/learning-erlang-using-projecteuler-net

Dato che è più veloce del tuo esempio C iniziale, direi che ci sono numerosi problemi, come altri hanno già trattato in dettaglio.

Questo modulo Erlang viene eseguito su un netbook economico in circa 5 secondi ... Utilizza il modello di thread di rete in erlang e, come tale, dimostra come sfruttare il modello di eventi. Potrebbe essere distribuito su molti nodi. Ed è veloce. Non il mio codice

-module(p12dist).  
-author("Jannich Brendle, jannich@bredsaal.dk, http://blog.bredsaal.dk").  
-compile(export_all).

server() ->  
  server(1).

server(Number) ->  
  receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},  
  server(Number+101);  
  {result,T} -> io:format("The result is: \~w.\~n", [T]);  
  _ -> server(Number)  
  end.

worker(Server_PID) ->  
  Server_PID ! {getwork, self()},  
  receive {work,Start,End} -> solve(Start,End,Server_PID)  
  end,  
  worker(Server_PID).

start() ->  
  Server_PID = spawn(p12dist, server, []),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]).

solve(N,End,_) when N =:= End -> no_solution;

solve(N,End,Server_PID) ->  
  T=round(N*(N+1)/2),
  case (divisor(T,round(math:sqrt(T))) > 500) of  
    true ->  
      Server_PID ! {result,T};  
    false ->  
      solve(N+1,End,Server_PID)  
  end.

divisors(N) ->  
  divisor(N,round(math:sqrt(N))).

divisor(_,0) -> 1;  
divisor(N,I) ->  
  case (N rem I) =:= 0 of  
  true ->  
    2+divisor(N,I-1);  
  false ->  
    divisor(N,I-1)  
  end.

Il test seguente si è svolto su una CPU Intel (R) Atom (TM) N270 a 1,60 GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

real    0m5.510s
user    0m5.836s
sys 0m0.152s



Cercando GO:

package main

import "fmt"
import "math"

func main() {
    var n, m, c int
    for i := 1; ; i++ {
        n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
        for f := 1; f < m; f++ {
            if n % f == 0 { c++ }
    }
    c *= 2
    if m * m == n { c ++ }
    if c > 1001 {
        fmt.Println(n)
        break
        }
    }
}

Ottengo:

versione originale c: 9.1690 100%
go: 8.2520 111%

Ma usando:

package main

import (
    "math"
    "fmt"
 )

// Sieve of Eratosthenes
func PrimesBelow(limit int) []int {
    switch {
        case limit < 2:
            return []int{}
        case limit == 2:
            return []int{2}
    }
    sievebound := (limit - 1) / 2
    sieve := make([]bool, sievebound+1)
    crosslimit := int(math.Sqrt(float64(limit))-1) / 2
    for i := 1; i <= crosslimit; i++ {
        if !sieve[i] {
            for j := 2 * i * (i + 1); j <= sievebound; j += 2*i + 1 {
                sieve[j] = true
            }
        }
    }
    plimit := int(1.3*float64(limit)) / int(math.Log(float64(limit)))
    primes := make([]int, plimit)
    p := 1
    primes[0] = 2
    for i := 1; i <= sievebound; i++ {
        if !sieve[i] {
            primes[p] = 2*i + 1
            p++
            if p >= plimit {
                break
            }
        }
    }
    last := len(primes) - 1
    for i := last; i > 0; i-- {
        if primes[i] != 0 {
            break
        }
        last = i
    }
    return primes[0:last]
}



func main() {
    fmt.Println(p12())
}
// Requires PrimesBelow from utils.go
func p12() int {
    n, dn, cnt := 3, 2, 0
    primearray := PrimesBelow(1000000)
    for cnt <= 1001 {
        n++
        n1 := n
        if n1%2 == 0 {
            n1 /= 2
        }
        dn1 := 1
        for i := 0; i < len(primearray); i++ {
            if primearray[i]*primearray[i] > n1 {
                dn1 *= 2
                break
            }
            exponent := 1
            for n1%primearray[i] == 0 {
                exponent++
                n1 /= primearray[i]
            }
            if exponent > 1 {
                dn1 *= exponent
            }
            if n1 == 1 {
                break
            }
        }
        cnt = dn * dn1
        dn = dn1
    }
    return n * (n - 1) / 2
}

Ottengo:

versione originale c: 9.1690 versione 100%
thaumkid's c: 0.1060 8650%
versione first go: 8.2520 versione secondo passaggio 111%
: 0.0230 39865%

Ho anche provato Python3.6 e pypy3.3-5.5-alpha:

versione originale c: 8.629 versione 100%
di thaumkid: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

e poi con il seguente codice ho ottenuto:

versione originale c: 8.629 versione 100% di
thaumkid: 0.109 8650%
Python3.6: 1.489 580%
pypy3.3-5.5-alpha: 0.582 1483%

def D(N):
    if N == 1: return 1
    sqrtN = int(N ** 0.5)
    nf = 1
    for d in range(2, sqrtN + 1):
        if N % d == 0:
            nf = nf + 1
    return 2 * nf - (1 if sqrtN**2 == N else 0)

L = 1000
Dt, n = 0, 0

while Dt <= L:
    t = n * (n + 1) // 2
    Dt = D(n/2)*D(n+1) if n%2 == 0 else D(n)*D((n+1)/2)
    n = n + 1

print (t)



Ho ipotizzato che il numero di fattori sia grande solo se i numeri coinvolti hanno molti piccoli fattori. Quindi ho usato l'algoritmo eccellente di thaumkid, ma prima ho usato un'approssimazione del conteggio dei fattori che non è mai troppo piccola. È abbastanza semplice: controlla i fattori primi fino a 29, quindi controlla il numero rimanente e calcola un limite superiore per il numero di fattori. Usalo per calcolare un limite superiore per il numero di fattori, e se quel numero è abbastanza alto, calcola il numero esatto di fattori.

Il codice sotto non ha bisogno di questa assunzione per correttezza, ma per essere veloce. Sembra funzionare; solo circa uno su 100.000 numeri dà una stima che è abbastanza alta da richiedere un controllo completo.

Ecco il codice:

// Return at least the number of factors of n.
static uint64_t approxfactorcount (uint64_t n)
{
    uint64_t count = 1, add;

#define CHECK(d)                            \
    do {                                    \
        if (n % d == 0) {                   \
            add = count;                    \
            do { n /= d; count += add; }    \
            while (n % d == 0);             \
        }                                   \
    } while (0)

    CHECK ( 2); CHECK ( 3); CHECK ( 5); CHECK ( 7); CHECK (11); CHECK (13);
    CHECK (17); CHECK (19); CHECK (23); CHECK (29);
    if (n == 1) return count;
    if (n < 1ull * 31 * 31) return count * 2;
    if (n < 1ull * 31 * 31 * 37) return count * 4;
    if (n < 1ull * 31 * 31 * 37 * 37) return count * 8;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41) return count * 16;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43) return count * 32;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47) return count * 64;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53) return count * 128;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59) return count * 256;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61) return count * 512;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67) return count * 1024;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71) return count * 2048;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73) return count * 4096;
    return count * 1000000;
}

// Return the number of factors of n.
static uint64_t factorcount (uint64_t n)
{
    uint64_t count = 1, add;

    CHECK (2); CHECK (3);

    uint64_t d = 5, inc = 2;
    for (; d*d <= n; d += inc, inc = (6 - inc))
        CHECK (d);

    if (n > 1) count *= 2; // n must be a prime number
    return count;
}

// Prints triangular numbers with record numbers of factors.
static void printrecordnumbers (uint64_t limit)
{
    uint64_t record = 30000;

    uint64_t count1, factor1;
    uint64_t count2 = 1, factor2 = 1;

    for (uint64_t n = 1; n <= limit; ++n)
    {
        factor1 = factor2;
        count1 = count2;

        factor2 = n + 1; if (factor2 % 2 == 0) factor2 /= 2;
        count2 = approxfactorcount (factor2);

        if (count1 * count2 > record)
        {
            uint64_t factors = factorcount (factor1) * factorcount (factor2);
            if (factors > record)
            {
                printf ("%lluth triangular number = %llu has %llu factors\n", n, factor1 * factor2, factors);
                record = factors;
            }
        }
    }
}

Questo trova il 14.753.024th triangolare con 13824 fattori in circa 0,7 secondi, il numero triangolare 879,207,615th con 61,440 fattori in 34 secondi, il numero triangolare 12,524,486,975th con 138,240 fattori in 10 minuti 5 secondi e il numero triangolare 26,467,792,064th con 172,032 fattori in 21 minuti e 25 secondi (Core2 Duo 2,4 GHz), quindi questo codice richiede in media solo 116 cicli del processore per numero. L'ultimo numero triangolare è più grande di 2 ^ 68, quindi




#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate<=n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

gcc -lm -Ofast euler.c

tempo ./a.out

2.79s utente 0.00 sistema 99% cpu 2.794 totale






Related