While the preceding chapters are devoted mostly to one type of automata, the transducers, in the current chapter, we focus on another type of automata, the generators. We are mostly interested in pseudorandom number generators, the PRNG, as the latter generators can be used to produce pseudorandom sequences that “look like” random ones. As a rule, uniform distribution is the weakest statistical property the sequence must necessarily satisfy to be considered as a pseudorandom in any reasonable meaning as frequencies of occurrences of terms in a truly random sequence are (approximately) equal. That is why in the current chapter, we are focused on algorithms which produce uniformly distributed sequences out of a given short random string and which are the most suitable for implementation as programs (mostly, as straight line programs, SLP) for contemporary digital computers.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Applications to Computer Science

  • Vladimir Anashin

摘要

While the preceding chapters are devoted mostly to one type of automata, the transducers, in the current chapter, we focus on another type of automata, the generators. We are mostly interested in pseudorandom number generators, the PRNG, as the latter generators can be used to produce pseudorandom sequences that “look like” random ones. As a rule, uniform distribution is the weakest statistical property the sequence must necessarily satisfy to be considered as a pseudorandom in any reasonable meaning as frequencies of occurrences of terms in a truly random sequence are (approximately) equal. That is why in the current chapter, we are focused on algorithms which produce uniformly distributed sequences out of a given short random string and which are the most suitable for implementation as programs (mostly, as straight line programs, SLP) for contemporary digital computers.