Lequel est calculé plus rapidement,

Lequel est calculé plus rapidement, ou ou ? , et sont des réels positifs avec .log a c b $a^b$$\log_a c$ abcb>$\sqrt[b]{c}$$a$$b$$c$$b>1$

Quels types d'algorithmes utiliserez-vous dans la comparaison? Quelles sont leurs complexités?

Par exemple, lorsque ou c ≈ a $c \equiv a^b$$c \approx a^b$

Cette question a été inspirée par les commentaires sur la question d' échange de pile de mathématiques Quel est le but de l'approximation de Stirling à une factorielle? . Surtout, ces commentaires laissés par mjqxxxx , Thomas Andrews et moi.

Voir ma réponse à cette question pour certains problèmes connexes.

En général, les ordinateurs peuvent uniquement ajouter, soustraire, multiplier, diviser et décaler les bits. Pour les besoins de l'argument, supposons que vous ne calculez pas dans le cas spécial où a est une puissance de 2 et b est un nombre naturel, car ce cas se réduit à un décalage de bit, et est donc facile.$a^b$$a$$b$

Si est un nombre naturel et que vous souhaitez calculer un b , vous pouvez utiliser l' exponentiation de chaîne d'addition . Tous les autres cas dans votre question sont difficiles (en général).$b$$a^b$

Certains algorithmes rapides utilisés pour rapprocher ces fonctions avec une grande précision nécessitent de la magie noire. Pour voir ce que j'entends par «magie noire», jetez un œil à ce billet de blog de Martin Ankerl et à un article associé auquel il renvoie dans Neural Computation . Voir également l' algorithme CORDIC .

Des types similaires d'astuces de retournement de bits sont expliqués dans Hacker's Delight (le lien est vers le site Web compagnon du livre).

D'autres façons de calculer de bonnes approximations utilisent l'analyse numérique (voir l'article Wikipedia sur la théorie de l'approximation ). Une mauvaise façon de le faire est de créer une équation différentielle appropriée et de l'intégrer en utilisant une méthode numérique comme la méthode d'Euler (comme je l'ai dit, une mauvaise approximation, mais vous pouvez le faire). Une meilleure façon de procéder consiste à utiliser des approximations en série. La série de Taylor converge beaucoup trop lentement, donc quelque chose comme un approximant de Padé ou un autre type d'approximation de série à convergence rapide pourrait être utilisé à la place (autres approximants rationnels, série de Chebyshev, etc.).

L'algorithme que vous utilisez pour approximer les fonctions ci-dessus dépendra de votre architecture, des exigences de vitesse et des exigences de précision.

Le problème de la complexité est que tout algorithme ne calculera qu'une approximation à virgule flottante des fonctions que vous mentionnez, donc le temps d'exécution dépendra certainement de la précision que vous exigez de votre approximation. Même en tenant compte de cela, je ne pense pas que la complexité de calcul soit une bonne première approximation des performances; la taille de vos entrées va être mesurée en bits (c'est-à-dire le nombre de bits nécessaires pour représenter , b et $a$$b$$c$), qui vont dépendre de la précision plutôt que de la magnitude des entrées numériques elles-mêmes. À des fins pratiques, la précision de la représentation numérique des nombres ne variera pas beaucoup (simple précision, double précision, précision quad) et vous ne décidez généralement pas d'utiliser cette précision en fonction des estimations de la complexité de calcul des fonctions scalaires. . La métrique la plus pertinente est l'heure de l'horloge murale, et à moins que vous n'utilisiez une architecture spéciale (systèmes embarqués) ou que votre application n'exige vraiment une exponentielle rapide (voir le lien du billet de blog et le lien Neural Computation ci-dessus), les bibliothèques intrinsèques de votre la langue de choix est probablement très bien.

C'est une bonne question, car la compréhension des algorithmes numériques et des performances est une condition préalable importante pour être un scientifique de calcul efficace. En même temps, c'est une mauvaise question car les contraintes telles qu'elles sont posées ne la qualifient pas suffisamment pour donner une réponse significative.

Les performances des trois calculs dépendront fortement de la précision requise dans le résultat final ainsi que de la précision minimale requise pour représenter les opérandes. Vous qualifiez , b et c comme des nombres réels positifs, mais nous devons également savoir combien de chiffres binaires d n sont nécessaires pour les représenter avec précision. Pour comprendre les considérations de performances pour les nombres réels généraux, nous devons d'abord comprendre comment les ordinateurs représentent les nombres entiers ainsi que la façon dont il se rapproche des nombres réels à l'aide de nombres à virgule flottante.$a$$b$$c$$d_n$

Lorsque les ordinateurs fonctionnent sur un entier , le nombre de chiffres binaires nécessaires est évidemment égal au log 2 de la grandeur de l'entier, plus un bit supplémentaire pour gérer le signe:$M$$_2$

log 2 | M | + $d_n=$$_2|M|+1$

Par exemple, le nombre -8 peut être représenté avec 4 chiffres binaires. Pour les performances et l'efficacité de l'espace, les unités de logique arithmétique (ALU), responsables des calculs numériques des nombres entiers sur les unités de traitement modernes, sont conçues pour gérer les mathématiques sur des nombres entiers jusqu'à une certaine taille fixe, la plus courante de nos jours étant d = 32 et d = 64. Non seulement les processeurs x86 comme dans votre ordinateur ont des ALU, ils sont un élément fondamental de l'architecture informatique omniprésent dans la société électronique d'aujourd'hui. Si vous êtes familier avec les consoles de jeux vidéo, vous vous souvenez peut-être de la Nintendo 64, un système de jeu vidéo nommé d'après la taille (en bits), les unités logiques arithmétiques sur le processeur de la console ont été conçues pour gérer.

Les additions, soustractions et multiplications entières sur les unités logiques arithmétiques sont très efficaces et ne nécessitent généralement pas plus de plusieurs cycles pour être calculées. Les divisions sont moins performantes et, sur les processeurs modernes, elles peuvent nécessiter jusqu'à plusieurs dizaines de cycles. Les performances dépendent à la fois de l'architecture de l'unité de traitement (et de la mise en œuvre correspondante de l'unité arithmétique et logique) et de sa fréquence. Notez qu'un processeur 64 bits peut généralement effectuer de l'arithmétique sur des opérandes bits à la même vitesse pour x, entre 1 et 64.$x$$x$

En informatique générale, et en particulier en informatique scientifique, les mathématiques entières sont difficiles à gérer pour de nombreux calculs, et une autre représentation des nombres est nécessaire, la représentation dite à virgule flottante. Les nombres à virgule flottante représentent un compromis entre le fonctionnement des microprocesseurs modernes (cartilage des données en morceaux de bits) et les besoins de calcul en représentant les nombres sur le processeur en notation scientifique tronquée, en utilisant une base fixe b (généralement b = 2 ou b = 10 ) et représentant le nombre à l'aide de deux entiers, une mantisse (significande dans certains cercles) s , et un exposant e . Un nombre donné $n$$b$$b=2$$b=10$$s$$e$$x$ est alors approximativement représenté comme:

$x = s*b^e$

Je dis approximativement parce qu'il devrait être évident que même des justifications simples telles que ne peut pas être représenté exactement comme un nombre à virgule flottante pour les bases standard. Le nombre de chiffres engagés dans la signification détermine la précision du nombre, qui est relative à sa propre amplitude. Lanorme IEEE 754spécifie un certain nombre de règles sur la façon dont les nombres à virgule flottante devraient se comporter, y compris les plages de la signification et de la mantisse (et la plage et la précision correspondantes) pour plusieurs valeurs importantes dedn, de sorte que les calculs numériques soient répétables dans une certaine tolérance. Il y a beaucoup de subtilité dans le fonctionnement des nombres à virgule flottante que je ne peux pas espérer capturer dans cette réponse, pour une bonne introduction, je recommande"Ce que tout informaticien devrait savoir sur l'arithmétiqueà virgule flottante"$\frac{1}{3}$$d_n$.

Un effort intellectuel important au cours des 50 dernières années a été investi dans l'amélioration de la capacité du processeur pour calculer efficacement les opérations arithmétiques en virgule flottante. Sur les processeurs modernes, ces calculs sont gérés par une ou plusieurs unités à virgule flottante (FPU), une version plus sophistiquée de l'unité logique arithmétique conçue pour effectuer des opérations arithmétiques sur des nombres à virgule flottante et généralement conçue pour gérer les deux spécifiés IEEE 754 32 les nombres à virgule flottante à bits (souvent appelés «flottants») et les nombres à virgule flottante à 64 bits (souvent appelés «doubles») de manière efficace. Semblables aux unités logiques arithmétiques, les unités à virgule flottante peuvent souvent calculer l'addition, la soustraction et la multiplication en seulement quelques cycles, tandis que la division nécessite généralement un peu plus.

$a$$b$$c$

1. $a^b$
2. $_a c$
3. $c^\frac{1}{b}$

1 L'exponentiation générale est souvent mise en œuvre avec l'identité suivante:

$a^b = \beta^{a\cdot\text{log}_\beta b}$

$\beta$$2$$e$$\beta=2$$a$$b$$t=a\cdot\text{log}_2 b$$2^t$

FYL2X + F2XM1 + ~ 20 = 80 + 51 + ~ 20 = ~ 151 cycles

2 Ceci peut être transformé en deux logarithmes et en une division par le changement d'identité de base et n'a pas besoin d'être redimensionné pour un résultat précis.

2 * FYL2X + FDIV = 2 * 80 + (7 à 27) = 167 à 187 cycles

[3] Ceci équivaut à une division suivie d'une exponentiation, donc [1] plus FDIV, ~ 175 cycles.

Voyons si je peux paraphraser la question:

$a^b$$\log_a(c)$$a$

Réponse : cela dépend vraiment de la dépendance de c à l'égard de a et de la façon dont a se compare à b (supérieur, inférieur ou égal).

$c$$b$$a$

$c$$\log_a(c) = \ln(c)/\ln(a)$$\log_a(c)$$a^b$$a$$a^b = \omega(\log_a(c))$

$c=a^b$$\log_a(a^b)=b$$b$$a^b$$log_a(c)$$a^b = \omega(\log_a(c))$

$c$$a^b$$a^b$$c=\Theta(a^b)$

$\log_a(c)$$c^{1/b}$

$a$$b$$c$

$c$$c^{1/b}$$b$$c^{1/b} = o(\log_a(c))$

$c = a^b$$\log_a(c)= a$$c^{1/b} = a$$\log_a(c) = \Theta(c^{1/b})$

$c$$a^b$$a^b$$c$

$c^{1/b}$$a^b$

$c$$c^{1/b}$$a^b$$c^{1/b}=o(a^b)$

$c=a^b$$c^{1/b}=a$$b>1$$a^b$$c^{1/b}$

$a$$b$$c$