00:09:10 -!- tromp has quit (Remote host closed the connection).
00:17:02 -!- TheLie has quit (Remote host closed the connection).
00:37:09 <esowiki> [[XENBLN]] M https://esolangs.org/w/index.php?diff=69961&oldid=69960 * PythonshellDebugwindow * (+1) /* Commands */
00:38:34 <esowiki> [[XENBLN]] M https://esolangs.org/w/index.php?diff=69962&oldid=69961 * PythonshellDebugwindow * (+37) /* Number non-literals */
00:44:16 -!- tromp has joined.
00:48:38 -!- tromp has quit (Ping timeout: 245 seconds).
01:09:14 -!- arseniiv has quit (Ping timeout: 240 seconds).
02:06:18 -!- tromp has joined.
02:11:19 -!- tromp has quit (Ping timeout: 272 seconds).
02:18:04 -!- FreeFull has quit.
02:21:55 -!- imode has joined.
02:25:24 -!- oerjan has joined.
03:54:33 -!- tromp has joined.
03:57:19 -!- tromp_ has joined.
03:59:37 -!- tromp has quit (Ping timeout: 272 seconds).
04:02:09 -!- tromp_ has quit (Ping timeout: 272 seconds).
04:05:14 -!- Lord_of_Life has quit (Ping timeout: 240 seconds).
04:06:42 -!- Lord_of_Life has joined.
04:36:21 -!- imode has quit (Ping timeout: 272 seconds).
05:16:20 -!- xkapastel has joined.
05:45:56 -!- tromp has joined.
05:50:42 -!- tromp has quit (Ping timeout: 260 seconds).
06:19:19 -!- xelxebar has quit (Remote host closed the connection).
06:19:38 -!- xelxebar has joined.
06:44:23 -!- sprocklem has quit (Ping timeout: 260 seconds).
06:46:11 -!- sprocklem has joined.
06:54:50 <esowiki> [[Feather]] M https://esolangs.org/w/index.php?diff=69963&oldid=53242 * IFcoltransG * (+12) Added dead link template to broken link
06:55:13 -!- Sgeo has quit (Read error: Connection reset by peer).
06:55:40 -!- Sgeo has joined.
07:11:48 <esowiki> [[Clue (oklopol)]] https://esolangs.org/w/index.php?diff=69964&oldid=69957 * IFcoltransG * (+172) /* Syntax */ Rewrote some sentences for clarity, fluency, and fixing of a spelling mistake
07:14:58 <esowiki> [[Clue (oklopol)]] https://esolangs.org/w/index.php?diff=69965&oldid=69964 * IFcoltransG * (+65) /* Syntax */ Added note on spaces in identifiers
07:33:48 -!- tromp has joined.
07:38:45 -!- tromp has quit (Ping timeout: 272 seconds).
07:54:10 <zzo38> Is it possible in PostScript to specify output page numbers using the "pdfmark" command?
07:55:51 <zzo38> (Also, do any PostScript interpreters that do not produce PDF support any subset of uses of pdfmark?)
07:56:05 -!- xkapastel has quit (Quit: Connection closed for inactivity).
08:02:34 <oerjan> ouch, it looks like clog/tunes has started deleting old logs
08:05:37 <shachaf> They are at http://tunes.org/~nef/logs/old/
08:08:53 <oerjan> oh. well i've already found the esolangs.org version.
08:09:36 -!- tromp has joined.
08:09:56 <oerjan> oh and they're zipped by year, i see, so even worse for linking
08:10:39 -!- iiee has joined.
08:12:18 <esowiki> [[Feather]] https://esolangs.org/w/index.php?diff=69966&oldid=69963 * Oerjan * (-32) Link to esolangs.org log instead
08:14:51 -!- TheLie has joined.
08:17:05 <zzo38> Also, I think I read somewhere that if you make DjVu output from PostScript then it tries to figure out automatically what to put into foreground/background. Is there a way to specify it by yourself? I don't really know if it make sense, as I don't know how the DjVu is working.
08:25:17 -!- xkapastel has joined.
08:34:44 -!- dog_star has quit (Ping timeout: 248 seconds).
08:34:56 -!- dog_star has joined.
08:36:20 -!- ^[ has quit (Ping timeout: 248 seconds).
08:38:32 -!- ^[ has joined.
08:52:34 -!- oerjan has quit (Quit: Nite).
10:12:30 -!- MDead has joined.
10:14:22 -!- MDude has quit (Ping timeout: 260 seconds).
10:14:26 -!- MDead has changed nick to MDude.
10:29:09 -!- cpressey has joined.
11:34:23 -!- TheLie has quit (Remote host closed the connection).
11:42:07 -!- arseniiv has joined.
11:51:02 -!- ddmm_ has quit (*.net *.split).
11:52:10 -!- ddmm_ has joined.
12:15:50 -!- wmww has quit (Ping timeout: 252 seconds).
12:17:04 -!- wmww has joined.
12:17:39 -!- iiee has left ("ERC (IRC client for Emacs 26.1)").
12:29:12 -!- tromp has quit (Read error: Connection reset by peer).
12:29:48 -!- tromp has joined.
12:40:48 -!- arseniiv has quit (Read error: Connection reset by peer).
12:41:52 -!- arseniiv has joined.
13:19:06 <esowiki> [[FAKE]] M https://esolangs.org/w/index.php?diff=69967&oldid=68815 * Argv0 * (+15) /* Commands */ conditional operator syntax change
13:21:29 <esowiki> [[FAKE]] M https://esolangs.org/w/index.php?diff=69968&oldid=69967 * Argv0 * (-12) /* Examples */ adaptation to conditional operator syntax change
14:56:05 -!- xkapastel has quit (Quit: Connection closed for inactivity).
15:49:59 -!- MDude has quit (Quit: Going offline, see ya! (www.adiirc.com)).
15:59:12 -!- imode has joined.
16:08:37 -!- Lord_of_Life_ has joined.
16:10:12 -!- Lord_of_Life has quit (Ping timeout: 260 seconds).
16:11:23 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
16:11:56 <esowiki> [[Special:Log/newusers]] create * Amakukha * New user account
17:16:20 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=69969&oldid=69900 * Amakukha * (+206) /* Introductions */
17:17:05 <esowiki> [[User:Amakukha]] N https://esolangs.org/w/index.php?oldid=69970 * Amakukha * (+62) Created page with "My favourite [[Brainfuck|Brainf**k]] dialect is [[Brainlove]]."
17:30:18 -!- tromp has quit (Remote host closed the connection).
17:30:50 <esowiki> [[Brainfuck]] https://esolangs.org/w/index.php?diff=69971&oldid=69560 * Amakukha * (+95)
17:32:06 <esowiki> [[Urban Mller]] https://esolangs.org/w/index.php?diff=69972&oldid=30824 * Amakukha * (+103) /* External resources */ +recent talk
17:33:30 <esowiki> [[Special:Log/newusers]] create * Pitust * New user account
17:36:16 <esowiki> [[Brainfuck]] https://esolangs.org/w/index.php?diff=69973&oldid=69971 * Amakukha * (+22) BF was inspired by FALSE according to the video
17:37:26 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=69974&oldid=69969 * Pitust * (+117) I need to complete the sign-up, right?
17:43:19 -!- tromp has joined.
17:44:24 -!- cpressey has quit (Quit: A la prochaine.).
17:48:19 -!- LKoen has joined.
18:20:03 -!- LKoen has quit (Remote host closed the connection).
18:21:00 <int-e> tromp: Ooph, I pushed my formalization effort through. https://int-e.eu/~bf3/tmp/Goodstein.html
18:23:54 -!- FreeFull has joined.
18:25:15 <int-e> tromp: The issue with these formalizations is that one has to make many intuitive steps more detailed. This is hard, and easily ends up in a mess. In this case the property that stood out to me was this: Consider the map that takes a number in hereditary base n and convertes it to heriditary base n+1. So for n=2, we map [0..8] to [0,1,3,4,9,10,12,13,27]. This map is monotonic. Obvious? Yeah,...
18:25:21 <int-e> ...kind of, but it's not immediately clear what the proof is.
18:34:02 -!- joes has joined.
18:35:12 -!- LKoen has joined.
18:53:07 <tromp> that looks like a major effort!
18:53:48 <tromp> does Isabelle have ascii alternatives for symbols like ⇩ ?
18:54:59 -!- imode has quit (Ping timeout: 258 seconds).
18:55:14 <int-e> tromp: It's actually a subscript (for the next character) in the editor. Could be replaced by _ for ASCII.
18:57:04 <int-e> tromp: If you look at the .thy file it's actually \<^sub> there... but nobody wants to type or read things like that, I believe.
19:00:44 <int-e> And yeah, it was quite some effort. I mean, you brought this up a week ago; I spent maybe a day wrapping my head around why things work, and realized that while I kind of trusted what I did, it was subtle enough to have gone wrong somewhere... so I foolishly started to formalize and it turned out to be a bit trickier than anticipated.
19:00:48 <tromp> link added to now capitalized Goodstein.hs in AIT repo
19:02:15 <int-e> I'm happy with the result though. Will probably clean up a bit more another day.
19:02:33 <int-e> Hmm, linking to my tmp directory isn't good :-/
19:03:18 <int-e> And I haven't decided yet where to put it permanently. But I'll find a public place.
19:06:08 <esowiki> [[Special:Log/newusers]] create * Asasnat * New user account
19:11:15 -!- joes has left ("Leaving").
19:13:42 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=69975&oldid=69974 * Asasnat * (+306)
19:13:47 <tromp> feel free to add it to AIT repo
19:14:19 <esowiki> [[User:Asasnat]] N https://esolangs.org/w/index.php?oldid=69976 * Asasnat * (+31) Created page with "hi im guy who likes programming"
19:14:24 <tromp> i also link to Goodstein.hs from Wikipedia article
19:14:26 <int-e> And oops, I got the mapping wrong... should be [0,1,3,4,27,28,30,31,81].
19:16:16 <b_jonas> int-e: are you fighting a dire hydra?
19:17:52 <int-e> b_jonas: Nah, I'm not in the mood for hydras, though that should fit into the same kind of ordinal number representation.
19:24:04 <int-e> b_jonas: Also the point here is that the Goodstein problem is reall subverted... we get termination for free (essentially) because it's all primitive recursion. (And the lambda calculus version is typeable in System F... again termination is free.) But proving that it actually implements the Goodstein iteration is where all the effort goes instead.
19:24:49 <b_jonas> ok. I don't actually know how Goodstein works.
19:27:00 -!- LKoen has quit (Remote host closed the connection).
19:28:56 -!- LKoen has joined.
19:31:52 <arseniiv> suppose you have a biased coin with probability of heads p. How do you find the most uniform distribution on a set {1, …, k} which can be realized by n flips of that coin (and assigning each outcome to 1, …, k)? I came to a greedy algorithm which ended up not optimal. Brute force search suffers from combinatorial explosion even for quite small n, k
19:32:48 <b_jonas> arseniiv: ooh, a box packing thing.... I don't know
19:34:25 <int-e> arseniiv: You should try this months' Ponder This problem, it has a similar (but more awkward) binpacking flavour.
19:34:51 <arseniiv> my algorithm was the following: sort coin flip outcomes from the most probable to the least probable and then assign each one in turn so that the current (incomplete) distribution has the largest entropy. Sadly, for (n, k, p) = (4, 2, 0.7) that gives a suboptimal answer
19:36:11 <arseniiv> int-e: ok I’ll chek that out. Though I’m not at all into packing, this one just popped from a discussion of making almost uniform distributions with a fair coin, which is far more trivial
19:36:18 <int-e> arseniiv: It's something that /should/ be NP-hard but will be awkward to actually prove NP-hard.
19:36:26 <int-e> (The biased coin problem.)
19:36:37 <b_jonas> int-e: why should it be NP-hard?
19:37:57 <arseniiv> I reckon if we have a completely arbitrary distribution instead of the binomial here, it could get tricky enough to be more obviously NP maybe
19:38:02 <int-e> Because bin-packing is NP-hard and I don't see how the additional structure that is there helps once you get close to the optimum.
19:39:36 <int-e> (Though obviously I may just lack imagination. My "awkward to prove" includes the possibility that it's actually false for some incredible reason.)
19:40:05 <arseniiv> ❝Your challenge this month is to design a game with 10 ladders and snakes altogether that will lead to an expected number of moves (rounded to the 6th decimal place) of 66.978705.❞ => omg
19:40:21 <int-e> arseniiv: If you have an arbitrary partition of 1 into positive rational numbers, and you try to split them as closely into two parts as possible, that *is* NP-hard.
19:40:56 <int-e> tow parts -> two equal parts
19:41:38 <b_jonas> int-e: but isn't it more like a lattice small vector search problem, with the O(sqrt(n)) types of boxes around n/p counting?
19:41:47 <int-e> (Deciding whether you can get equality is NP-complete, cf. https://en.wikipedia.org/wiki/Partition_problem)
19:42:46 <arseniiv> int-e: oh, that’s pretty close! I’ll tell this to the person which was interested in the packing. I bet 3, 5 etc. parts aren’t becoming not NP-hard suddenly too
19:43:55 <int-e> b_jonas: The downside is that the number of pieces you're working with is exponential in the input size.
19:44:31 <b_jonas> int-e: yes, but they're identical pieces, like in a small vector search problem, or like in that problem we considered some months ago about finding a number close to a target with only small divisors
19:44:39 <b_jonas> I should get back to that problem some day by the way
19:46:24 -!- imode has joined.
19:48:13 <int-e> Hrm, we should probably make the output size the parameter here, not the input size (because the input is compressed too much. The output is a partition into k parts, each of which can be described by n (that's the number of different probabilities) n-bit numbers.)
19:49:02 <b_jonas> yes, but only sqrt(n) of those numbers can count
19:49:46 <b_jonas> all the other types of boxes are small even if you take all the available ones together
19:50:07 <b_jonas> because of Cramer's theorem
19:50:30 <b_jonas> probably doesn't matter in whether it's NP-complete though
19:50:43 <int-e> But they're still important for the optimum.
19:51:03 <arseniiv> hopefully I infected you with not too hopeless a problem
19:51:23 <b_jonas> hmm, maybe they can be if the optimum is exponentially close to 1/k so you have to approximate it very closely
19:51:28 <int-e> arseniiv: Nah, I think it *is* hopeless.
19:51:48 <b_jonas> but not if you only want to get within 10**(-6) of 1/k
19:51:57 <int-e> b_jonas: Clearly the results about approximability do not carry over.
19:56:12 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
19:59:13 <int-e> arseniiv: This should approximate very well, but except for small n I would not have big hopes of finding the optimum. And I'm not really sure how small "small" is here.
20:00:49 <arseniiv> that one counterexample I found was pretty close to the optimum, yeah
20:00:56 <arseniiv> though maybe there are very bad ones
20:01:16 <arseniiv> I’d be interested what could be done to find them BTW :D
20:01:17 <int-e> Presumably you can randomize a little and avoid the terrible cases.
20:01:40 -!- Phantom_Hoover has joined.
20:01:42 <b_jonas> arseniiv: I think how you find good approximations for these is to type your program into an irc channel full of geeks and hope they'll spend their time to torture their computer to find a good approximation and tell you
20:02:16 <b_jonas> unless of course your inputs are too secret
20:04:24 <int-e> arseniiv: I guess you can also make a collection of micro-optimizations... different multisets of proabilities that have almost the same sum, that you can swap between the partitions to make small adjustments.
20:05:23 <int-e> arseniiv: At the very least this gives you something to burn CPU cycles with, in contrast to the greedy algorithm which will be over very quickly and never get a better answer.
20:06:10 <arseniiv> int-e: b_jonas: (and others interested) tangentially, how would you generate *truly* uniform variates (on that same finite set 1..k) having an infinite sequence of fair coin flips? I believed one simple algorithm using a binary tree is optimal until I calculated the entropy several years later. Now I was told another algorithm, quite a more efficient one as it seems, though I haven’t checked its optimality by myself. Could you reinvent it? (It should
20:06:10 <arseniiv> n’t be hard, I wonder why I hadn’t stumbled upon it myself)
20:06:14 <int-e> I also don't have the right theoretical background on this.
20:06:32 <b_jonas> arseniiv: that one is much easier
20:06:49 <int-e> arseniiv: Welcome to the wonderful world of entropy coding.
20:06:59 <b_jonas> arseniiv: if k is small, throw your coin k times, if it is head the rth time but tail all other k-1 times, then your result is r, otherwise retry
20:07:15 <b_jonas> you can do better than this, arithmetic coding is probably optimal
20:07:36 <int-e> arseniiv: You can get as close as you want to log_2(k) coin flips per choice, but at the expense of keeping increasingly bigger entropy buffers.
20:08:59 <arseniiv> b_jonas: no, I have no practical need to solve instances of this problem, though it’s a bit interesting as we can see here :)
20:09:15 <b_jonas> arseniiv: or in practice, flip the coin enough times to get more than 256 bytes of entropy (how many times that is depends on p), feed that to initialize a cryptographic pseudonumber generator, and use the outputs of that for all the randomness you want to generate
20:09:16 <arseniiv> (that was an answer to the older post)
20:09:41 <arseniiv> <b_jonas> arseniiv: that one is much easier => yeah I know! :)
20:09:43 -!- MDude has joined.
20:09:49 <b_jonas> you can get an arbitrarily long random output, nobody will notice that the seed is only 256 bits long
20:10:09 <b_jonas> you can use 512 bits if you're particularly paranoid
20:10:30 <b_jonas> yeah, probably better use 512 bits
20:11:23 <arseniiv> <int-e> arseniiv: You can get as close as you want to log_2(k) coin flips per choice, but at the expense of keeping increasingly bigger entropy buffers. => yeah that’s what that newer algorithm needs, but it has a neat and very concise description which is yet to be spoiled here
20:11:52 <int-e> I'd use some kind of range coder.
20:12:27 <b_jonas> so if you know that your coin's probability is between 1/4 and 3/4, then the entropy of one flip is at least 0.81 bits, so flip 632 times and use that as your seed
20:13:34 <b_jonas> if you need only a few random outputs and you want fewer coin flips, then use arithmetic coding to approximate a real number with smaller and smaller intervals after each coin flip, and generate your randomness from that real number when the output is certain
20:14:26 <b_jonas> there's probably also a way to use arithmetic coding if you don't know the exact value of p, but it might be ugly
20:14:48 <b_jonas> at least I don't know a way how you'd do that optimally, but I could probably do it optimally by constant factor of flips
20:15:44 <b_jonas> the easiest way to do that is do pairs of coin flips, and rethrow for HH and TT
20:15:55 <b_jonas> and then use the HT and TH results as your fair flip input
20:16:01 <arseniiv> the description they gave me was this (for the fair coin): use the coin to divide a line segment into halves etc., and when the small subsegment is completely inside of one of k equal parts of the original segment, you have one value; then you divide that part into k parts and continue further. So I definitely see the need for unbounded entropy storage but the description is quite neat in itself
20:16:27 <b_jonas> arseniiv: yes, that's how arithmetic coding works
20:16:32 <arseniiv> <b_jonas> if you need only a few random outputs and you want fewer coin flips, then use arithmetic coding to approximate a real number with smaller and smaller intervals after each coin flip, and generate your randomness from that real number when the output is certain => ah you wrote it all already
20:17:01 <arseniiv> so now I see how that person gave an answer almost immediately: they probably knew arithmetic coding too
20:17:53 <arseniiv> <b_jonas> and then use the HT and TH results as your fair flip input => definitely cool thing
20:18:11 <b_jonas> arseniiv: https://www.perlmonks.com/?node_id=877696 has an example code for arithmetic coding with big integers; practical algorithms for compression are trickier because they want to stream the output without having to keep all the input or all the output in memory
20:18:56 <int-e> arseniiv: this is a sketch: http://paste.debian.net/1131148/
20:19:21 <b_jonas> it's an example of steganographic typography: I use a known pre-existing text verbatim, and hide information in its presentation
20:19:30 <int-e> arseniiv: (It's not code because I (deliberately) didn't include the policy for balancing refills and making choices.)
20:20:00 <b_jonas> sadly it's not very impressive because I managed to hide very little information
20:20:29 <arseniiv> and the suboptimal algorithm was to have a set of nodes, just one node at the start, and double them for each coin flip, giving an answer if there are enough nodes, and continuing with the remainder of nodes otherwise. That gives quite a heavy entropy loss for some k but it runs in constant space
20:21:18 <arseniiv> (when optimizing, that relates to a binary digits of 1/k)
20:22:51 <int-e> arseniiv: I made this a sketch because I wanted to make the following point: This procedure does not waste any entropy, except in the FAIL case in make_choice. So in the long run, you need to minimize the probabilitiy of that case... which means you want to make the range large. The downside of having a large range is startup cost, and, if you overdo it, expensive computations. But in practice,...
20:22:57 <int-e> ...keeping r around 2^32 * max(k) is probably good enough.
20:23:58 <arseniiv> I just can’t absorb too much at once :D
20:25:34 <arseniiv> wait, is it bounded-space after all?
20:25:49 <int-e> Well, that's up to the user...
20:26:01 <int-e> if you just keep adding flips you'll run out of space.
20:26:33 <int-e> (imagine an arbitrary precision type for "int")
20:27:11 <arseniiv> ah so it’s unbounded if we don’t want to lose entropy but if we can afford it I see, that can be simplified to the tree algotihm even
20:28:05 <arseniiv> but that one isn’t good because we can’t tweak it, and a normal arithmetic coding is tweakable
20:28:19 <arseniiv> (that one = tree one I described)
20:28:19 <int-e> what do you want to tweak?
20:28:57 <arseniiv> and your sketch shows how we can keep the buffer the length we want
20:29:27 <int-e> You can get arbitrary (rational) distributions with a fairly minor tweak...
20:30:23 <int-e> The add_flip can be generalized to adding an arbitrary uniform choice (multiply by number of choices c instead of 2; add value [0..<c])
20:31:07 <arseniiv> <int-e> what do you want to tweak? => the amount of entropy we discard/keep. I just hadn’t thought about that at all before I wrote here, as I wasn’t aware in full that we need to have unbounded space to not lose entropy
20:31:56 <int-e> And then you can sample a distribution described by frequencies [a1,a2,...,an] in three steps: 1) sample uniformly from a1+a2+...+an choices. 2) find corresponding ak and offset into ak chunk (in range [0..<ak]). 3) add back a uniform choice of size ak with the offset as value to the pool.
20:33:11 <int-e> Also, range coders are a kind of arithmetic coders anyway; the differences aren't so big.
20:36:33 <int-e> For this particular application (fair die rolls) I like the clean invariant (v uniformly random in [0..<r]), where with arithmetic coders one often has to worry about rounding or switch to rational numbers.
20:37:02 <int-e> But for the more common practial application (namely, compression) that hardly matters.
21:08:19 -!- dingwat has quit (Quit: Connection closed for inactivity).
21:32:55 -!- imode has quit (Ping timeout: 260 seconds).
23:09:55 -!- tromp has quit (Remote host closed the connection).
23:29:02 -!- Phantom_Hoover has quit (Ping timeout: 268 seconds).
23:31:04 -!- sprocklem has quit (Read error: Connection reset by peer).
23:32:18 -!- sprocklem has joined.
23:38:50 <zzo38> What I think should be a document storage format, is storing compressed rasters, with the ability to efficiently encode with multiple resolutions and/or colour spaces, and supports encoding the represented text (for use of search and copying), and a subset of pdfmark features, but not all of them. (DjVu is almost like this, I think.)
23:40:13 -!- tromp has joined.
23:45:04 <zzo38> The subset of pdfmark features I think should be wanted are: /PAGELABEL, /ANN (only for links to pages in the same document; the only optional keys allowed are /Page and /View, and the only valid view type is /XYZ, and the zoom level isn't used), /OUT (with the same restrictions as for /ANN, except /Count is also allowed).
23:45:13 -!- tromp has quit (Ping timeout: 272 seconds).
23:48:23 -!- arseniiv has quit (Ping timeout: 272 seconds).
23:49:43 <zzo38> I think it would be the simpler way to make it
23:51:42 -!- imode has joined.