In computer science, the iterated logarithm of , written (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to . The simplest formal definition is the result of this recurrence relation:
On the positive real numbers, the continuous super-logarithm (inverse tetration) is essentially equivalent:
i.e. the base b iterated logarithm is if n lies within the interval , where denotes tetration. However, on the negative real numbers, log-star is , whereas for positive , so the two functions differ for negative arguments.
The iterated logarithm accepts any positive real number and yields an integer. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the interval on the x-axis.
In computer science, is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base ) instead of the natural logarithm (with base e).
Mathematically, the iterated logarithm is well-defined for any base greater than , not only for base and base e.
The iterated logarithm is useful in analysis of algorithms and computational complexity, appearing in the time and space complexity bounds of some algorithms such as:
Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n n) time.
Fürer's algorithm for integer multiplication: O(n log n 2O( n)).
Finding an approximate maximum (element at least as large as the median): n − 4 to n + 2 parallel operations.
Richard Cole and Uzi Vishkin's distributed algorithm for 3-coloring an n-cycle: O( n) synchronous communication rounds.
The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself. For all values of n relevant to counting the running times of algorithms implemented in practice (i.e., n ≤ 265536, which is far more than the estimated number of atoms in the known universe), the iterated logarithm with base 2 has a value no more than 5.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
La tétration (ou encore nappe exponentielle, hyperpuissance, tour de puissances, super-exponentiation ou hyper4) est une « exponentiation itérée ». C'est le premier hyperopérateur après l'exponentiation. Le mot-valise tétration a été forgé par Reuben Goodstein sur la base du préfixe tétra- (quatre) et itération. La tétration est utilisée pour l'écriture des grands nombres. Elle suit l'addition, la multiplication et l'exponentiation comme indiqué ci-après : addition multiplication exponentiation tétration avec chaque fois b apparitions de la lettre a.
vignette|Tracés des fonctions logarithmes en base 2, e et 10. En mathématiques, le logarithme (de logos : rapport et arithmos : nombre) de base d'un nombre réel strictement positif est la puissance à laquelle il faut élever la base pour obtenir ce nombre. Dans le cas le plus simple, le logarithme compte le nombre d'occurrences du même facteur dans une multiplication répétée : comme 1000 = 10×10×10 = 10, le logarithme en base 10 de 1000 est 3. Le logarithme de en base est noté : . John Napier a développé les logarithmes au début du .
En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction au voisinage d'un point ou à l'infini, en la comparant à celle d'une autre fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes.
We study the existence and propagation of singularities of the solution to a one-dimensional linear stochastic wave equation driven by an additive Gaussian noise that is white in time and colored in space. Our approach is based on a simultaneous law of the ...
We establish a Chung-type law of the iterated logarithm and the exact local and uniform moduli of continuity for a large class of anisotropic Gaussian random fields with a harmonizable-type integral representation and the property of strong local nondeterm ...
We determine the exact Hausdorff measure functions for the range and level sets of a class of Gaussian random fields satisfying sectorial local nondeterminism and other assumptions. We also establish a Chung-type law of the iterated logarithm. The results ...