Let's give this thread another try:
>was interviewing
>was asked to write a random integer generator between 0 and 6 given a random 0 1 generator
> never heard this question before
>can not figure it out by myself and had to ask for hints
>came up with an anwser that is acceptable after those hints are given finally but didn't have time to code
Am I a brainlet?
Other urls found in this thread:
github.com
twitter.com
yes
ok mr smarty pants how would you answer it?
sum = 0
for 0 to 5
sum += rand(0,1)
return sum
that's a nice start but can you come up with something that gives a uniform probability distribution?
this has uniform probability, glownigger
2^n cannot be uniformly divided by 7, therefore it is impossible with integers
no, the probability of your function returning 0 is 1/64, not 1/6
no, its weighted towards the middle
We already told you are a brainlet on the last thread.
>we are impressed that you noticed that, user, but we tasked you to write such a generator anyway.
what do now?
int gen_bit(void);
int gen_0_to_6(void)
{
while (1) {
int result = 0;
result += gen_bit()
Technically correct, but it feels ugly to me (runtime is unknown - and theoretically unbounded if the RNG is fucked). I wonder if there exists a constant-time version..
Well converting it to a real number line with intervals would not be practical as some intervals will always have a higher probability than others unless you have 2^n, n->∞ which would not work for obvious reasons.
I think the most practical solution would be to roll 3 times for 2^3=8 outputs, and have 1 output just be a reroll, and just terminating it if it fails 10 times or so, this is likely the most resource efficient solution.
(same as but just have the loop stop if RNG is fucked)
you can have a constant time version if you do rounding but that has a margin of error
yes, there is a answer with both a bounded runtime and a theoretical uniform distribution
result = (gen_bit()
for reasons similar to the ones in the problem we are discussing here, any bitwise generator for floats between 0 and 1 would not have the same density of outputs in [0, 1/6] as it would across all of [0, 1]
it isn't uniform-- generating a 0 is twice is likely as returning any other digit.
Probability of failing to generate a number n times in a row is 8^-n. RNG will unfuck itself eventually.
>it isn't uniform
yeah but fuck you
You tell them to go fuck themselves.
This is so fucking stupid.
unsigned i, val;
for (i = 0; i < 6; i++)
val += rand_0_1();
return val; // guaranteed to be between 0 and 6.
>I'm not going to answer your easy question because I think it's impossible
You're hired!
the result isn't uniformly random
how do you know that?
>interview promptly ends
presuming the RNG is truly random? yeah, perhaps. but who do you think is going to eat the blame if it isn't and product gets stuck in an endless loop in the subroutine you wrote?
this has a binomial distribution
They said it had to be uniform. They didn't say you had to have a constant number of calls to the generator.
x = (get_bit()
printf ("Pretend this is uniformly random I don't got time for your professor layton bullshit");
Draw a probability tree or run tests on it and you'll see
You are much more likely to get a 3,4 than you are a 0 or 6
Let's say you wanted to only generate a number between 0 and 2, so you generate 3 bits this way:
0 0 = 0 (25% chance)
0 1 = 1 (50% chance)
1 0 = 1
1 1 = 2 (25% chance)
Now scale that up.
They didn't say it had to be uniform either actually
>for reasons similar to the ones in the problem we are discussing here, any bitwise generator for floats between 0 and 1 would not have the same density of outputs in [0, 1/6] as it would across all of [0, 1]
yes you get the 2^n outputs, equally spread them over a real number line with 7 intervals. Again the problem is that they are not equally distributed unless you have an amount of outputs that tends to infinite. Which is why it can't work (what I said earlier).
The only remaining solution if you absolutely need a fixed runtime is to have an acceptable error margin and just have a 2^n with a large enough number of outputs to satisfy the error margin (7/(2^n) < error margin)
Will I really be turned down for a job if I don't correctly solve brain teaser bullshit like this?
this is an algorithm that actually has real world application, although probably not for most jobs
last thread had a correct solution dimwit
>answering trivia for a paycheck
nah it didn't. i'll post a hint at 75 posts, solution at 200
is this going to be like when you posted 'I GOT IT GUYS' in the last thread and it didn't work at all?
>yeah, perhaps. but who do you think is going to eat the blame if it isn't and product gets stuck in an endless loop in the subroutine you wrote?
The person who wrote the RNG. Next stupid question.
that's not really going to cut it when a container ship capsizes because it was stuck in an infinite subroutine you personally committed to the build. "the rng wasn't really random" is "the dog ate my homework" of software engineering.
multiply by 6 and round?
why does a container ship need a random number generator?
you can do the other solution here which has constant runtime but will be very slightly inaccurate
It really depends on your application
(define (rand-from-zero-one I)
(if (= i 0) 5 3))
It's usually random.
that's a fair point, for instance if some moron deleted the line that seeds the RNG then there's a good chance it would hang
however, you still haven't addressed the fact that there were two 'acceptable' types of answers in the original thread, and one did have a bound runtime.
>pull the faggot over the interviewing desk
>bash his bitch face against it
>number of teeth he loses is his answer
what do I win?
>if some moron deleted the line that seeds the RNG then there's a good chance it would hang
no it wouldn't, it would only hang if the RNG was literally broken and returned the same result over and over again
well, then tweak it so that it is accurate
you can't
as the post said, you need infinite precision for total accuracy
but the error of margin will be very small, so small that it doesn't matter for any application i can think of if you use a 32 or 64 bit value
2^n = size of float or whatever variable type you want to use.
1 / (size of var type) is your error margin.
this would have been the error margin anyways.
is this an acceptable solution now?
do you mean:
1) reroll if 7
2) modulo a big number by 7
the first one is not guaranteed to terminate and the second reveals its bias after sufficiently many uses.
neither answer is optimal.
In [1]: import random
In [2]: from functools import reduce
In [3]: rand_bit = lambda:random.randint(0,1)
In [4]: reduce(lambda x, y: x
and what bias is that? I'm not seeing it.
why don't you just post your code. Jow Forums didn't get smarter overnight
the bias is that a handful of numbers have a higher chance of occurring because any power of 2 is not divisible by 7
what? and you say 'after sufficiently many uses'
If I run it with thousands of trials, i get an uneven distribution obviously. the difference between each variable is under 1%, and if i run it again, I get a different looking distribution and so on
so what's sufficient according to you?
private static final int SAMPLES = 1000000;
public static void main(String[] args) {
ZeroOneGenerator zog = new ZeroOneGenerator();
ZeroSixGenerator zsg = new ZeroSixGenerator(zog);
Map histogram = new HashMap();
long time = System.nanoTime();
for (int i = 0; i < SAMPLES; i++) {
int result = zsg.next();
int hits = histogram.getOrDefault(result, 0);
histogram.put(result, hits + 1);
}
time = System.nanoTime() - time;
System.out.println(String.format("Completed in %.3f ms", time / 1000000f));
for (Entry histEntry : histogram.entrySet()) {
float percent = (histEntry.getValue() / (float) SAMPLES) * 100f;
System.out.println(String.format("%d: %d (%.2f%%)", histEntry.getKey(), histEntry.getValue(), percent));
}
}
Completed in 74.110 ms
0: 148282 (14.83%)
1: 148622 (14.86%)
2: 141282 (14.13%)
3: 140223 (14.02%)
4: 140914 (14.09%)
5: 140653 (14.07%)
6: 140024 (14.00%)
That's not uniform either. 0 and 6 have probability 1/16, 3 has 4/16
I ran it on a very large sample size to prove the point. also 64 bit integers. Now where exactly is the mystical bias you were talking about.
./a.out 0 7
0.142848 0.142842 0.142866 0.142853 0.142854 0.142870 0.142866
aight how bout this
7x7 grid
each collumn represents a number for [0,6]
generate a random number 7 times for each collumn
sum each collumn
collumn with highest sum is output
if multiple collumns have same highest sum then output is just the amount of the sum which can also only be [0,6]
actually small correction
number of rows should be 6 not 7
OP is a highschool student taking babbys first stats class, they don't know what they're talking about
I went ahead and did the same thing for mine:
In [5]: from collections import Counter
In [6]: c = Counter(rand_int() for _ in range(2**20))
In [7]: [c[i]/2**20 for i in range(7)]
Out[7]:
[0.14295387268066406,
0.14252758026123047,
0.14288043975830078,
0.14229202270507812,
0.1432666778564453,
0.14281749725341797,
0.14326190948486328]
yours is just as 'wrong' as everybody else's, it's just slower.
>collumn with highest sum is output
you mean the column number, not the sum, right?
>if multiple collumns have same highest sum then output is just the amount of the sum which can also only be [0,6]
if 5th and 6th column have highest sum, output is 11
>collumn number
yes
e.g. collumn 2 had highest sum of 5
output is 2
>5th and 6th collumn have highest sum
in that case the amount of the sum is output (not the collumn numbers)
e.g. 5th and 6th both had 4
then output is 4
oh i see, my bad
well the sum of 6 bits is still biased towards the middle
you've reduced the bias but not completely eliminated it
pretty creative solution though
Technically still possibly a random number generator. You're just getting really lucky.
0 to 1 generator is just a random bit
Unbiased with uniform distribution:
Roll 0-1 three times x0,x1,x2. Make n = x0 + 2*x1 + 4*x2.
If n > 6 reject and resample.
If n
Take in a sequence of 6 bits and add them together, do you mean generate 0-6 from a single bit?
you're the 20th user to post this
def get_random_number():
return 4
:^)
Too bad I didn't read through the thread and spoil the problem. Sorry to have inconvenienced you.
bump for autistic op's 'hint'
here you are
>make autistic thread two days in a row
>reject all solutions
>say that you have a better solution
>offer hint at x posts
>realize your solution is shit and doesn't actually work
>fuckfuckfuck
>time to post hint
>post random gif
>Am I a brainlet?
the answer is yes, OP
it isn't random, it's an example of a technique called "color cycling"
int value = 0;
while (!value)
value = (get_bit()
not uniform: generating 0 is twice as likely as generating each of 1,2,3,4,5,6
>it isn't random
random in this case meaning unrelated to the problem at hand
keep up, brainlet.
welcome to the thread #21
How come he gets to be #21 if he fucked up the solution?
lol ok man. can you point me to the post with your solution? i'm going to fix it for you in like 3 lines
it's the same core concept
>get three random bits
>if it's 7 do something to make it not 7
sure, why not fix #21's solution
even though i technically could, i won't because it was far too stupid.
Is this not obvious? Link it to a function pulling an integer from the system time as a seed. Then do some weird funsie shit with it like a square root or multiply it by a weird number and get the modulus of the resulting number to whatever number range you need.
>modulus
Nice non-uniform and biased distribution user
see: you're as obviously clueless as
this is right, doing a modulo of any power of 2 by anything other than a power of 2 will bias the return of your function towards the lower integers
yeah, it'll have an obvious bias just like these:
ok schizo, where's your hint? this is post 89
right here:
>generate 32 random bits and shift them into position to create a random 32 bit number
>% 7
There you go.
I'm not OP, that was sarcasm
is the correct answer
op says that's 'biased', he lost his medicine and he's posting cryptic gifs trying to hint at non-existent solutions. welcome to the thread.
meant to reply to
Generate a random 3 digit sequence of 0s and 1s and convert it to decimal. If it's all 1s(i.e., answer = 7), repeat the process.
...
Went down the rabbit hole, technically he is right. But there appears to be no solution that isn't either non-uniform or is guaranteed to finish in finite time.
github.com
Here's the implementation openBSD uses.
In what fucking world would you be limited to only 2 states in a random function?
>But there appears to be no solution that isn't either non-uniform
yeah, it's non-uniform in the same sense that hash tables can have collisions. So what.
why is everyone inclusive on 6 i though we were simulating a dice with a coin