DOI: 10.1145/42372.42381. Binomial random variate generation

10.1145/42372.42381

Crossref journal-article

Association for Computing Machinery (ACM)

Communications of the ACM (320)

Abstract

Existing binomial random-variate generators are surveyed, and a new generator designed for moderate and large means is developed. The new algorithm, BTPE, has fixed memory requirements and is faster than other such algorithms, both when single, or when many variates are needed.

Bibliography

Kachitvichyanukul, V., & Schmeiser, B. W. (1988). Binomial random variate generation. Communications of the ACM, 31(2), 216â222.

Authors 2

Voratas Kachitvichyanukul (first)
Bruce W. Schmeiser (additional)

References 26 Referenced 84

Abramowitz , M. , and Stegun , I.A . Handbook of Mathematical Functions , National Bureau of Standards , Applied Mathematics Series 55, June 1964 . Abramowitz, M., and Stegun, I.A. Handbook of Mathematical Functions, National Bureau of Standards, Applied Mathematics Series 55, June 1964. / Handbook of Mathematical Functions by Abramowitz M. (1964)
10.1007/BF02293108
10.1007/BF02241999
10.1145/355993.355997
Atkinson , A.C . The computer generation of poisson random variables , Applied Statistics 28 , 1 , 1979 , 29-35. Atkinson, A.C. The computer generation of poisson random variables, Applied Statistics 28, 1, 1979, 29-35. / Applied Statistics / The computer generation of poisson random variables by Atkinson A.C (1979)
Atkinson , A.C . Recent developments in the computer generation of poisson random variables , Applied Statistics 28 , 3 , 1979 , 260-263. Atkinson, A.C. Recent developments in the computer generation of poisson random variables, Applied Statistics 28, 3, 1979, 260-263. / Applied Statistics / Recent developments in the computer generation of poisson random variables by Atkinson A.C (1979)
10.5555/17320
10.1080/05695557408974949
10.1145/359460.359482
10.1007/BF02243478
Devroye , L. " The Computer Generation of Binomial Random Variables,'' Technical Report , McGill University , Montreal , Quebec , Canada , 1980 . Devroye, L. "The Computer Generation of Binomial Random Variables,'' Technical Report, McGill University, Montreal, Quebec, Canada, 1980. / Montreal by Devroye L. (1980)
10.1016/0898-1221(80)90039-5
Feller , W. An Introduction to Probability Theory and Its Applications , Volume 1 , Wiley , New York , 1968 . Feller, W. An Introduction to Probability Theory and Its Applications, Volume 1, Wiley, New York, 1968. / An Introduction to Probability Theory and Its Applications by Feller W. (1968)
10.1007/BF02276759
Fishman , G.S. Principles of Discrete Event Simulation , Wiley , New York , 1978 . Fishman, G.S. Principles of Discrete Event Simulation, Wiley, New York, 1978. / Principles of Discrete Event Simulation by Fishman G.S. (1978)
Fishman , G.S . Sampling from the binomial distribution on a computer , Journal of the American Statistical Association 74 , 366 , 1979 , 418-423. Fishman, G.S. Sampling from the binomial distribution on a computer, Journal of the American Statistical Association 74, 366, 1979, 418-423. / Journal of the American Statistical Association / Sampling from the binomial distribution on a computer by Fishman G.S (1979)
Fishman , G.S. , and Moore , L.R . Sampling from a discrete distribution while preserving monotonicity , The American Statistician 38 , 3 1984 , 219-223. Fishman, G.S., and Moore, L.R. Sampling from a discrete distribution while preserving monotonicity, The American Statistician 38, 3 1984, 219-223. (10.1080/00031305.1984.10483208) / The American Statistician / Sampling from a discrete distribution while preserving monotonicity by Fishman G.S. (1984)
10.1080/01621459.1976.10480965
10.1080/00031305.1979.10482697
10.1080/01621459.1972.10481259
Schmeiser , B.W. " Random Variate Generation : A Survey." In Simulation with Discrete Models: A State-of-the-Art View, T.I. Oren, C.M. Shub, and P.F. Roth (eds.) . In Proceedings of the 1980 Winter Simulation Conference, IEEE , 1980 , 79 - 104 . Schmeiser, B.W. "Random Variate Generation: A Survey." In Simulation with Discrete Models: A State-of-the-Art View, T.I. Oren, C.M. Shub, and P.F. Roth (eds.). In Proceedings of the 1980 Winter Simulation Conference, IEEE, 1980, 79-104. / Proceedings of the 1980 Winter Simulation Conference, IEEE by Schmeiser B.W. (1980)
Schmeiser , B.W. " Random Variate Generation ." In Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE , 1981 , 227 - 242 . Schmeiser, B.W. "Random Variate Generation." In Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE, 1981, 227-242. / Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE by Schmeiser B.W. (1981)
10.1287/opre.28.4.917
Schmeiser , B.W. , and Kachitvichyanukul , V . " Poisson Random Varlate Generation," Research Memorandum 81-4 , Purdue University , 1981 . Schmeiser, B.W., and Kachitvichyanukul, V. "Poisson Random Varlate Generation," Research Memorandum 81-4, Purdue University, 1981. / Poisson Random Varlate Generation," Research Memorandum 81-4 by Schmeiser B.W. (1981)
10.1145/318242.318445
10.1145/355744.355749

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:38 a.m.)
Deposited	2 months, 2 weeks ago (June 18, 2025, 5:14 p.m.)
Indexed	1 month ago (July 30, 2025, 10:45 a.m.)
Issued	37 years, 7 months ago (Feb. 1, 1988)
Published	37 years, 7 months ago (Feb. 1, 1988)
Published Online	37 years, 7 months ago (Feb. 1, 1988)
Published Print	37 years, 7 months ago (Feb. 1, 1988)

Funders 0

None

BibTeX

@article{Kachitvichyanukul_1988, title={Binomial random variate generation}, volume={31}, ISSN={1557-7317}, url={http://dx.doi.org/10.1145/42372.42381}, DOI={10.1145/42372.42381}, number={2}, journal={Communications of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Kachitvichyanukul, Voratas and Schmeiser, Bruce W.}, year={1988}, month=feb, pages={216–222} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        30
      ]
    ],
    "date-time": "2025-07-30T14:45:09Z",
    "timestamp": 1753886709913,
    "version": "3.41.0"
  },
  "reference-count": 26,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "2",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1988,
            2,
            1
          ]
        ],
        "date-time": "1988-02-01T00:00:00Z",
        "timestamp": 570672000000
      },
      "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": [
      [
        1988,
        2
      ]
    ]
  },
  "abstract": "<jats:p>Existing binomial random-variate generators are surveyed, and a new generator designed for moderate and large means is developed. The new algorithm, BTPE, has fixed memory requirements and is faster than other such algorithms, both when single, or when many variates are needed.</jats:p>",
  "DOI": "10.1145/42372.42381",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:38:11Z",
    "timestamp": 1027769891000
  },
  "page": "216-222",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 84,
  "title": "Binomial random variate generation",
  "prefix": "10.1145",
  "volume": "31",
  "author": [
    {
      "given": "Voratas",
      "family": "Kachitvichyanukul",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Univ. of Iowa, Iowa City"
        }
      ]
    },
    {
      "given": "Bruce W.",
      "family": "Schmeiser",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Purdue Univ., West Lafayette, IN"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_2",
      "volume-title": "Handbook of Mathematical Functions",
      "author": "Abramowitz M.",
      "year": "1964",
      "unstructured": "Abramowitz , M. , and Stegun , I.A . Handbook of Mathematical Functions , National Bureau of Standards , Applied Mathematics Series 55, June 1964 . Abramowitz, M., and Stegun, I.A. Handbook of Mathematical Functions, National Bureau of Standards, Applied Mathematics Series 55, June 1964."
    },
    {
      "key": "e_1_2_1_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02293108"
    },
    {
      "key": "e_1_2_1_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02241999"
    },
    {
      "key": "e_1_2_1_4_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/355993.355997"
    },
    {
      "key": "e_1_2_1_5_2",
      "first-page": "1",
      "article-title": "The computer generation of poisson random variables",
      "volume": "28",
      "author": "Atkinson A.C",
      "year": "1979",
      "unstructured": "Atkinson , A.C . The computer generation of poisson random variables , Applied Statistics 28 , 1 , 1979 , 29-35. Atkinson, A.C. The computer generation of poisson random variables, Applied Statistics 28, 1, 1979, 29-35.",
      "journal-title": "Applied Statistics"
    },
    {
      "key": "e_1_2_1_6_2",
      "first-page": "3",
      "article-title": "Recent developments in the computer generation of poisson random variables",
      "volume": "28",
      "author": "Atkinson A.C",
      "year": "1979",
      "unstructured": "Atkinson , A.C . Recent developments in the computer generation of poisson random variables , Applied Statistics 28 , 3 , 1979 , 260-263. Atkinson, A.C. Recent developments in the computer generation of poisson random variables, Applied Statistics 28, 3, 1979, 260-263.",
      "journal-title": "Applied Statistics"
    },
    {
      "key": "e_1_2_1_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.5555/17320"
    },
    {
      "key": "e_1_2_1_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/05695557408974949"
    },
    {
      "key": "e_1_2_1_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/359460.359482"
    },
    {
      "key": "e_1_2_1_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02243478"
    },
    {
      "key": "e_1_2_1_11_2",
      "volume-title": "Montreal",
      "author": "Devroye L.",
      "year": "1980",
      "unstructured": "Devroye , L. \" The Computer Generation of Binomial Random Variables,'' Technical Report , McGill University , Montreal , Quebec , Canada , 1980 . Devroye, L. \"The Computer Generation of Binomial Random Variables,'' Technical Report, McGill University, Montreal, Quebec, Canada, 1980."
    },
    {
      "key": "e_1_2_1_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0898-1221(80)90039-5"
    },
    {
      "key": "e_1_2_1_14_2",
      "volume-title": "An Introduction to Probability Theory and Its Applications",
      "author": "Feller W.",
      "year": "1968",
      "unstructured": "Feller , W. An Introduction to Probability Theory and Its Applications , Volume 1 , Wiley , New York , 1968 . Feller, W. An Introduction to Probability Theory and Its Applications, Volume 1, Wiley, New York, 1968."
    },
    {
      "key": "e_1_2_1_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02276759"
    },
    {
      "key": "e_1_2_1_16_2",
      "volume-title": "Principles of Discrete Event Simulation",
      "author": "Fishman G.S.",
      "year": "1978",
      "unstructured": "Fishman , G.S. Principles of Discrete Event Simulation , Wiley , New York , 1978 . Fishman, G.S. Principles of Discrete Event Simulation, Wiley, New York, 1978."
    },
    {
      "key": "e_1_2_1_17_2",
      "first-page": "366",
      "article-title": "Sampling from the binomial distribution on a computer",
      "volume": "74",
      "author": "Fishman G.S",
      "year": "1979",
      "unstructured": "Fishman , G.S . Sampling from the binomial distribution on a computer , Journal of the American Statistical Association 74 , 366 , 1979 , 418-423. Fishman, G.S. Sampling from the binomial distribution on a computer, Journal of the American Statistical Association 74, 366, 1979, 418-423.",
      "journal-title": "Journal of the American Statistical Association"
    },
    {
      "key": "e_1_2_1_18_2",
      "doi-asserted-by": "crossref",
      "first-page": "3",
      "DOI": "10.1080/00031305.1984.10483208",
      "article-title": "Sampling from a discrete distribution while preserving monotonicity",
      "volume": "38",
      "author": "Fishman G.S.",
      "year": "1984",
      "unstructured": "Fishman , G.S. , and Moore , L.R . Sampling from a discrete distribution while preserving monotonicity , The American Statistician 38 , 3 1984 , 219-223. Fishman, G.S., and Moore, L.R. Sampling from a discrete distribution while preserving monotonicity, The American Statistician 38, 3 1984, 219-223.",
      "journal-title": "The American Statistician"
    },
    {
      "key": "e_1_2_1_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/01621459.1976.10480965"
    },
    {
      "key": "e_1_2_1_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/00031305.1979.10482697"
    },
    {
      "key": "e_1_2_1_22_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/01621459.1972.10481259"
    },
    {
      "key": "e_1_2_1_23_2",
      "first-page": "79",
      "volume-title": "Proceedings of the 1980 Winter Simulation Conference, IEEE",
      "author": "Schmeiser B.W.",
      "year": "1980",
      "unstructured": "Schmeiser , B.W. \" Random Variate Generation : A Survey.\" In Simulation with Discrete Models: A State-of-the-Art View, T.I. Oren, C.M. Shub, and P.F. Roth (eds.) . In Proceedings of the 1980 Winter Simulation Conference, IEEE , 1980 , 79 - 104 . Schmeiser, B.W. \"Random Variate Generation: A Survey.\" In Simulation with Discrete Models: A State-of-the-Art View, T.I. Oren, C.M. Shub, and P.F. Roth (eds.). In Proceedings of the 1980 Winter Simulation Conference, IEEE, 1980, 79-104."
    },
    {
      "key": "e_1_2_1_24_2",
      "first-page": "227",
      "volume-title": "Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE",
      "author": "Schmeiser B.W.",
      "year": "1981",
      "unstructured": "Schmeiser , B.W. \" Random Variate Generation .\" In Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE , 1981 , 227 - 242 . Schmeiser, B.W. \"Random Variate Generation.\" In Proceedings of the 1981 Winter Simulation Conference, T.I. Oren, C.M. Delfosse, C.S. Shub (eds.), IEEE, 1981, 227-242."
    },
    {
      "key": "e_1_2_1_25_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1287/opre.28.4.917"
    },
    {
      "key": "e_1_2_1_26_2",
      "volume-title": "Poisson Random Varlate Generation,\" Research Memorandum 81-4",
      "author": "Schmeiser B.W.",
      "year": "1981",
      "unstructured": "Schmeiser , B.W. , and Kachitvichyanukul , V . \" Poisson Random Varlate Generation,\" Research Memorandum 81-4 , Purdue University , 1981 . Schmeiser, B.W., and Kachitvichyanukul, V. \"Poisson Random Varlate Generation,\" Research Memorandum 81-4, Purdue University, 1981."
    },
    {
      "key": "e_1_2_1_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/318242.318445"
    },
    {
      "key": "e_1_2_1_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/355744.355749"
    }
  ],
  "container-title": "Communications of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/42372.42381",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/42372.42381",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T21:14:54Z",
    "timestamp": 1750281294000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/42372.42381"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  },
  "references-count": 26,
  "journal-issue": {
    "issue": "2",
    "published-print": {
      "date-parts": [
        [
          1988,
          2
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/42372.42381"
  ],
  "URL": "http://dx.doi.org/10.1145/42372.42381",
  "relation": {},
  "ISSN": [
    "0001-0782",
    "1557-7317"
  ],
  "subject": [],
  "container-title-short": "Commun. ACM",
  "published": {
    "date-parts": [
      [
        1988,
        2
      ]
    ]
  },
  "assertion": [
    {
      "value": "1988-02-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}