Gérer les grands nombres avec des performances de type GMP dans Go

Question

J'apprends Go et j'ai commencé à utiliser le package math/big pour gérer les entiers de longueur arbitraire.

J'ai écrit ce programme qui calcule la n-ième nombre de Fibonacci: (supprimé les import s):

func main() { 
    imax, _ := strconv.Atoi(os.Args[1]) 
    var a, b, c big.Int 
    a.SetUint64(0) 
    b.SetUint64(1) 
    for i := 0; i < imax; i++ { 
     c.Set(&b) 
     b.Add(&b, &a) 
     a.Set(&c) 
    } 
    fmt.Println(a.String()) 
} 

Voici le code pour le programme C:

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

    mpz_t a, b, c; 
    mpz_inits(a, b, c, NULL); 
    mpz_set_ui(a, 0); 
    mpz_set_ui(b, 1); 

    int i = 0; 
    for (i = 0; i < imax; i++) { 
     mpz_swap(a, b); 
     mpz_add(b, a, b); 
    } 

    char* astr = NULL; 
    astr = mpz_get_str(NULL, 10, a); 
    printf("%s\n", astr); 

    return EXIT_SUCCESS; 
} 

Les Computes du programme Go le terme 100 000 en 0,1 seconde (moyenne), tandis que l'équivalent en C, utilisant le GMP lib, ne s'exécute qu'en 0,04 seconde. C'est deux fois plus lent.

Y a-t-il un moyen d'obtenir la même performance dans mon programme Go?

Answer 1

N'imprimez pas sur stdout, c'est lent. Quel résultat obtenez-vous pour ce code?

package main 

import (
    "math/big" 
    "os" 
    "strconv" 
) 

func main() { 
    max, err := strconv.Atoi(os.Args[1]) 
    if err != nil { 
     panic(err) 
    } 
    a, b := big.NewInt(0), big.NewInt(1) 
    for i := 0; i < max; i++ { 
     a.Add(a, b) 
     a, b = b, a 
    } 
} 

Go n'est pas un code assembleur fabriqué à la main.

Votre valeur de 100 000 est trop petite pour un benchmark fiable. Utilisez 1 000 000 ou une autre valeur qui dure au moins dix secondes.

Answer 2

En général, GMP est plus rapide car il est conçu pour la performance. Sous le capot, vous pouvez trouver qu'il est partiellement écrit dans l'assemblage, ce qui réduit les frais d'appel des fonctions, peut utiliser certaines instructions CPU comme ADX et ainsi de suite. Si vous vous souciez de la performance, alors vous pouvez utiliser la routine mpz_fib_ui, ce qui serait encore plus rapide, car elle gagne de la ruse mathématique.

La réponse directe à votre question est probablement d'utiliser la liaison de Go pour GMP.