The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [random-number-generator]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
204 views

Sampling a uniform distribution of fixed size strings containing no forbidden substrings

Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word? For short output strings ...
29 views

Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
47 views

Predicting the next number output by a random number generator

Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence? For example, ...
146 views

Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?

For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array, $32\cdot 624 = 19968$. How come the exponent is 19937 instead?
31 views

Are real computers capable of producing true random series with a program of finite length?

Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that ...
8k views

Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
31 views

arithmetic coding for generating random number with desired distribution

Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
41 views

How to generate a random number in a given range with uniform probability [closed]

I have used programming languages which generate a random number in a given range. Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
321 views

Unbiased random number generator

we have a six-sided dice numbered from 1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number from 1 to 10 using the given dice. I ...
77 views

Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
38 views

How to generate evenly distributed random numbers from the tics of a Geiger Counter?

How can I generate random numbers from the tics of a Geiger Counter? Say I have a file with the timestamps for every event. 0 325 456 920 .... The time spans ...
59 views

Why are random numbers important to the study and application of computer science?

Why are random numbers important to the study and application of computer science? I am new to computer science. So I am studying random numbers right now.
131 views

Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p

So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve... Given a random number generator that returns 0 or 1 with a 50% chance of either, ...
124 views

which arrangement gets favoured in naive shuffling for a given numbers from 1 to n according to the algorithm given?

algorithm: a=[1,2,3.....n] for i in (1,n+1): j=rand(1,n+1): swap(a[i],a[j]) let us say that n=3: 132 213 231 these 3 are 5 times possible and 123 312 321 are 4 times possible.... similarly ...
23 views

Testing two distributions, both accept null hypothesis

I have a sample that is collected to verify the accuracy of a new random number generator. Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and ...
9k views

Is von Neumann's randomness in sin quote no longer applicable?

Some chap said the following: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. That's always taken to mean that you can't generate ...
60 views

Would using mouse position in the below scenario generate true random numbers?

I'm having trouble wrapping my head around random number generation so I figure it would be better to ask now, rather than screw up later. Let's say I want to write a function that generates a random ...
76 views

RNG: removing bias by counting bits

I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias: two counters are used, ...
106 views

Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)

I'm looking for a reference to an algorithm that does the following. Given n, and a range [min, max], generate a random ...
84 views

Comparing the Speed of Random Number Generation to Reading Data

Imagine you need $n$ random numbers from a Gaussian distribution with $\mu=0$ and $\sigma=1$. And you need to use each of these $n$ numbers $k$ times in various operations. Let's identify the numbers ...
279 views

Pseudo random, unqiue integer numbers in a given range

I need an algorithm that gives me integer numbers with the following features: Numbers must be in a given range $[n..m]$; Numbers must be returned in pseudo-random order (random at visual inspection ...
35 views

TRNG by hamming distance of processor tics

I hardly remember on a lecture, where it was told, that the distance of the practical actual running-speed of a processor to the previous tic is used, to generated a true random entropy for seeding. ...
346 views

What's the possibility of random guessing a youtube's video ID [closed]

Let's say i make a program that produces an eleven character long ID like youtube does and tries to find a valid video in youtube. What's the actual possibility that it's going to produce a valid ID ...
54 views

How many bits needed to describe completely random function?

I read this sentence on mit.ocw and don't understand why this completely random function would need $|U|\log n$ bits to be described? Unfortunately, if we choose a hash function h that happens to ...
218 views

What makes a pseudorandom generator, a high quality one?

Reading this answer to this SO question: Why do we not combine random number generators?, it talks about very high-quality PRNG (Pseudo Random Number Generator) so it makes me wonder what ...
2k views

Generating values from a probability density function

If I have a probability density function, some f(x) which is >= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF? I know there is the box-muller transform ...
43 views

How to find a good saw function for PRNG?

As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with ...
80 views

Creating Random Number Generator with range

I've been trying to create my own random number library(in java). I've searched for randomization and Blum Blum Shub algorithm looks good. It needs a start value, it is not actually random. So i get ...
62 views

Fitting a feedback loop to data points

If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation. However, thinking in more ...
140 views

Generating Pairs of Random Numbers

Please consider the following probability density function of two variables. \begin{eqnarray*} f(x_1,x_2) &=& \begin{cases} 2(x_1+x_2) & \text{for} \,\, 0 \le x_1 \le x_2 \le 1\\ 0 ...
92 views

Remapping values to bias a uniform set towards a certain curvature [duplicate]

I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices. I came up with this: ...
8k views

Why do we not combine random number generators?

There are many applications where a pseudo random number generator is used. So people implement one that they think is great only to find later that it's flawed. Something like this happened with ...
583 views

Generate integer from 0 to 1 with equal probability

I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4. I am wondering if I can approach this way: ...
56 views

One-shot Private Randomness Extractor

Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for ...
98 views

One way recurrence O(N)->O(1)

Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence). I'm trying to find a system where it's fast to find many steps in the future ...
144 views

Uniform random number generation from random bits

I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me ...
574 views

Non-Uniform Random Number Generation, from Uniform Random Number Generater [closed]

The project I am currently working on (in C#) requires generating random integer between 0 and Int64.MaxValue. I have access to a Uniform RNG, which for pseudo-code purposes in the question, I will ...
3k views

Period of a pseudo-random sequence generated using an LFSR

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated ...
81 views

Creating a LCG with m = 32767

I want to create a PRNG for an integer only (with a max of 32767) system and tried to use an LCG. So I've chosen as $m = 32767$ and $c = 3$ and I tried to figure out a good $a$. However for the full ...
36 views

Approximate probabilities of passing a NIST statistical test

I am working with random number generation and testing, so I'm using NIST statistical tests to examine my random numbers. Now I want to compare my solution with other RNGs, but i can't find any ...
64 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
122 views

How to detect repeating random numbers?

What is the best way to detect repeating sequences of random numbers? For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of ...
619 views

Lazily computing a random permutation of the positive integers

Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)? What I ...
3k views

Simulate a fair die with a biased die

Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a ...
476 views

Recurrence relations that do not have a closed form solution

A recurrence relation computes value $d_n$ with the $\{d_{i},d_{j}\ldots\}$ previous digits of the sequence So for example, the Fibonacci sequence is defined as follows:  F_n = F_{n-1}+F_{n-2},\ \ \...
2k views

What's the problem of using the clock to generate random numbers?

If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number? What is wrong with this form of generating random numbers? I am aware that ...
2k views

Random sampling in a polygon

I would like to sample a uniformly random point in a polygon... If sample a large number they'd be equally likely to fall into two regions if they have the same area. This would be quite simple if ...
899 views

Generate random numbers from an interval with holes

Given a set $S$ of $k$ numbers in $[0, N)$. The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$. Edit - Also given an API to generate random numbers between \$[...