# Engineering Nonlinear Pseudorandom Number Generators

Ontology type: schema:Chapter

### Chapter Info

DATE

2014-05-06

AUTHORS ABSTRACT

In the era of multi and many-core processors, computer simulations increasingly require parallel, small and fast pseudorandom number generation. Although linear generators lend themselves to a simpler evaluation that ensures favorable properties like guaranteed period, they may adversely affect the result of simulations or be quite large. Conversely, nonlinear generators may provide apparently random sequences, but are either very slow or difficult to analyze regarding their period.This is the case of our previous functions, Tyche and Tyche-i. Despite being among the fastest in their class and having average periods of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{127}$$\end{document}, they may contain smaller cycles of arbitrary size. To overcome this limitation, in this paper we explore different forms of counters impacting either the state or the speed of the generator. We also introduce two number-theoretic generators that use \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \times 127$$\end{document} bits for periods of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{116}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{125}$$\end{document} and low to moderate computational costs. We experimentally demonstrate the efficiency of our new generators and observe that they exchange speed for period guarantees in a tradeoff that seems widespread in state-of-the-art random number generators. More... »

PAGES

96-105

### Book

TITLE

Parallel Processing and Applied Mathematics

ISBN

978-3-642-55223-6
978-3-642-55224-3

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-55224-3_10

DOI

http://dx.doi.org/10.1007/978-3-642-55224-3_10

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1043239860

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal",
"id": "http://www.grid.ac/institutes/grid.8051.c",
"name": [
"CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal"
],
"type": "Organization"
},
"familyName": "Neves",
"givenName": "Samuel",
"id": "sg:person.011136377232.42",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011136377232.42"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal",
"id": "http://www.grid.ac/institutes/grid.8051.c",
"name": [
"CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal"
],
"type": "Organization"
},
"familyName": "Araujo",
"givenName": "Filipe",
"id": "sg:person.01165636016.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165636016.38"
],
"type": "Person"
}
],
"datePublished": "2014-05-06",
"datePublishedReg": "2014-05-06",
"description": "In the era of multi and many-core processors, computer simulations increasingly require parallel, small and fast pseudorandom number generation. Although linear generators lend themselves to a simpler evaluation that ensures favorable properties like guaranteed period, they may adversely affect the result of simulations or be quite large. Conversely, nonlinear generators may provide apparently random sequences, but are either very slow or difficult to analyze regarding their period.This is the case of our previous functions, Tyche and Tyche-i. Despite being among the fastest in their class and having average periods of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{127}$$\\end{document}, they may contain smaller cycles of arbitrary size. To overcome this limitation, in this paper we explore different forms of counters impacting either the state or the speed of the generator. We also introduce two number-theoretic generators that use \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2 \\times 127$$\\end{document} bits for periods of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{116}$$\\end{document} and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{125}$$\\end{document} and low to moderate computational costs. We experimentally demonstrate the efficiency of our new generators and observe that they exchange speed for period guarantees in a tradeoff that seems widespread in state-of-the-art random number generators.",
"editor": [
{
"familyName": "Wyrzykowski",
"givenName": "Roman",
"type": "Person"
},
{
"familyName": "Dongarra",
"givenName": "Jack",
"type": "Person"
},
{
"familyName": "Karczewski",
"type": "Person"
},
{
"familyName": "Wa\u015bniewski",
"givenName": "Jerzy",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-55224-3_10",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-55223-6",
"978-3-642-55224-3"
],
"name": "Parallel Processing and Applied Mathematics",
"type": "Book"
},
"keywords": [
"number generator",
"nonlinear pseudorandom number generators",
"number-theoretic generators",
"pseudorandom number generation",
"random number generator",
"pseudorandom number generators",
"moderate computational cost",
"nonlinear generators",
"number generation",
"computational cost",
"arbitrary size",
"results of simulation",
"computer simulations",
"random sequence",
"new generator",
"linear generator",
"small cycles",
"simple evaluation",
"generator",
"simulations",
"favorable properties",
"speed",
"core processors",
"guarantees",
"class",
"previous functions",
"Tyche",
"state",
"properties",
"function",
"processors",
"bits",
"form",
"efficiency",
"cases",
"different forms",
"results",
"cost",
"size",
"limitations",
"generation",
"sequence",
"counter",
"evaluation",
"average period",
"cycle",
"period",
"era",
"paper"
],
"name": "Engineering Nonlinear Pseudorandom Number Generators",
"pagination": "96-105",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1043239860"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-55224-3_10"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-55224-3_10",
"https://app.dimensions.ai/details/publication/pub.1043239860"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-12-01T06:49",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_240.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-55224-3_10"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-55224-3_10'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-55224-3_10'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-55224-3_10'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-55224-3_10'

This table displays all metadata directly associated to this object as RDF triples.

131 TRIPLES      22 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0102
3 schema:author N46176b2c11c2430694be64984aa9b20c
4 schema:datePublished 2014-05-06
5 schema:datePublishedReg 2014-05-06
6 schema:description In the era of multi and many-core processors, computer simulations increasingly require parallel, small and fast pseudorandom number generation. Although linear generators lend themselves to a simpler evaluation that ensures favorable properties like guaranteed period, they may adversely affect the result of simulations or be quite large. Conversely, nonlinear generators may provide apparently random sequences, but are either very slow or difficult to analyze regarding their period.This is the case of our previous functions, Tyche and Tyche-i. Despite being among the fastest in their class and having average periods of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{127}$$\end{document}, they may contain smaller cycles of arbitrary size. To overcome this limitation, in this paper we explore different forms of counters impacting either the state or the speed of the generator. We also introduce two number-theoretic generators that use \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \times 127$$\end{document} bits for periods of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{116}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{125}$$\end{document} and low to moderate computational costs. We experimentally demonstrate the efficiency of our new generators and observe that they exchange speed for period guarantees in a tradeoff that seems widespread in state-of-the-art random number generators.
7 schema:editor N4e889f144af841198aca7a84a6d6a48b
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ne0caabc3436240f6899bee3972a1dc5d
11 schema:keywords Tyche
12 arbitrary size
13 average period
14 bits
15 cases
16 class
17 computational cost
18 computer simulations
19 core processors
20 cost
21 counter
22 cycle
23 different forms
24 efficiency
25 era
26 evaluation
27 favorable properties
28 form
29 function
30 generation
31 generator
32 guarantees
33 limitations
34 linear generator
35 moderate computational cost
36 new generator
37 nonlinear generators
38 nonlinear pseudorandom number generators
39 number generation
40 number generator
41 number-theoretic generators
42 paper
43 period
44 previous functions
45 processors
46 properties
47 pseudorandom number generation
48 pseudorandom number generators
49 random number generator
50 random sequence
51 results
52 results of simulation
53 sequence
54 simple evaluation
55 simulations
56 size
57 small cycles
58 speed
59 state
61 schema:name Engineering Nonlinear Pseudorandom Number Generators
62 schema:pagination 96-105
63 schema:productId N7a0797b1ac924c2abe28029b1118a641
64 Nf00a9780c4574a50b0233f5bf35efa34
65 schema:publisher Ndb245db6ce76456a93f83d0b72144b76
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043239860
67 https://doi.org/10.1007/978-3-642-55224-3_10
68 schema:sdDatePublished 2022-12-01T06:49
70 schema:sdPublisher Nb8084d8959c94020987f34bd0b981e01
71 schema:url https://doi.org/10.1007/978-3-642-55224-3_10
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N303299c7225f4baeb8f08c14f73899f5 schema:familyName Karczewski
77 rdf:type schema:Person
78 N3254da3a7cae4720b9d1081992dba5af schema:familyName Dongarra
79 schema:givenName Jack
80 rdf:type schema:Person
81 N46176b2c11c2430694be64984aa9b20c rdf:first sg:person.011136377232.42
82 rdf:rest N5b4931f0752f4eec8f48f44a7b8e4e7f
84 rdf:rest N8652d681ed0648f090161693a511527d
86 rdf:rest rdf:nil
87 N5b4931f0752f4eec8f48f44a7b8e4e7f rdf:first sg:person.01165636016.38
88 rdf:rest rdf:nil
89 N7a0797b1ac924c2abe28029b1118a641 schema:name dimensions_id
90 schema:value pub.1043239860
91 rdf:type schema:PropertyValue
92 N8652d681ed0648f090161693a511527d rdf:first N3254da3a7cae4720b9d1081992dba5af
93 rdf:rest Na41573458bf54c2aa868909e37c173eb
95 schema:givenName Jerzy
96 rdf:type schema:Person
97 Na41573458bf54c2aa868909e37c173eb rdf:first N303299c7225f4baeb8f08c14f73899f5
98 rdf:rest N522d3c25c6294ea08b9d562e86cf3d0d
99 Nb8084d8959c94020987f34bd0b981e01 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 Ndb245db6ce76456a93f83d0b72144b76 schema:name Springer Nature
102 rdf:type schema:Organisation
104 schema:givenName Roman
105 rdf:type schema:Person
106 Ne0caabc3436240f6899bee3972a1dc5d schema:isbn 978-3-642-55223-6
107 978-3-642-55224-3
108 schema:name Parallel Processing and Applied Mathematics
109 rdf:type schema:Book
110 Nf00a9780c4574a50b0233f5bf35efa34 schema:name doi
111 schema:value 10.1007/978-3-642-55224-3_10
112 rdf:type schema:PropertyValue
113 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
114 schema:name Mathematical Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
117 schema:name Applied Mathematics
118 rdf:type schema:DefinedTerm
119 sg:person.011136377232.42 schema:affiliation grid-institutes:grid.8051.c
120 schema:familyName Neves
121 schema:givenName Samuel
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011136377232.42
123 rdf:type schema:Person
124 sg:person.01165636016.38 schema:affiliation grid-institutes:grid.8051.c
125 schema:familyName Araujo
126 schema:givenName Filipe
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165636016.38
128 rdf:type schema:Person
129 grid-institutes:grid.8051.c schema:alternateName CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
130 schema:name CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
131 rdf:type schema:Organization