Challenge: Multithreaded KFY/Durstenfeld Shuffle?
I think he's right, though. You forgot a power of two, earlier.
32! is how many permutations can 32 elements generate. What you want is 2^32!, which is... large.It requires 32! bits, or this many TiB: 29,914,512,758,033,826,022,167.205810547.
EDIT: My bad. It's much larger.
32! is how many permutations can 32 elements generate. What you want is 2^32!, which is... large.
EDIT: My bad. It's much larger.
Last edited on
hahaha - you're right - 32! is only for nItemsInSpace==32
we want nItemsInSpace==232
so we want a random number from 1 to (232)! - that's a big-ass number
how many bits do we need?
we want nItemsInSpace==232
so we want a random number from 1 to (232)! - that's a big-ass number
how many bits do we need?
Last edited on
| What you want is 2^32!, which is... large |
A fun (easy) question: which is larger: (2^32)! or 2^(32!)?
Well, since the number will be random anyway, you can avoid generating it by just moving the elements to random positions! Problem solved!
Now, if we could just find some way to directly generate the sequence...
I know! Let's treat it as a permutation and generate an index for it!
Now, if we could just find some way to directly generate the sequence...
I know! Let's treat it as a permutation and generate an index for it!
Hmm... Well, log2(2^(32!))= 32! ~= 2.63E+35, and log2(2^32!) = log2(2^32)+log2(2^32-1)+... which I think looks a bit like the integral of log2(x) between 1 and 2^32, which is approximately 1.31E+11, so I guess 2^(32!) is bigger.
EDIT: On second thought, I don't think the above is right.
Last edited on
log2(2^32!) = log2(2^32)+log2(2^32-1)+... is a lot less than 32*2^32
Now , if you compare 32! with 32*2^32 (or 31! with 2^32) it is clear which is bigger (If it isn't, you can do log2 again). 2^32 is between 12! and 13!
Now , if you compare 32! with 32*2^32 (or 31! with 2^32) it is clear which is bigger (If it isn't, you can do log2 again). 2^32 is between 12! and 13!
Last edited on
Ahaha now let's step up the problem: explain what you just wrote so that an eight grader can understand it :)
Anyways, I totally agree with you both :)
[Edit:] This actually is incorrect problem: as it clearly depends on the eight grader, I must give you pointer to one.
Anyways, I totally agree with you both :)
[Edit:] This actually is incorrect problem: as it clearly depends on the eight grader, I must give you pointer to one.
Last edited on
| explain what you just wrote so that an eight grader can understand it :) |
log2(232!) = log2(232) + log2(232-1) + ... + log2(1).
This is a sum of 232 values. Each of them if less or equal to 32. Thus 32*232 is definitely more than this sum.
This is a sum of 232 values. Each of them if less or equal to 32. Thus 32*232 is definitely more than this sum.
Topic archived. No new replies allowed.