4 ms·
Is there an explanation of why it sometimes gives the wrong answer?
by raldi 2y ago
Is there an explanation of why it sometimes gives the wrong answer?
- genter 2y ago> will only produce correct results with probability < 1, though very close to 1 That's terrifying
- _a_a_a_ 2y agoWhy? So long as you know the probabilities and they are tolerable, why?
- kardos 2y agoThe challenge is to get the right answer. It's much less interesting if you relax the challenge to no longer require the right answer. Here's a really fast approximate answer: 50000000*(2^31-1)/2
- nerdponx 2y agoThe fact that it's wrong sometimes is a lot less interesting than the probability distribution of wrongness, conditional on magnitude.
- sYnfo 2y agoMap vs. territory. The challenge, as defined by the system the competition runs on, is to get 3 correct responses in a row. That's it.
- Neywiny 2y agoSolid point and good example
- madars 2y agoIt's worse: Pr[correct output | hard input] = 0, even though they estimate that Pr[correct output | random input] ~ 1. This means that you can't, for example, amplify your success probability by repeating the algorithm a bunch of times and taking the majority vote.
- sYnfo 2y ago1) if you set BATCH_SIZE > 14 sums_acc may overflow 2) chunks with too many small numbers cannot be processed with just 2 shuffle-adds 3) (not mentioned in the post) HighLoad limits the size of the source code you can submit, so you can't put all possible values in the look-up table
- kardos 2y agoFor 1, can you raise that to 28 with unsigned accumulators?
- sYnfo 2y ago14 already assumes unsigned accumulator! 255 [accumulator capacity] / (2 [shuffle-adds] * 9 [highest digit value]) ~= 14
- dzaima 2y agoYou could have a separate accumulator for each shuffle, which should allow 28 iterations. (and merge those together at the end of the 28-iteration-loop by widening to u16; at which point you could have an outer loop accumulating in u16 until that runs out)
- camel-cdr 2y agoCouldn't you organize the accumulators in 8 byte chunks, and leave the upper byte unused. Then you map consecutive digits to those chunks and use 64 bit addition for the accumulation. Then overflow between the bytes would keep the correct result if you do the shuffles correctly, and you have a full byte of overflow buffer.
- Dwedit 2y agoGaps in the numbers are often enough to do some kind of "SIMD" even on ordinary 32-bit processors.
- 2y ago