Computing desk | ||
---|---|---|
< January 21 | << Dec | January | Feb >> | January 23 > |
Welcome to the Wikipedia Computing Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
The Art of Computer Programming §3.4.1.A (vol.2 pp 120-121 in the third edition) shows a clever way to generate a random number from an arbitrary discrete distribution, with one call to the random number generator. If the number of possible results has n bits, you take the top n bits of the RNG's output as a tentative answer, and compare the lower bits to a table entry to decide whether to return that result or a different one. I amused myself by generating a table for the three highest of four dice with a 16bit RNG. (For simplicity of exposition, these dice are marked 0–5 rather than 1–6.)
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
criterion | 4045 | 3894 | 3590 | 3034 | 2174 | 961 | 203 | 100 | 0 | 50 | 405 | 0 | 505 | 708 | 1365 | 3035 |
substitute | 10 | 9 | 11 | 12 | 7 | 10 | 8 | 8 | (8) | 8 | 11 | (11) | 9 | 6 | 13 | 8 |
y = random16bits() x = (y>>12) & 0xf if y & 0xfff ≥ criterion[x]: return x else: return substitute[x]
The probability of returning 10 is (4045+961+(4096-405)) in 2^16. I hope that's tolerably clear. (Knuth's version, arguably more natural to the eye, has < rather than ≥, with the values of criterion
accordingly inverted; my way, the generation of the table is more natural.)
My question is about generating the table.
Initially criterion[j]
is 2^12 minus 2^16 times the desired probability; for unlikely results this is positive, for the most likely results it is negative.
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
initial criterion | 4045 | 3894 | 3590 | 3034 | 2174 | 961 | -505 | -2074 | -3388 | -4349 | -4601 | -3995 | -2529 | -657 | 1365 | 3035 |
I used a greedy algorithm: let j be the index of the highest number in criterion
and k that of the lowest; set substitute[j]=k
and criterion[k] += criterion[j]
; repeat, excluding j from further consideration.
For speed, we want to minimize the likelihood of looking at substitute
; thus, minimize the sum of criterion
. The greedy algo works pretty well, but I suspect it can be bettered. Ideas? —Tamfang (talk) 08:33, 22 January 2017 (UTC)
criterion[k] < 0 ≤ criterion[j]+criterion[k]
, choose the pair with the smallest nonnegative sum. This reduces sum(criterion)
by 759 in the example:x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
criterion | 4045 | 3894 | 3590 | 3034 | 2174 | 961 | 0 | 100 | 202 | 51 | 0 | 50 | 505 | 304 | 1365 | 3035 |
substitute | 11 | 10 | 8 | 12 | 7 | 13 | (6) | 10 | 10 | 10 | (10) | 10 | 6 | 10 | 9 | 9 |
Okay, I think what I'm trying to do is to create a template in OpenOffice 3.0 (Writer). Or maybe what I'm trying to do is called a master page. Or a vastly other outlandish name. See, the official documentation and googling has me so confused already that I don't even know what this thing I want is called. When I'm looking at the official documentation and what it says about templates, it mainly looks like an invitation to overwrite existing templates from the word go. And when I'm googling for how-tos on OpenOffice templates on the web, they seem to be occupied with way other things than what I wanna do, as they're mainly about tables, paragraphs, and square borders on a page.
Okay, so what I've done is set my page to a specific size in width and heigth, to achieve dimensions that were nowhere in the available page templates. Here's my main goal: How do I save this new page size (into a template?) so it will be available via Format --> Page..., and then under the header Page, to be one template option next to A4, Legal, Letter and other such templates? Of secondary interest would be stuff like default font and default font size for this page template, and maybe also default paragraph/indent/tab (Absatz, where I can define that every paragraph's first line is indented by 0.30cm). --2003:71:4E6A:B447:D574:717B:EA24:352A (talk) 19:12, 22 January 2017 (UTC)