Engineering Nonlinear Pseudorandom Number Generators View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014-05-06

AUTHORS

Samuel Neves , Filipe Araujo

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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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", 
        "givenName": "Konrad", 
        "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", 
      "tradeoff", 
      "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-10-01T06:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_398.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-55224-3_10"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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'

Turtle is a human-readable linked data format.

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
1 sg:pub.10.1007/978-3-642-55224-3_10 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nb2ff189c804e4df4ae57ef1a285e6509
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 Nad0cbde93bb14834821501780e7ff525
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N0b7ded3aa1874347a702fc42f01fc5ee
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
60 tradeoff
61 schema:name Engineering Nonlinear Pseudorandom Number Generators
62 schema:pagination 96-105
63 schema:productId Na16a5b57fa0f41f39972b47aecc25dbb
64 Ne114f580ce374bb4a08114dccdc22b97
65 schema:publisher N01e886bb8a09482c9292a520c0c73384
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-10-01T06:58
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N5502f9d4813f4df08c9c369e8158774d
71 schema:url https://doi.org/10.1007/978-3-642-55224-3_10
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N01e886bb8a09482c9292a520c0c73384 schema:name Springer Nature
76 rdf:type schema:Organisation
77 N0b7ded3aa1874347a702fc42f01fc5ee schema:isbn 978-3-642-55223-6
78 978-3-642-55224-3
79 schema:name Parallel Processing and Applied Mathematics
80 rdf:type schema:Book
81 N16454106908c441e8ba4c8e0b577eadd rdf:first Nfef223fc1eb0443ea6a68cb74208b736
82 rdf:rest Ned03bdf6cae5455ca053c196ed495d60
83 N1f0ea67314144a6ebc5d541de832d671 rdf:first N30d622f89ee04cd1b8a4590c5f805276
84 rdf:rest N16454106908c441e8ba4c8e0b577eadd
85 N30d622f89ee04cd1b8a4590c5f805276 schema:familyName Dongarra
86 schema:givenName Jack
87 rdf:type schema:Person
88 N5502f9d4813f4df08c9c369e8158774d schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 N8438d13d1d3f4f0c85d3685fef8ed043 rdf:first sg:person.01165636016.38
91 rdf:rest rdf:nil
92 Na16a5b57fa0f41f39972b47aecc25dbb schema:name dimensions_id
93 schema:value pub.1043239860
94 rdf:type schema:PropertyValue
95 Nad0cbde93bb14834821501780e7ff525 rdf:first Nf3ca3d94e3264003a6642f05bb4dc440
96 rdf:rest N1f0ea67314144a6ebc5d541de832d671
97 Nb2ff189c804e4df4ae57ef1a285e6509 rdf:first sg:person.011136377232.42
98 rdf:rest N8438d13d1d3f4f0c85d3685fef8ed043
99 Ncea67b5ccbc44522a94252caffd7ad81 schema:familyName Waśniewski
100 schema:givenName Jerzy
101 rdf:type schema:Person
102 Ne114f580ce374bb4a08114dccdc22b97 schema:name doi
103 schema:value 10.1007/978-3-642-55224-3_10
104 rdf:type schema:PropertyValue
105 Ned03bdf6cae5455ca053c196ed495d60 rdf:first Ncea67b5ccbc44522a94252caffd7ad81
106 rdf:rest rdf:nil
107 Nf3ca3d94e3264003a6642f05bb4dc440 schema:familyName Wyrzykowski
108 schema:givenName Roman
109 rdf:type schema:Person
110 Nfef223fc1eb0443ea6a68cb74208b736 schema:familyName Karczewski
111 schema:givenName Konrad
112 rdf:type schema:Person
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
 




Preview window. Press ESC to close (or click here)


...