7 papers
Fine-Grained Analysis of SIMD-Based Hash Table Implementations
Cyril Nicaud, Pablo Rotondo
In recent years, several variants of classical hash table schemes have been developed by engineers in order to take advantage of the processor's internal parallelism using SIMD ins…
Efficient sampling of the unlabeled structure of uniform random mappings and surjections
Arnaud Carayol, Pablo Rotondo
This article deals with the sampling and statistics of uniform random mappings and surjections from to . More precisely, we focus on statis…
Shannon Weights for binary dynamical recurrent sources of zero entropy
Ali Akhavi, Eda Cesaratto, Frédéric Paccaut +2
A probabilistic source is defined as the set of infinite words (over a given denumerable alphabet) endowed with a probability . The paper deals with general binary sources where…
Mathematical Models to Analyze Lua Hybrid Tables and Why They Need a Fix
Conrado Martínez, Cyril Nicaud, Pablo Rotondo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mech…
Lochs-type theorems beyond positive entropy
Valérie Berthé, Eda Cesaratto, Pablo Rotondo +1
Lochs' theorem and its generalizations are conversion theorems that relate the number of digits determined in one expansion of a real number as a function of the number of digits g…
Analysis of the Continued Logarithm Algorithm
Pablo Rotondo, Brigitte Vallee, Alfredo Viola
The Continued Logarithm Algorithm - CL for short- introduced by Gosper in 1978 computes the gcd of two integers; it seems very efficient, as it only performs shifts and subtraction…
The recurrence function of a random Sturmian word
Pablo Rotondo, Brigitte Vallee
This paper describes the probabilistic behaviour of a random Sturmian word. It performs the probabilistic analysis of the recurrence function which can be viewed as a waiting time…