Chaos, Solitons & Fractals 45 (2012) 238–245

Contents lists available at SciVerse ScienceDirect

Chaos, Solitons & Fractals

Nonlinear Science, and Nonequilibrium and Complex Phenomena

journal homepage: www.elsevier.com/locate/chaos

Analyzing logistic map pseudorandom number generators for

periodicity induced by finite precision floating-point representation
K.J. Persohn, R.J. Povinelli ⇑
Electrical and Computer Engineering Department, Marquette University, Milwaukee, WI, USA

a r t i c l e i n f o a b s t r a c t

Article history: Because of the mixing and aperiodic properties of chaotic maps, such maps have been used
Received 31 December 2010 as the basis for pseudorandom number generators (PRNGs). However, when implemented
Accepted 6 December 2011 on a finite precision computer, chaotic maps have finite and periodic orbits. This manu-
Available online 20 January 2012
script explores the consequences finite precision has on the periodicity of a PRNG based
on the logistic map. A comparison is made with conventional methods of generating pseu-
dorandom numbers. The approach used to determine the number, delay, and period of the
orbits of the logistic map at varying degrees of precision (3 to 23 bits) is described in detail,
including the use of the Condor high-throughput computing environment to parallelize
independent tasks of analyzing a large initial seed space. Results demonstrate that in terms
of pathological seeds and effective bit length, a PRNG based on the logistic map performs
exponentially worse than conventional PRNGs.
Ó 2011 Elsevier Ltd. All rights reserved.

1. Introduction to develop an understanding of why (1) performs poorly

compared to conventional PRNGs, our results are also
Chaotic nonlinear dynamical systems are capable of applicable to understanding the limitations of finite preci-
imitating random noise. This property has sparked re- sion simulations of (1).
search interest leading to various proposals of applied PRNGs are an important area of study because of their
chaos in communications, cryptography, and computer ubiquitous use in a variety of applications: decision-making,
simulations. Misunderstanding the relationship between sampling, cryptography, and computer simulations. One
chaos and an applied field has resulted in numerous fail- can also use a PRNG to construct other cryptographic
ures when practical applications attempt to implement primitives such as block-ciphers and hashing functions
chaos theory. Some examples include an insecure synchro- [4–7]. Various generation methods have different tradeoffs
nized communication system [1], a weak and slow encryp- in randomness and computational efficiency that lead to
tion algorithm [2], and a pseudorandom number generator compromises in speed, security, and randomness. Quantify-
(PRNG) that falls short of its claims [3]. ing these characteristics is essential for comparisons be-
In this manuscript, we explore the following logistic tween chaos-based algorithms and their conventional
map as a PRNG. counterparts. In the next section, we discuss ideal properties
of PRNGs that influence randomness and metrics for bench-
xnþ1 ¼ 4xn ð1  xn Þ; xn 2 ð0; 1Þ: ð1Þ
marking performance in this context.
Specifically, we examine empirically and exhaustively the In the remainder of this manuscript, we present neces-
cyclic behavior of (1) in the range of 3 to 23 bits of preci- sary background information, which explains why the
sion. While we analyze (1) in the context of cryptography claims in [3] are impossible in practice. Next, we propose
a method to quantify the periodicity of a chaos-based
⇑ Corresponding author. PRNG implementation. Finally, an example based on the
E-mail addresses: kpersohn@ieee.org (K.J. Persohn), richard.povinelli@ logistic map demonstrates the differences between
marquette.edu (R.J. Povinelli). chaos-based and conventional PRNGs.

0960-0779/$ - see front matter Ó 2011 Elsevier Ltd. All rights reserved.
doi:10.1016/j.chaos.2011.12.006
 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245 239

2. Background chaotic generators in a class of their own does not put the
limitations of finite precision in perspective.
2.1. Pseudorandom number generators As a review, consider the following conventional
methods:
Sequences of random numbers are useful in many com-
puter applications. Generation of these sequences is said to 2.1.1. Linear congruential generator
be done pseudo-randomly. That is, although the output ap- The linear congruential generator (LCG) is a very com-
pears to be random, the output is actually generated deter- mon class of PRNG used by many C compilers. It is defined
ministically based on a seed value. Seeds are useful when by the recurrence relation
reproducible sequences are desired, for example, debug-
ging a simulation or encrypting/decrypting a message. An xkþ1 ¼ ðaxk þ cÞ mod m: ð2Þ
ideal random number generator is infinite, aperiodic, uni- The maximum period is limited to m uncorrelated num-
form, uncorrelated, and computationally efficient [3]. In bers [13]. Some implementations, for example the Java 2
other words, an ideal generator produces an endless se- SE Random class, elect to throw out lower order bits for en-
quence of numbers without repeating itself, and each hanced randomness [14]. Consequently, they do not maxi-
number in the sequence has an equal probability of being mize periodicity with respect to the number of bits
generated. Moreover, successive terms are not predictable representing the seed. Nevertheless, the LCG utilizes
without knowing the seed [8]. Repetitive or correlated gen- 100% of the retained bits producing a full period for all seed
erators lead to systematic errors in simulations and inse- values when a, c, and m meet certain conditions [9]. In
cure cryptosystems. addition, LCGs are relatively fast and easy to implement.
In practice, a PRNG implementation cannot be infinite or Unfortunately, this class of generator is subject to a num-
aperiodic when implemented with a finite precision com- ber of defects making it unsuitable for simulations or cryp-
puter system. The bit depth allocated to each numerical rep- tography [8].
resentation inherently limits the quantity of unique
numbers. Consequently, this finite set limits the seed space
2.1.2. Mersenne Twister (MT)
for any PRNG implementation as well. As a corollary, a PRNG
The MT is the default choice for randomization in many
implementation is periodic because the sequences naturally
popular software tools including MATLAB, Python, and
repeat when the finite space used to represent each term is
Ruby. The MT recurrence relation takes the form
exhausted. In the context of finite precision implementa-
 
tions, an ideal PRNG does not repeat itself until all elements xkþn ¼ xkþm  xuk jxlkþ1 A; k ¼ 0; 1; 2; . . . ð3Þ
of its seed space have been generated. Like the theoretically
ideal PRNG, the ideal practical implementation is uncorre- where j denotes bitwise OR,  is bitwise XOR, and xu, xl
lated, uniformly distributed, and computationally efficient represent bitmasks applied to x. The matrix A is the twist
for the first iteration of the entire seed space. transformation as described in [15]. The MT period is based
Various statistical and empirical tests exist to measure on a Mersenne prime, commonly 219937  1. This extre-
the randomness of a sequence generated by a PRNG. Some mely long period is attractive for simulations; however,
popular metrics are the chi-square (v2), Kolmogorov– the MT becomes predictable after a relatively small num-
Smirnov, poker, and run-up tests [9]. Passing these tests ber of iterations. For example, the MT19937 is predictable
is a good indication a PRNG produces uncorrelated terms. after only 624 iterations—far short of its entire period. Con-
Other authors have obtained results from standard metrics sequently, the MT is unsuitable for cryptographic applica-
that suggest chaos-based generators are capable of suffi- tions without further modifications such as those in [16].
cient randomness [10,11]. However, it is always best to
test a PRNG in a specific application before determining 2.2. Chaos and cryptography
it is sufficiently random [12]. For this reason, diverse gen-
eration methods are desirable for different applications. The motivation to study chaos-based PRNGs comes
However, statistical analysis does not provide a complete from many parallels between chaos and cryptography.
characterization of a PRNG. Previous studies of chaotic Chaotic systems are highly sensitive to changes in initial
PRNGs limited their statistical tests to single, relatively conditions. As a result, the mixing property of chaotic sys-
short sequences [3,10]. While these sequences pass various tems achieves desirable cryptographic properties of diffu-
statistical tests, our results illustrate that these sequence sion and confusion. This ensures that influence of key
lengths are inconsistent. As a baseline for comparison, and plaintext bits are spread over the ciphertext, where
consider the characteristics of conventional, integer-based the key is a secret, the plaintext is the message, and the
generation methods. Specifically, properly configured ciphertext is an encrypted combination of the key and
conventional generators can guarantee 100% utilization of the plaintext. Moreover, successive iterations of a chaotic
the bits allotted for representing an entire period without system reduce the statistical dependency of the ciphertext
repetition. This comparison bridges the gap between chaotic on the plaintext. These iterations closely parallel rounds of
and conventional PRNGs. As will be shown later in this a cryptosystem [17]. All of these relationships allude to ap-
manuscript, truncation effects can be detrimental to the plied chaos being useful for cryptography. Likewise, chaos
performance of a chaos-based implementation using finite is also applicable to other situations that require random-
precision floating-point numbers. Analyzing floating-point ness, such as computer simulations.
240 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245

There is one significant difference between chaotic sys- represents all possible outcomes. While (4) with k = 4
tems and cryptosystems that makes successful implemen- and an appropriately chosen seed (x0) is aperiodic on
tation challenging. Cryptosystems are defined on a discrete (0, 1), truncation of xn to the floating-point representation
set of numbers (often a range of integers) that can be on a finite precision system limits xn to the set identified
implemented on a computer with finite precision. On the by the significand bits.
other hand, chaotic systems rely on the set of real numbers
to produce many of the desirable properties that are appli- 2.5. Related work
cable to PRNGs. Truncation of finite precision real numbers
causes sequences to repeat with very small periods relative The idea of using the logistic map to build a PRNG has
to the corresponding cycles in purely theoretical infinite been previously discussed. LOGMAP has been shown to
precision representations. Overlooking this crucial detail pass the standard statistical tests by subsampling the lo-
leads to implementations that fall short of expectations gistic map and transforming the output to a uniformly dis-
[3]. In terms of cryptanalysis, short periods lead to predict- tributed, uncorrelated sequence [10]. However, this study
ability after a relatively small number of iterations. Obvi- did not rigorously test the periodicity; only random seeds
ously, this trait is undesirable in a secure system and is were considered resulting in unclear conclusions. Further-
further explained in [18]. more, the specific approach to testing for periodicity was
omitted; consequently, the test in [10] is neither reproduc-
2.3. The logistic map ible nor applicable to other recurrence relations.
Andrecut proposes a different transformation of the lo-
Our example chaotic PRNG is based on the logistic map. gistic map to produce uniform, uncorrelated series [3]. The
The recurrence relation result also passes various statistical tests and appears to be
computationally efficient. Nevertheless, the author con-
xnþ1 ¼ kxn ð1  xn Þ; xn 2 ð0; 1Þ ð4Þ
cludes that these series are aperiodic and infinite, which
defines the logistic map, where xn is the nth value of the disregards the adverse effects of an implementation in fi-
map and k is a parameter. Since chaotic behavior is of nite precision. The generator proposed in [3] when imple-
interest, k = 4 for this example. For a detailed discussion mented on a finite computer is finite and periodic and
of the logistic map and its many applications, see [19]. therefore far less impressive than the original claim of an
Note that (4) is defined on the open set (0, 1) because 0 is endless generator.
a known fixed point and 1 maps to 0. The logistic map is Our approach to analyzing chaos-based PRNGs, which
an interesting chaotic system to study because it uses sim- we name finite precision period calculation (FPPC), aims
ple operators that should be computationally fast in imple- to provide a universal method for analyzing the period
mentation. Furthermore, it is defined on a range of real lengths of recurrence relations implemented in finite pre-
numbers so it exemplifies the problem of interest when cision. Our FPPC approach helps evaluate chaos-based
implemented in finite precision. PRNGs against their conventional counterparts. Jiang and
Wu present a method to efficiently convert series pro-
2.4. Floating-point representation duced by the logistic map into uncorrelated uniform se-
quences [11]. FPPC complements their study by
Computers use a special representation to store floating- addressing the periodicity of the logistic map.
point numbers as binary digits in memory. This demonstra-
tion uses the format that virtually all modern computers 3. Finite precision period calculation
conform to, IEEE 754-2008 [12]. Specifically, this study uses
single precision (binary32) numbers to keep computations A finite precision implementation limits a theoretically
manageable. In binary32, 4 bytes represent each floating- aperiodic, infinite series produced by chaotic PRNGs to a
point number. The left-most bit designates the sign followed periodic, finite series. In this section, we describe an ap-
by 8 exponent bits and finally 23 fraction bits (significand). proach, which we call finite precision period calculation
An additional implied leading 1 on the fractional part gives (FPPC), to determine the periodic behavior of a map imple-
24 total bits of significand precision. A bias representation mented on a finite computer. The FPPC algorithm exhaus-
allows signed exponents. For example, Fig. 1 depicts the bit- tively explores a maps periodic behavior across a range of
wise representation of decimal 0.123456 in memory. precisions.
For the map defined in (4), interest focuses on the frac-
tional portion of the IEEE representation since (4) is evalu-
3.1. Example
ated between 0 and 1. Henceforth, references to the bits of
significand precision will refer to the number of bits
To demonstrate how a map’s periods may be calculated,
explicitly represented in memory.
consider an example based on the logistic map. Substitut-
The significand bits represent all possible seed values x0
ing k = 4 into (4) yields the chaotic relation of interest,
for the map defined in (4). Likewise, the same set
xnþ1 ¼ 4xn ð1  xn Þ; xn 2 ð0; 1Þ: ð5Þ

Let 4-bit binary fractions represent the set of x0 (seeds).

This demonstrates the effect of a 4-bit floating-point signif-
Fig. 1. IEEE 754-2008 binary32 representation of 0.12345610. icand. Obviously, this is an extreme simplification that
 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245 241

would never be implemented in practice; nevertheless,

this example illustrates the calculations that a computer Algorithm 1: Finite precision period calculation
performs for greater bit precisions. There are 24  1 or 15 Require: min, max, bitsPrecision
possible seeds (0 and 1 are excluded). Each produces a suc- for (xn min; xn 6 max; xn xn + ) do
cessive floating-point number, which is then truncated to seeds[ ] {SYMBOL}
its closest 4-bit representation. Table 1 summarizes the re- while (!periodic) do
sults of each seed including the sequence up to the first bf float2BinFrac(xn)
duplicate, the length of the periodic cycle, how many num- seeds[bf] n++
bers are generated before the cycle (delay), and the total xn+1 4xn(1  xn)
length of the sequence before the generator starts to repeat xn+1 float2BinFrac(xn+1)
terms. bf trunc(xn+1, bitsPrecision)
Given a finite seed space, the ideal sequence has a per- xn+1 binFrac2Float(bf)
iod equal to the cardinality of the space. Clearly, the effects if (seeds[bf] == SYMBOL) then
of truncation are detrimental to achieving the ideal se- xn = xn+1
quence period. For the 4-bit example, the maximum period else
of 5 is less than the ideal of 15. Moreover, many of the peri- periodic true
ods are even shorter, suggesting an extremely inefficient end if
use of the available seed space. This simple case exempli- end while
fies the challenges introduced by implementing a PRNG calculateCycles(seeds)
with truncated real numbers. As a result, the same bit end for
depth produces a far less random sequence than an inte-
ger-based generator achieves [9]. It is critical to under-
stand the effects of truncation in order to evaluate the
amount of randomness a chaotic PRNG is capable of
Certain design decisions balance trade-offs in flexibility
producing.
and performance. For example, restricting this algorithm to
single precision greatly reduces the data structure com-
3.2. Algorithm plexity. Likewise, calculations are much faster than if de-
signed to accommodate double precision. Contiguous
The FPPC algorithm performs the afore mentioned cal- blocks of memory make use of array indexing to efficiently
culations for a given recurrence relation. Our reference determine when the relation enters a periodic cycle. This is
implementation, written in ANSI C, performs calculations not possible for double precision numbers given the mem-
for bit depths up to single precision (binary32). Given a ory available on most computer systems. With some mod-
seed range and bit precision, FPPC calculates lengths and ifications to the data structures, this same approach
delays for each seed (Algorithm 1). Using a range of seeds applies to increased bit depths beyond those presented in
as input allows multiple copies of the same executable to this study.
run subsets of the entire seed space in parallel. As the In order to efficiently track previously generated xn, the
recurrence relation generates each term, FPPC tracks the binary fraction representation of each number replaces
output checking for duplicates. We initialize the array of IEEE 754-2008 binary32. The 23-bit representation of each
seeds with a symbol not in the seed space as a way to indi- number requires significantly less memory and allows for
cate whether or not a term repeats. The seeds array, in- easy truncation. This is an efficient solution for the logistic
dexed by each seed’s binary fraction representation, map since the seed space is defined as (0, 1). An additional
stores the time step when each number is generated. sign bit may be optionally added to accommodate other

Table 1
Logistic map series for a 4 bit significand.

Binary fraction x0 x1 trunc(x1) Sequence (x0, x1, . . . , xduplicate) Length Delay Total
0001 0.0625 0.234375 0.1875 0.0625, 0.1875, 0.5625, 0.9375, 0.1875 3 1 4
0010 0.1250 0.437500 0.4375 0.1250, 0.4375, 0.9375, 0.1875, 0.5625, 0.9375 3 2 5
0011 0.1875 0.609375 0.5625 0.1875, 0.5625, 0.9375, 0.1875 3 0 3
0100 0.2500 0.750000 0.7500 0.2500, 0.7500, 0.7500 1 1 2
0101 0.3125 0.859375 0.8125 0.3125, 0.8125, 0.5625, 0.9375, 0.1875, 0.5625 3 2 5
0110 0.3750 0.937500 0.9375 0.3750, 0.9375, 0.1875, 0.5625, 0.9375 3 1 4
0111 0.4375 0.984375 0.9375 0.4375, 0.9375, 0.1875, 0.5625, 0.9375 3 1 4
1000 0.5000 1.000000 1.0000 0.5000, 1.0000, 1.0000 1 1 2
1001 0.5625 0.984375 0.9375 0.5625, 0.9375, 0.1875, 0.5625 3 0 3
1010 0.6250 0.937500 0.9375 0.6250, 0.9375, 0.1875, 0.5625, 0.9375 3 1 4
1011 0.6875 0.859375 0.8125 0.6875, 0.8125, 0.5625, 0.9375, 0.1875, 0.5625 3 2 5
1100 0.7500 0.750000 0.7500 0.7500, 0.7500 1 0 1
1101 0.8125 0.609375 0.5625 0.8125, 0.5625, 0.9375, 0.1875, 0.5625 3 1 4
1110 0.8750 0.437500 0.4375 0.8750, 0.4375, 0.9375, 0.1875, 0.5625, 0.9375 3 2 5
1111 0.9375 0.234375 0.1875 0.9375, 0.1875, 0.5625, 0.9375 3 0 3
242 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245

recurrence relations seeded with (1, 1) at the cost of dou- Lastly, the truncated result requires conversion back to
bling the memory required to detect duplicates. binary32 representation before it can update the recur-
rence relation. Start by left-shifting the binary fraction un-
3.3. Restricting precision til the ‘‘implicit’’ 1 exits the mantissa region. The number
of shifts is subtracted from the exponent bias to determine
Another key feature of FPPC is its ability to restrict bit the value of the exponent bits. After discarding the implicit
precision lower than single precision. This feature serves 1, combine the leftover mantissa bits and the generated
two purposes: results verification and trend analysis of exponent via bitwise OR. Applying this process to (12)
period length vs. precision. The implementation of this fea- yields,
ture again makes use of the binary fraction number repre-
0 01111110 00100000000000000000000: ð13Þ
sentation. The normalized nature of IEEE 754-2008
floating-point numbers makes it difficult to truncate di- which is the normalized binary32 representation. Finally,
rectly. Conversely, a binary fraction can easily be truncated the unsigned integer bits are restored to a float type, thus
using a bitmask corresponding to the desired bits. completing the cycle.
To illustrate the entire process, consider an example As demonstrated previously, the effects of truncation
from Table 1, row 4. The decimal 0.1875 is used to seed can be studied manually for reasonable lesser degrees of
(5), which is represented in memory as precision, such as the 4-bit case presented in Table 1. We
have verified FPPC results for three, four, and five bits of
0 01111100 10000000000000000000000: ð6Þ
precision, which correspond, respectively, to base 10 preci-
The resulting term, decimal 0.609375, is represented by sions of 0.125 (1/8), 0.0625 (1/16), and 0.03125 (1/32).
Using this software truncation technique one can explore
0 01111110 00111000000000000000000: ð7Þ
the relationship between sequence period length and
In order to truncate (7) to a 4-bit representation, FPPC con- depth of precision.
verts the binary32 format to a denormalized binary frac-
tion. The float type requires conversion to an unsigned 3.4. Distributed computing implementation
integer containing bitwise representation. Next, right-shift
until the exponent bits become isolated and store this re- As FPPC utilizes more bits of precision, the number of
sult to another variable. At this point, the exponent and possible seeds and outcomes drastically increase. For sin-
signed bit from the original representation are discarded, gle precision and beyond the seed space is so large it be-
isolating the mantissa. Now bitwise OR the fraction bits comes unreasonable to calculate on a single computer.
with a 1 in position 23 (little endian) introducing the im- Single precision calculations performed on a single Intel
plicit 1 from the normalized representation, which Core 2 Duo workstation clocked at 2.26 GHz were very
produces time consuming. As the cardinality of the random number
0 00000001 00111000000000000000000: ð8Þ space approaches the order of 106, calculating all possible
outcomes approaches days of computing time instead of
Subtract the stored exponent bits from the bias (12710) to hours or minutes. Fortunately, each period calculation is
determine the denormalization shift. Finally, right-shift (8) independent of one another for a given seed. Under this
by this result to produce the resulting binary fraction, condition, seed ranges are easily distributed to multiple
0 00000000 10011100000000000000000: ð9Þ nodes in a distributed computing environment without
the need for communication between nodes. This enables
Now, envision the mantissa bits as if they had a leading many nodes to simultaneously determine the period of dif-
decimal point. As a sanity check, add the significant frac- ferent subsets of the entire random number space. After
tion bits, FPPC calculates the metrics for each seed (in parallel), a
1 0 0 1 1 1 post-processing job aggregates the output files into a uni-
þ þ þ þ þ ð10Þ fied result. Using this technique, the computation time
21 22 23 24 25 26
for higher degrees of precision becomes reasonable.
which of course equals 0.609375, as one would expect. FPPC is designed to run in a distributed high-through-
Truncating the binary fraction representation is quite put environment using Condor middleware [20]. The logis-
simple. First, generate a bitmask corresponding to the de- tic map example runs on Père, a homogeneous subset of
sired precision. For n bits, left-shift 1 n times and subtract the Marquette University distributed computing grid
1. This result gets left-shifted to the most significant bit of [16]. Père is comprised of 128 compute nodes each with
the mantissa. The 4-bit truncation mask is 8 Intel Nehalem 2.67 GHz cores. Even with the overhead
introduced by Condor’s job management, single precision
0 00000000 11110000000000000000000: ð11Þ FPPC calculations are reduced from several days on a single
machine to about 20 min on the cluster. High-throughput
Next, combine (9) and (11) with the bitwise AND opera-
computing enables the possibility to test precision beyond
tion, producing the truncated binary fraction
the binary32 format. In a parallel environment, random ac-
0 00000000 10010000000000000000000: ð12Þ cess memory (RAM) becomes a greater limiting factor than
processing power. FPPC requires enough memory to repre-
The decimal equivalent of (12) is 0.5625, which corre- sent all possible outcomes in order to detect when repeti-
sponds to the expected value shown in Table 1. tion occurs. The binary64 standard for floating-point
 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245 243

precision representation uses 8 bytes of memory for each As one might expect, the total period length generally
number [21]. Given m bytes of available heap memory, increases with more bits of precision. On some occasions,
FPPC can calculate periods for up to however, the length actually decreases for a 1-bit increase
   j m k in precision. This demonstrates that due to truncation ef-
available memory
log2 ¼ log2 ð14Þ fects, an increase in precision does not guarantee an in-
sizeof ðdoubleÞ 8
crease in period length. Interestingly, the maximum
bits of precision. Eq. (14) comes from dividing the available period length for single precision (23 bit significand) is sev-
system memory by the size of a double precision number. eral orders of magnitude smaller than that of the logistic
Flooring the base-2 logarithm of this result converts the ac- map’s conventional counter parts. Moreover, the linear
tual seed space size into the integer number of bits possible methods guarantee the maximum length (with correct
for binary representation without exceeding the system parameter selection), while the logistic map only produces
memory limitation. For example, each core on Père, has that sequence for a few select seeds. Fig. 2 also confirms
3 GiB of physical RAM. After accounting for the operating that the logistic map performs much worse than the LCG
system kernel, job management overhead, etc. there are [9] and the Mersenne Twister [15]. On top of these poor
approximately 2.75 GiB available for FPPC. Substituting performance characteristics, the logistic map has numer-
into (14) yields, ous pathological seeds that should deter anyone from
$ !% using it as a PRNG where the application requires long se-
2:75  230 quences of non-repetitive numbers.
log2 ¼ 28 bits: ð15Þ
8 For each bit depth, FPPC calculates the delay, length,
and total statistics introduced in the four bit example.
As it turns out, 23 bits successfully demonstrates the effects These arrays represent the number of times each period
of truncation on the logistic map so it is not necessary to ex- occurs. For example, the logistic map has seven unique cy-
haust these limits for this particular example. Of course, (15) cles (Table 2) when implemented in single precision (23 bit
assumes memory is allocated contiguously, as it is in this significand).
implementation of FPPC. Alternatively, any bookkeeping Although there are only a small number of periodic cy-
overhead needs consideration if a noncontiguous data struc- cles, the delay before landing on one of these orbits greatly
ture replaces the array to improve memory allocation varies. Combining the various delays with each periodic
efficiency. cycle yields numerous, but a finite number of, total series
elements before the generator repeats itself. Fig. 3 shows
4. Results

FPPC reveals poor periodicity characteristics for the lo- Table 2

gistic map represented in (5) when implemented as a Finite cycles of the logistic map in single precision.
PRNG. The truncation routine previously described simu- Period length Occurrences Frequency (%)
lates precision varying from 3-bits to 23-bits. Fig. 2 shows
1 238,675 2.8452
box and whiskers plots of the total period lengths with re- 2 502 0.0060
spect to bit depth. The ‘‘whiskers’’ illustrate minimum and 4 204 0.0024
maximum lengths and the box outlines the interquartile 115 49,998 0.5960
range (25th to 75th percentile). Moreover, the center line 123 211,896 2.5260
400 1,677,912 20.0023
depicts the median length. As indicated by the lower whis- 487 6,209,420 74.0221
ker, all depths of precision tested have pathological seeds
that result in minimum cycles of length 1 or 2.
4 4
10 10

3 3
10 10
Total Period Length

Occurrences

2 2
10 10

1 1
10 10

Total Length
0 0
Delay
10 10
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 500 1000 1500 2000 2500 3000 3500 4000
Bits of Precision Length

Fig. 2. Logistic map: periodicity vs. bits of precision. Fig. 3. Finite cycles of the logistic map (single precision).
244 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245

50
12
45

40 10
Parameter Space Utilization (%)

Effective Bits of Precision

35
8
30

25 6

20
4
15

10 2

5
0
0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Bits of Precision Actual Bits of Precision

Fig. 4. Parameter space utilization shows the total sequence lengths Fig. 5. Effective precision shows the number of bits utilized by the
normalized to the maximum length possible with a certain number of logistic map PRNG with respect to the bit depth of the seed space.
bits.

the occurrences of each delay and total cycle lengths for decreases severely. In single precision, the logistic map
single precision. Although the distribution of lengths is only uses a tiny fraction of a percent of the maximum pos-
not perfectly uniform, the general trend suggests undesir- sible sequence length. In contrast, integer based generators
able short lengths are similarly likely as the most robust are capable of guaranteeing 100% utilization before repeat-
lengths. A good PRNG should have rare pathological seeds, ing [9,15]. Simply providing the real number-based gener-
which are excluded from use if necessary. The distribution ator more memory does not increase its efficiency.
in Fig. 3 suggests the logistic map does not meet this Effective precision is another interesting metric for ana-
condition. lyzing the PRNG performance. For a good generator, the
Phatak and Rao determined the logistic map has six un- bits required to represent the sequence length should
ique periods using 105 seeds chosen by another PRNG [10]. equal the bits required to represent all possible outcomes.
The extra period FPPC finds is likely due to an exhaustive Fig. 5 shows the effective precision produced by the logis-
search. Regardless, the similarity between both results is tic map.
good validation that FPPC produces correct results. How- The effective precision is computed by taking the base-2
ever, there is a discrepancy between the exact cycle logarithm of the total period lengths. For almost every bit
lengths reported in [10] and those determined by FPPC. depth, the bits required to represent the sequence length
Phatak and Rao did not elaborate on their technique so it is less than half the bits available in memory. Again, this
is difficult to determine the cause of this difference. It is trend does not suggest that the efficiency of the logistic
possible that their periodicity detection was based on map will improve simply by increasing the available
when the logistic map hits fixed points, {0, 0.75, 1}. We sus- memory.
pect the study in [10] allowed the use of escalated preci- All of these metrics suggest the logistic map performs
sion for intermediate calculations. This could explain why poorly as a PRNG. It is clear that the truncation of the real
Phatak and Rao observed periodicity after approximately number floating-point representation is detrimental to the
5000 iterations, when truncation to zero occurs. In con- performance of this generator. Conversely, numerous stud-
trast, FPPC, which finds cycles based on any repeated value, ies [3,10,11] conclude the logistic map performs ade-
does not detect any periods larger than 4261. quately based on the results of many standardized
An ideal PRNG never repeats itself; however, an actual statistical tests. This discrepancy is simply due to the fact
implementation cannot meet this characteristic with a fi- that the statistical tests pass when applied to a sequence
nite amount of memory. Nevertheless, the best realistic that has not yet entered its periodic cycle. Phatak and
implementation maximizes the usage of its finite memory Rao explicitly describe rejecting terms beyond the region
allotment. In other words, the sequence length is equal to they determined to be aperiodic [10]. Jiang and Wu use
the size of the seed space for the best-performing realistic 100,000 iterations of the logistic map implemented in dou-
generator. ble precision [11]. As a result, the statistical tests pass be-
Fig. 4 demonstrates how poorly the logistic map utilizes cause the sequences are not periodic unless the length is
its available seed space. From Fig. 2 alone it seems reason- another order of magnitude larger [10]. In conclusion, the
able to keep increasing the bit of precision until a desired logistic map produces sufficiently uniform and uncorre-
length results. However, Fig. 4 demonstrates how ineffi- lated series; nonetheless, the length of these series is infe-
cient that approach is for the logistic map. Due to real rior relative to what a conventional generator produces
number truncation, the utilization of the available space given the same amount of memory.
 K.J. Persohn, R.J. Povinelli / Chaos, Solitons & Fractals 45 (2012) 238–245 245

5. Future work References

FPPC is primarily limited by the amount of memory re- [1] Alvarez G, Li S, Montoya F, Pastor G, Romera M. Breaking projective
chaos synchronization secure communication using filtering
quired to store sequence history. In order to enable effi- and generalized synchronization. Chaos Solitons Fract
cient exploration of double precision and beyond, a 2005;24(3):775–83.
creative coding scheme is required to represent this data. [2] Baptista MS. Cryptography with chaos. Phys Lett A 1998;240(1–
2):50–4.
As computing resources expand it will be necessary to [3] Andrecut M. Logistic map as a random number generator. Int J
study the effects of finite precision with larger and more Modern Phys B 1998;12(9):921–30.
complicated number representations. Extending FPPC with [4] Dachselt F, Schwarz W. Chaos and cryptography. IEEE Trans Circ Syst
I: Fundam Theory Appl 2001;48(12):1498–509.
modular data structures would enable it to grow alongside [5] Wang F, Zhang Y, Cao T. Research of chaotic block cipher algorithm
the data storage industry. The logistic map has been thor- based on logistic map. In: Second international conference on
oughly analyzed with respect to each of the ideal PRNG intelligent computation technology and automation, 2009,
ICICTA’09; 2009. p. 678 –81.
characteristics except for computational speed. Although
[6] Jakimoski G, Kocarev L. Chaos and cryptography: block encryption
some authors [3,10,11] have made loose claims about the ciphers based on chaotic maps. IEEE Trans Circ Syst I: Fundam
efficiency of the logistic map, it has yet to be quantitatively Theory Appl 2001;48(2):163–9.
[7] Xiao D, Liao X, Deng S. One-way hash function construction based on
benchmarked against other algorithms. Understanding the
the chaotic map with changeable-parameter. Chaos Solitons Fract
tradeoffs between computational performance and ran- 2005;24(1):65–71.
domness is key to determining if the logistic map can make [8] Park SK, Miller KW. Random number generators: good ones are hard
up for what it lacks in periodicity with generation speed. to find. Commun ACM 1988;31(10):1192–201.
[9] Knuth DE. The Art of Computer Programming, 2nd ed., vol.
2. Addison Wesley; 1981.
6. Conclusion [10] Phatak SC, Rao SS. Logistic map: a possible random-number
generator. Phys Rev E 1995;51(4):3670–8.
[11] Jiang C, Wu S. A valid algorithm of converting chaos sequences to
Real number implementations in finite precision are det- uniformity pseudo-random ones. In: International symposium on
rimental to the periodicity of chaotic PRNGs. Ignoring this information engineering and electronic commerce, 2009, IEEC’09;
2009. p. 295–8.
reality makes chaos-based PRNGs deceptively appealing [12] Ferrenberg AM, Landau DP, Wong YJ. Monte Carlo simulations:
for random applications. FPPC algorithm can comprehen- hidden errors from ‘‘good’’ random number generators. Phys Rev
sively analyze the periodicity of truncated real number ser- Lett 1992;69(23):3382–4.
[13] Lehmer DH. Mathematical methods in large-scale computing units.
ies generated by a recurrence relation. Using these results Ann Comput Lab Harvard Univ 1951;26:141–6.
one can make informed decisions about the appropriate [14] Oracle. Java 2 platform se random class. <http://download.oracle.
use of a chaotic PRNG with respect to its conventional coun- com/javase/1.4.2/docs/api/java/util/Random.html>; 2010.
[15] Matsumoto M, Nishimura T. Mersenne twister: a 623-dimensionally
ter-parts. The results revealed about the logistic map do not
equidistributed uniform pseudo-random number generator. Trans
appear competitive with conventional PRNGs. Model Comput Simul 1998;8(1):3–30.
[16] Matsumoto M, Nishimura T, Hagita M, Saito M. Cryptographic
Mersenne twister and Fubaki stream/block cipher, cryptology ePrint
Acknowledgment archive, Report 2005/165; 2005.
[17] Kocarev L. Chaos-based cryptography: a brief overview. IEEE Circ
This research was funded in part by National Science Syst Mag 2001;1(3):6–21.
[18] Alvarez G, Li S. Some basic cryptographic requirements for chaos-
Foundation awards OCI-0923037 ‘‘MRI: Acquisition of a
based cryptosystems. Int J Bifurcat Chaos 2006;16:2129–51.
Parallel Computing Cluster and Storage for the Marquette [19] Feigenbaum MJ. Quantitative universality for a class of nonlinear
University Grid (MUGrid)’’ and CBET-0521602 ‘‘Acquisition transformations. J Stat Phys 1978;19(1):25–52.
of a Linux Cluster to Support College-Wide Research & [20] Condor high throughput computing. <http://www.cs.wisc.edu/
condor/>.
Teaching Activities.’’ K. J. Persohn is funded by the Greater [21] Standard for floating-point arithmetic, Tech. Rep. 754-2008, IEEE;
Milwaukee Foundation’s Frank Rogers Bacon Fellowship. 2008.