DOI: 10.1145/189443.189445. Twisted GFSR generators II

10.1145/189443.189445

Crossref journal-article

Association for Computing Machinery (ACM)

ACM Transactions on Modeling and Computer Simulation (320)

Abstract

The twisted GFSR generators proposed in a previous article have a defect in k -distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k -distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.

Bibliography

Matsumoto, M., & Kurita, Y. (1994). Twisted GFSR generators II. ACM Transactions on Modeling and Computer Simulation, 4(3), 254â266.

Authors 2

Makoto Matsumoto (first)
Yoshiharu Kurita (additional)

References 9 Referenced 118

FREDRICSSON , S.A. 1975 . Pseudo-randomness properties of binary shift register sequences . IEEE Trans. Inf. Theory IT-21, 115-120 FREDRICSSON, S.A. 1975. Pseudo-randomness properties of binary shift register sequences. IEEE Trans. Inf. Theory IT-21, 115-120 (10.1109/TIT.1975.1055310) / IEEE Trans. Inf. Theory IT-21, 115-120 / Pseudo-randomness properties of binary shift register sequences by FREDRICSSON S.A. (1975)
10.1016/0377-0427(90)90341-V
FUSmMI M. AND TEZUKA S. 1983 The k-distribution of generahzed feedback shift register pseudorandom numbers. Commun. ACM 2G 516-523. 10.1145/358150.358159 FUSmMI M. AND TEZUKA S. 1983 The k-distribution of generahzed feedback shift register pseudorandom numbers. Commun. ACM 2G 516-523. 10.1145/358150.358159 (10.1145/358150.358159)
KNUTH , D. E. 1981. The Art of Computer Programming . Vol. 2 . Sem~numerzcal Algomthms, 2 nd ed. Addison-Wesley , Reading, Mass. KNUTH, D. E. 1981. The Art of Computer Programming. Vol. 2. Sem~numerzcal Algomthms, 2nd ed. Addison-Wesley, Reading, Mass. / The Art of Computer Programming by KNUTH D. E.
L'ECUYER , P. 1992 . Testing random number generators . In Proceedtngs of the 1992 Winter S~mulation Conference. IEEE , New York , 305 - 313 . 10.1145/167293.167354 L'ECUYER, P. 1992. Testing random number generators. In Proceedtngs of the 1992 Winter S~mulation Conference. IEEE, New York, 305-313. 10.1145/167293.167354 / Proceedtngs of the 1992 Winter S~mulation Conference. IEEE by L'ECUYER P. (1992)
L'ECU~ER P. 1994. Uniform random number generation. An. Oper. Res. To be published. L'ECU~ER P. 1994. Uniform random number generation. An. Oper. Res. To be published. (10.1007/BF02136827)
LINDHOLM , J. H. 1968 . An analysis of the pseudo-randomness properties of subsequences of long m-sequences . IEEE Trans. lnf. Theory IT-14 ( July ), 569 576. LINDHOLM, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. lnf. Theory IT-14 (July), 569 576. / Theory IT-14 / An analysis of the pseudo-randomness properties of subsequences of long m-sequences by LINDHOLM J. H. (1968)
10.1145/146382.146383
10.1145/321765.321778

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:28 a.m.)
Deposited	2 months, 2 weeks ago (June 18, 2025, 6:52 a.m.)
Indexed	2 months, 2 weeks ago (June 18, 2025, 7:10 a.m.)
Issued	31 years, 2 months ago (July 1, 1994)
Published	31 years, 2 months ago (July 1, 1994)
Published Online	31 years, 2 months ago (July 1, 1994)
Published Print	31 years, 2 months ago (July 1, 1994)

Funders 0

None

BibTeX

@article{Matsumoto_1994, title={Twisted GFSR generators II}, volume={4}, ISSN={1558-1195}, url={http://dx.doi.org/10.1145/189443.189445}, DOI={10.1145/189443.189445}, number={3}, journal={ACM Transactions on Modeling and Computer Simulation}, publisher={Association for Computing Machinery (ACM)}, author={Matsumoto, Makoto and Kurita, Yoshiharu}, year={1994}, month=jul, pages={254–266} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T11:10:01Z",
    "timestamp": 1750245001319,
    "version": "3.41.0"
  },
  "reference-count": 9,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1994,
            7,
            1
          ]
        ],
        "date-time": "1994-07-01T00:00:00Z",
        "timestamp": 773020800000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1994,
        7
      ]
    ]
  },
  "abstract": "<jats:p>\n            The twisted GFSR generators proposed in a previous article have a defect in\n            <jats:italic>k</jats:italic>\n            -distribution for\n            <jats:italic>k</jats:italic>\n            larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better\n            <jats:italic>k</jats:italic>\n            -distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.\n          </jats:p>",
  "DOI": "10.1145/189443.189445",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:28:46Z",
    "timestamp": 1027769326000
  },
  "page": "254-266",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 118,
  "title": "Twisted GFSR generators II",
  "prefix": "10.1145",
  "volume": "4",
  "author": [
    {
      "given": "Makoto",
      "family": "Matsumoto",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Kyoto Univ., Kyoto, Japan"
        }
      ]
    },
    {
      "given": "Yoshiharu",
      "family": "Kurita",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "National Research Lab of Metrology, Tsukuba, Japan"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1994,
        7
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_1",
      "doi-asserted-by": "crossref",
      "DOI": "10.1109/TIT.1975.1055310",
      "article-title": "Pseudo-randomness properties of binary shift register sequences",
      "author": "FREDRICSSON S.A.",
      "year": "1975",
      "unstructured": "FREDRICSSON , S.A. 1975 . Pseudo-randomness properties of binary shift register sequences . IEEE Trans. Inf. Theory IT-21, 115-120 FREDRICSSON, S.A. 1975. Pseudo-randomness properties of binary shift register sequences. IEEE Trans. Inf. Theory IT-21, 115-120",
      "journal-title": "IEEE Trans. Inf. Theory IT-21, 115-120"
    },
    {
      "key": "e_1_2_1_2_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0377-0427(90)90341-V"
    },
    {
      "key": "e_1_2_1_3_1",
      "doi-asserted-by": "crossref",
      "unstructured": "FUSmMI M. AND TEZUKA S. 1983 The k-distribution of generahzed feedback shift register pseudorandom numbers. Commun. ACM 2G 516-523. 10.1145/358150.358159   FUSmMI M. AND TEZUKA S. 1983 The k-distribution of generahzed feedback shift register pseudorandom numbers. Commun. ACM 2G 516-523. 10.1145/358150.358159",
      "DOI": "10.1145/358150.358159"
    },
    {
      "key": "e_1_2_1_4_1",
      "volume-title": "The Art of Computer Programming",
      "author": "KNUTH D. E.",
      "unstructured": "KNUTH , D. E. 1981. The Art of Computer Programming . Vol. 2 . Sem~numerzcal Algomthms, 2 nd ed. Addison-Wesley , Reading, Mass. KNUTH, D. E. 1981. The Art of Computer Programming. Vol. 2. Sem~numerzcal Algomthms, 2nd ed. Addison-Wesley, Reading, Mass.",
      "edition": "2"
    },
    {
      "key": "e_1_2_1_5_1",
      "first-page": "305",
      "volume-title": "Proceedtngs of the 1992 Winter S~mulation Conference. IEEE",
      "author": "L'ECUYER P.",
      "year": "1992",
      "unstructured": "L'ECUYER , P. 1992 . Testing random number generators . In Proceedtngs of the 1992 Winter S~mulation Conference. IEEE , New York , 305 - 313 . 10.1145/167293.167354 L'ECUYER, P. 1992. Testing random number generators. In Proceedtngs of the 1992 Winter S~mulation Conference. IEEE, New York, 305-313. 10.1145/167293.167354"
    },
    {
      "key": "e_1_2_1_6_1",
      "doi-asserted-by": "crossref",
      "unstructured": "L'ECU~ER P. 1994. Uniform random number generation. An. Oper. Res. To be published.  L'ECU~ER P. 1994. Uniform random number generation. An. Oper. Res. To be published.",
      "DOI": "10.1007/BF02136827"
    },
    {
      "key": "e_1_2_1_7_1",
      "first-page": "569",
      "article-title": "An analysis of the pseudo-randomness properties of subsequences of long m-sequences",
      "author": "LINDHOLM J. H.",
      "year": "1968",
      "unstructured": "LINDHOLM , J. H. 1968 . An analysis of the pseudo-randomness properties of subsequences of long m-sequences . IEEE Trans. lnf. Theory IT-14 ( July ), 569 576. LINDHOLM, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. lnf. Theory IT-14 (July), 569 576.",
      "journal-title": "Theory IT-14"
    },
    {
      "key": "e_1_2_1_8_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/146382.146383"
    },
    {
      "key": "e_1_2_1_9_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/321765.321778"
    }
  ],
  "container-title": "ACM Transactions on Modeling and Computer Simulation",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/189443.189445",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/189443.189445",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T10:52:35Z",
    "timestamp": 1750243955000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/189443.189445"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1994,
        7
      ]
    ]
  },
  "references-count": 9,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          1994,
          7
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/189443.189445"
  ],
  "URL": "http://dx.doi.org/10.1145/189443.189445",
  "relation": {},
  "ISSN": [
    "1049-3301",
    "1558-1195"
  ],
  "subject": [],
  "container-title-short": "ACM Trans. Model. Comput. Simul.",
  "published": {
    "date-parts": [
      [
        1994,
        7
      ]
    ]
  },
  "assertion": [
    {
      "value": "1994-07-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}