0
Soit a, b deux entiers avec n chiffres. Je me demande si le temps de calcul du carré de a est plus court qu'un * b.la comparaison du temps de calcul de la multiplication
Nous vous remercions de votre aide.
A
Répondre
1
Je ne pense pas qu'il existe un moyen de faire un carré A sans utiliser un IMUL sur x86. Je peux me tromper.
Pour savoir combien de temps quelque chose prend, microbenchmark!
Éditer: oh attends, je l'ai! un b prend deux lectures en mémoire et un en prend un! Donc un * a est plus rapide :-). Vraie réponse: il n'y a pas de raison pour que * b soit plus lent à moins d'avoir un facteur extérieur qui influence les choses.
0
Jetez un oeil à the benchmarks in Bentley's "Programming Pearls", vous pouvez pirater quelque chose à partir de là pour mesurer.
1
Je suppose que votre question est:
* Soient a, b deux entiers avec n chiffres. Je me demande si le temps de calcul du carré de a est plus court que le temps de calcul de * b. *
Si n est suffisamment grand pour que vous ne puissiez pas utiliser une seule instruction de multiplication, alors tout algorithme que je savoir peut tirer parti du fait que les deux facteurs sont les mêmes. C'est vrai pour l'algorithme que vous avez appris à l'école, puisque presque la moitié des produits de paires de chiffres n'ont pas besoin d'être multipliés. À l'extrémité extrême pour un très grand n, en utilisant la convolution avec des FFT, la FFT pour les deux facteurs est la même pour le carré et ne doit être calculée qu'une seule fois.
Je ne vois pas ce que ce serait; tant que a et b sont de la même taille (en bits, pas en chiffres). Bien sûr, la seule façon de savoir est de l'évaluer. – quantumSoup
Si je suis autorisé à travailler en base-n, calculer n^2 est trivial. –