Maybe I'm not well versed enough in math for this, but I don't see what prime-ness has to do with this.

Doesn't writing rand4 based on rand9 suffer the same non-terminal fate? Over infinite trials, the probability of generating a number that doesn't need to be thrown out (< 9 in this case) approaches 1 but never reaches it right?

e.g 8/9 * 8/9 * 8/9 ...

Its not specifically that they're prime, its that there's no way to get 5^n = 7^m the same way you can't get 4^n = 9^m. Whatever the precise way of stating that is. Has to do with prime factorizations. If I get any more specific I'll probably misstate something, but you know if there's a number in the prime factorization of the first value that doesn't appear in the prime factorization of the second, there's no way to make it work.

And here's a test case: Generate 1..12 from 1..18. Even though both prime factorizations are 2*2*3 versus 2*3*3, so it's all just 2's and 3's, you still can't get 12^n = 18^m because the ratios of 2's to 3's in the prime factorizations will always be different. I think it only works (guaranteed termination) if the larger number is evenly divisible by the smaller.

Ah... cool, thanks!

Yeah disregard that second paragraph, please, I'm completely wrong. Getting 1..12 from 1..18 with guaranteed termination is not difficult. Bolded part is correct.

I agree that it is initially offensive to the senses, especially from an academic/theory perspective. I It looks like it ends up being about as efficient as you can get without using some storage or something, but I didn't know that at the time and I wouldn't have been surprised to find some elegant mathy solution.

From a practical perspective, though, I wouldn't hesitate. The average running time is O(n) and it's easy to understand what's going on. Ship it!

Agreed.

Do tell...

Ha, it might be kind of a fun puzzle so I'll put it in a spoiler. And I'm just going for guaranteed termination, nevermind efficiency.

that's why i said co-prime. i think that's all you need.

Thank you for this explanation. It seems that all numbers in the prime factorization of the smaller number must be present in the prime factorization of the larger number, but doesn't that then simplify down to "For the problem write randX using randY to have a terminal solution, X must be a factor of Y?"

the example that lead me to that conclusion: rand4 from rand14 seems to be impossible despite all the prime factors of 4 being present in the prime factors of 14

Edit: Guaranteed terminating version of rand4 from rand14

Class im supposed to design, the login screen

SPRITES! Jesus christ

See my comments in the spoil tags, it seems like now you bias to 1-3 and 10-12 and don't have equal probability for all numbers 1-12

Holy ****. Sprites instead of asterisks. And then blinking sprites!? What is this, geocities?

My group leader is a moron

Sorry meant implement not design, i obviously have no control over this future flaming pile of garbage

Aren't you glad now that like 85% of your grade or whatever is based on having voluminous documentation that your professor will never read?

No... He must have sensed my sour attitude, as soon as I came back from dinner break i got demoted to just producing documentation. Me and some other poor **** are responsible for all the state flow diagrams and ****.

So not only do i have no control over this project whatsoever ive been delegated to reading and interpreting everyone's ****ty code. Lol this might be the worst class ever.

When are you supposed to have your piece ready?

Edit: I posted while you were announcing your demotion. I think your demotion might be preferable to actually implementing the code but not sure.

Teacher gave an example program's documentation, it has all the features that I suggested that he dismissed as too difficult.

Yea it's difficult using your ****ty ass platform, ******

Not exactly. 6 and 4 are not co-prime but you can't get rand(6) out of rand(4) without the unbounded edge case. I think the following works: to get rand(n) out of rand(m) with a finite time guarantee, the set of prime factors of n has to be a subset of the set of prime factors of m.

Edit: apparently my pony's slow and this has already been pointed out lol.

If you haven't watched these, you might find them helpful. Misko Hevery, the guy now known as the creator of AngularJS, was once beter known as an automated testing guru internally at Google and did a series of talks on how to write testable code, mainly aimed at Java developers but generally applicable regardless:

https://www.youtube.com/watch?v=wEhu57pih5w

https://www.youtube.com/watch?v=RlfLCWKxHJ0

https://www.youtube.com/watch?v=-FRm3VPhseI

https://www.youtube.com/watch?v=4F72VULWFvc

If nothing else, they should give you an idea of how hard it must be to get a strong automated testing initiative off the ground without a strong buy-in from everyone. Automated testing is something everyone talks about but something that I've rarely seen done properly. Getting everything set up mechanically so that tests can be written and run automatically is hard enough, but structuring everything so that different components are easy to isolate and test is harder and convincing everyone to do that properly is even harder. I find that even a lot of people who think they have it under control are often just going through the motion and writing tests to just to write tests, over-mocking habitually and testing implementation details as opposed to behavior.

that sounds right, ty.

This seems right except the part about it already having been pointed out. Where was that? This is how I tried to explain it to myself.

Ok so we have rand(m) and we want to generate rand(n) using k or fewer calls to rand(m) for some finite k. k calls to rand(m) will produce a sequence of return values and there are m^k such sequences, each equally probable. To get rand(n) as a uniform distribution we must partition those sequences into n equal sized groups, so m^k must be evenly divisible by n. Which is true if and only if the set of prime factors of n is a subset of the set of prime factors of m (as you stated).

The "or fewer" in "k or fewer calls" doesn't really matter. If some subsequences return early, we can consider that as mapping all possible full sequences that started with the subsequence to whatever value is returned.