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.

January 22

probability substitution tables

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)[reply]

Here's an improvement: if there exist j,k such that 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

—Tamfang (talk) 19:50, 22 January 2017 (UTC)[reply]

Need help with OpenOffice!

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)[reply]

Hm, okay, googled again, this time with create "page size" template OpenOffice rather than just create "page template" OpenOffice, and it seems the solution is to set all the parameters (page dimensions, font, font size, and indent), with no text or anything whatsoever on the page yet, and then go File Templates --> Save. In the open window, add your new template's name and hit OK. That's how your new page template is created. To open it from now on, you go File --> New --> Templates and Documents, and there it is, ready for you to open, complete with all the parameters. The official documentation said nothing of the sort, they only told me to do F11 to open a way different template window where I can never be sure what I'm saving and where most stuff you can do looks like overwriting existing templates, as there's no way to select parameters or set a template name. And the most online tutorials in relation to OO templates were only about tables, paragraphs, and drawing borders on your page. --2003:71:4E6A:B422:D574:717B:EA24:352A (talk) 20:39, 22 January 2017 (UTC)[reply]

OpenOffice is based on LibreOffice. All this software are free to use. Why not updating Your copy? As I read Absatz which is German for Paragraph, do You need the German version?

https://de.libreoffice.org/ German
https://www.libreoffice.org/ English

Need help to download or find the right version? --Hans Haase (有问题吗) 21:30, 26 January 2017 (UTC)[reply]