< 1582070950 450276 :tromp!~tromp@2a02:a210:ca3:2800:c8e4:42df:9970:7194 QUIT :Remote host closed the connection
< 1582071422 821791 :TheLie!~TheLie@ip5b428f85.dynamic.kabel-deutschland.de QUIT :Remote host closed the connection
> 1582072629 885893 PRIVMSG #esoteric :14[[07XENBLN14]]4 M10 02https://esolangs.org/w/index.php?diff=69961&oldid=69960 5* 03PythonshellDebugwindow 5* (+1) 10/* Commands */
> 1582072714 802075 PRIVMSG #esoteric :14[[07XENBLN14]]4 M10 02https://esolangs.org/w/index.php?diff=69962&oldid=69961 5* 03PythonshellDebugwindow 5* (+37) 10/* Number non-literals */
< 1582073056 415262 :tromp!~tromp@2a02:a210:ca3:2800:c8e4:42df:9970:7194 JOIN :#esoteric
< 1582073318 311980 :tromp!~tromp@2a02:a210:ca3:2800:c8e4:42df:9970:7194 QUIT :Ping timeout: 245 seconds
< 1582074554 855027 :arseniiv!~arseniiv@136.169.210.57 QUIT :Ping timeout: 240 seconds
< 1582077978 137702 :tromp!~tromp@2a02:a210:ca3:2800:414a:46bb:4e62:ab93 JOIN :#esoteric
< 1582078279 150432 :tromp!~tromp@2a02:a210:ca3:2800:414a:46bb:4e62:ab93 QUIT :Ping timeout: 272 seconds
< 1582078684 127489 :FreeFull!~freefull@defocus/sausage-lover QUIT :
< 1582078915 102588 :imode!~linear@unaffiliated/imode JOIN :#esoteric
< 1582079124 941236 :oerjan!oerjan@sprocket.nvg.ntnu.no JOIN :#esoteric
< 1582084473 126030 :tromp!~tromp@2a02:a210:ca3:2800:414a:46bb:4e62:ab93 JOIN :#esoteric
< 1582084639 107917 :tromp_!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582084777 120891 :tromp!~tromp@2a02:a210:ca3:2800:414a:46bb:4e62:ab93 QUIT :Ping timeout: 272 seconds
< 1582084929 133506 :tromp_!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 QUIT :Ping timeout: 272 seconds
< 1582085114 931414 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 240 seconds
< 1582085202 306468 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric
< 1582086981 177130 :imode!~linear@unaffiliated/imode QUIT :Ping timeout: 272 seconds
< 1582089380 137984 :xkapastel!uid17782@gateway/web/irccloud.com/x-szvjnugtiouczbiu JOIN :#esoteric
< 1582091156 149381 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582091442 170370 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 QUIT :Ping timeout: 260 seconds
< 1582093159 813863 :xelxebar!~xelxebar@gateway/tor-sasl/xelxebar QUIT :Remote host closed the connection
< 1582093178 705785 :xelxebar!~xelxebar@gateway/tor-sasl/xelxebar JOIN :#esoteric
< 1582094663 283158 :sprocklem!~sprocklem@unaffiliated/sprocklem QUIT :Ping timeout: 260 seconds
< 1582094771 724963 :sprocklem!~sprocklem@unaffiliated/sprocklem JOIN :#esoteric
> 1582095290 346238 PRIVMSG #esoteric :14[[07Feather14]]4 M10 02https://esolangs.org/w/index.php?diff=69963&oldid=53242 5* 03IFcoltransG 5* (+12) 10Added dead link template to broken link
< 1582095313 138075 :Sgeo!~Sgeo@ool-18b982ad.dyn.optonline.net QUIT :Read error: Connection reset by peer
< 1582095340 193582 :Sgeo!~Sgeo@ool-18b982ad.dyn.optonline.net JOIN :#esoteric
> 1582096308 722819 PRIVMSG #esoteric :14[[07Clue (oklopol)14]]4 10 02https://esolangs.org/w/index.php?diff=69964&oldid=69957 5* 03IFcoltransG 5* (+172) 10/* Syntax */ Rewrote some sentences for clarity, fluency, and fixing of a spelling mistake
> 1582096498 256334 PRIVMSG #esoteric :14[[07Clue (oklopol)14]]4 10 02https://esolangs.org/w/index.php?diff=69965&oldid=69964 5* 03IFcoltransG 5* (+65) 10/* Syntax */ Added note on spaces in identifiers
< 1582097628 121130 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582097925 143224 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 QUIT :Ping timeout: 272 seconds
< 1582098850 546571 :zzo38!~zzo38@host-24-207-50-7.public.eastlink.ca PRIVMSG #esoteric :Is it possible in PostScript to specify output page numbers using the "pdfmark" command?
< 1582098951 865034 :zzo38!~zzo38@host-24-207-50-7.public.eastlink.ca PRIVMSG #esoteric :(Also, do any PostScript interpreters that do not produce PDF support any subset of uses of pdfmark?)
< 1582098965 900914 :xkapastel!uid17782@gateway/web/irccloud.com/x-szvjnugtiouczbiu QUIT :Quit: Connection closed for inactivity
< 1582099354 992178 :oerjan!oerjan@sprocket.nvg.ntnu.no PRIVMSG #esoteric :ouch, it looks like clog/tunes has started deleting old logs
< 1582099537 462577 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :They are at http://tunes.org/~nef/logs/old/
< 1582099733 332210 :oerjan!oerjan@sprocket.nvg.ntnu.no PRIVMSG #esoteric :oh. well i've already found the esolangs.org version.
< 1582099776 690241 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582099796 673564 :oerjan!oerjan@sprocket.nvg.ntnu.no PRIVMSG #esoteric :oh and they're zipped by year, i see, so even worse for linking
< 1582099839 31774 :iiee!~user@109.108.213.4 JOIN :#esoteric
> 1582099938 102028 PRIVMSG #esoteric :14[[07Feather14]]4 10 02https://esolangs.org/w/index.php?diff=69966&oldid=69963 5* 03Oerjan 5* (-32) 10Link to esolangs.org log instead
< 1582100091 155425 :TheLie!~TheLie@ip5b428f85.dynamic.kabel-deutschland.de JOIN :#esoteric
< 1582100225 926953 :zzo38!~zzo38@host-24-207-50-7.public.eastlink.ca PRIVMSG #esoteric :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.
< 1582100717 271078 :xkapastel!uid17782@gateway/web/irccloud.com/x-rifdomzukbpjzaiz JOIN :#esoteric
< 1582101284 890522 :dog_star!sid310875@gateway/web/irccloud.com/x-toqlxxzqvgkymquo QUIT :Ping timeout: 248 seconds
< 1582101296 310428 :dog_star!sid310875@gateway/web/irccloud.com/x-bghzyxxnbooorzxg JOIN :#esoteric
< 1582101380 773481 :^[!sid43445@ircpuzzles/2015/april-fools/sixth/zgrep QUIT :Ping timeout: 248 seconds
< 1582101512 393407 :^[!sid43445@ircpuzzles/2015/april-fools/sixth/zgrep JOIN :#esoteric
< 1582102354 499534 :oerjan!oerjan@sprocket.nvg.ntnu.no QUIT :Quit: Nite
< 1582107150 339523 :MDead!~MDude@97-127-171-136.cdrr.qwest.net JOIN :#esoteric
< 1582107262 293407 :MDude!~MDude@97-127-171-136.cdrr.qwest.net QUIT :Ping timeout: 260 seconds
< 1582107266 322062 :MDead!~MDude@97-127-171-136.cdrr.qwest.net NICK :MDude
< 1582108149 661354 :cpressey!~cpressey@5.133.242.4 JOIN :#esoteric
< 1582112063 802333 :TheLie!~TheLie@ip5b428f85.dynamic.kabel-deutschland.de QUIT :Remote host closed the connection
< 1582112527 672770 :arseniiv!~arseniiv@136.169.210.57 JOIN :#esoteric
< 1582113062 61268 :ddmm_!atrapmatri@gateway/shell/matrix.org/x-sdvbsqkuskwdqztp QUIT :*.net *.split
< 1582113130 691730 :ddmm_!atrapmatri@gateway/shell/matrix.org/x-sypjadpngjovtjyv JOIN :#esoteric
< 1582114550 39372 :wmww!wmwwmatrix@gateway/shell/matrix.org/x-ajqertfrywxjhgjw QUIT :Ping timeout: 252 seconds
< 1582114624 285299 :wmww!wmwwmatrix@gateway/shell/matrix.org/x-fgmambrhebwcgsef JOIN :#esoteric
< 1582114659 950089 :iiee!~user@109.108.213.4 PART #esoteric :"ERC (IRC client for Emacs 26.1)"
< 1582115352 841366 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 QUIT :Read error: Connection reset by peer
< 1582115388 131083 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582116048 387219 :arseniiv!~arseniiv@136.169.210.57 QUIT :Read error: Connection reset by peer
< 1582116112 110724 :arseniiv!~arseniiv@136.169.210.57 JOIN :#esoteric
> 1582118346 795952 PRIVMSG #esoteric :14[[07FAKE14]]4 M10 02https://esolangs.org/w/index.php?diff=69967&oldid=68815 5* 03Argv0 5* (+15) 10/* Commands */ conditional operator syntax change
> 1582118489 971610 PRIVMSG #esoteric :14[[07FAKE14]]4 M10 02https://esolangs.org/w/index.php?diff=69968&oldid=69967 5* 03Argv0 5* (-12) 10/* Examples */ adaptation to conditional operator syntax change
< 1582124165 913582 :xkapastel!uid17782@gateway/web/irccloud.com/x-rifdomzukbpjzaiz QUIT :Quit: Connection closed for inactivity
< 1582127399 41600 :MDude!~MDude@97-127-171-136.cdrr.qwest.net QUIT :Quit: Going offline, see ya! (www.adiirc.com)
< 1582127952 362720 :imode!~linear@unaffiliated/imode JOIN :#esoteric
< 1582128517 392179 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 JOIN :#esoteric
< 1582128612 204940 :Lord_of_Life!~Lord@unaffiliated/lord-of-life/x-0885362 QUIT :Ping timeout: 260 seconds
< 1582128683 853455 :Lord_of_Life_!~Lord@unaffiliated/lord-of-life/x-0885362 NICK :Lord_of_Life
> 1582128716 83601 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Amakukha 5* 10New user account
> 1582132580 180484 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=69969&oldid=69900 5* 03Amakukha 5* (+206) 10/* Introductions */
> 1582132625 867358 PRIVMSG #esoteric :14[[07User:Amakukha14]]4 N10 02https://esolangs.org/w/index.php?oldid=69970 5* 03Amakukha 5* (+62) 10Created page with "My favourite [[Brainfuck|Brainf**k]] dialect is [[Brainlove]]."
< 1582133418 918310 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 QUIT :Remote host closed the connection
> 1582133450 329117 PRIVMSG #esoteric :14[[07Brainfuck14]]4 10 02https://esolangs.org/w/index.php?diff=69971&oldid=69560 5* 03Amakukha 5* (+95) 10
> 1582133526 572212 PRIVMSG #esoteric :14[[07Urban Mller14]]4 10 02https://esolangs.org/w/index.php?diff=69972&oldid=30824 5* 03Amakukha 5* (+103) 10/* External resources */ +recent talk
> 1582133610 522598 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Pitust 5* 10New user account
> 1582133776 948928 PRIVMSG #esoteric :14[[07Brainfuck14]]4 10 02https://esolangs.org/w/index.php?diff=69973&oldid=69971 5* 03Amakukha 5* (+22) 10BF was inspired by FALSE according to the video
> 1582133846 771272 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=69974&oldid=69969 5* 03Pitust 5* (+117) 10I need to complete the sign-up, right?
< 1582134199 663446 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 JOIN :#esoteric
< 1582134264 855351 :cpressey!~cpressey@5.133.242.4 QUIT :Quit: A la prochaine.
< 1582134499 859897 :LKoen!~LKoen@81.255.219.130 JOIN :#esoteric
< 1582136403 647280 :LKoen!~LKoen@81.255.219.130 QUIT :Remote host closed the connection
< 1582136460 791208 :int-e!~noone@int-e.eu PRIVMSG #esoteric :tromp: Ooph, I pushed my formalization effort through. https://int-e.eu/~bf3/tmp/Goodstein.html
< 1582136486 769616 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(In Isabelle/HOL)
< 1582136634 307017 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric
< 1582136715 698807 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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,...
< 1582136721 705553 :int-e!~noone@int-e.eu PRIVMSG #esoteric :...kind of, but it's not immediately clear what the proof is.
< 1582137242 320939 :joes!~joes@dyndsl-080-228-188-151.ewe-ip-backbone.de JOIN :#esoteric
< 1582137312 306332 :LKoen!~LKoen@81.255.219.130 JOIN :#esoteric
< 1582138387 837561 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 PRIVMSG #esoteric :that looks like a major effort!
< 1582138428 121597 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 PRIVMSG #esoteric :does Isabelle have ascii alternatives for symbols like ⇩ ?
< 1582138499 371517 :imode!~linear@unaffiliated/imode QUIT :Ping timeout: 258 seconds
< 1582138514 902178 :int-e!~noone@int-e.eu PRIVMSG #esoteric :tromp: It's actually a subscript (for the next character) in the editor. Could be replaced by _ for ASCII.
< 1582138624 568299 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582138844 763918 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582138848 34756 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 PRIVMSG #esoteric :link added to now capitalized Goodstein.hs in AIT repo
< 1582138935 420746 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I'm happy with the result though. Will probably clean up a bit more another day.
< 1582138953 646925 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Hmm, linking to my tmp directory isn't good :-/
< 1582138998 827158 :int-e!~noone@int-e.eu PRIVMSG #esoteric :And I haven't decided yet where to put it permanently. But I'll find a public place.
> 1582139168 329536 PRIVMSG #esoteric :14[[07Special:Log/newusers14]]4 create10 02 5* 03Asasnat 5* 10New user account
< 1582139475 237536 :joes!~joes@dyndsl-080-228-188-151.ewe-ip-backbone.de PART #esoteric :"Leaving"
> 1582139622 652215 PRIVMSG #esoteric :14[[07Esolang:Introduce yourself14]]4 10 02https://esolangs.org/w/index.php?diff=69975&oldid=69974 5* 03Asasnat 5* (+306) 10
< 1582139627 594939 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 PRIVMSG #esoteric :feel free to add it to AIT repo
> 1582139659 723897 PRIVMSG #esoteric :14[[07User:Asasnat14]]4 N10 02https://esolangs.org/w/index.php?oldid=69976 5* 03Asasnat 5* (+31) 10Created page with "hi im guy who likes programming"
< 1582139664 822620 :tromp!~tromp@2a02:a210:ca3:2800:9884:4170:921d:a690 PRIVMSG #esoteric :i also link to Goodstein.hs from Wikipedia article
< 1582139666 159970 :int-e!~noone@int-e.eu PRIVMSG #esoteric :And oops, I got the mapping wrong... should be [0,1,3,4,27,28,30,31,81].
< 1582139776 638542 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :int-e: are you fighting a dire hydra?
< 1582139872 300597 :int-e!~noone@int-e.eu PRIVMSG #esoteric :b_jonas: Nah, I'm not in the mood for hydras, though that should fit into the same kind of ordinal number representation.
< 1582140059 35632 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :ok
< 1582140244 941009 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582140289 250684 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :ok. I don't actually know how Goodstein works.
< 1582140407 940646 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :hi!
< 1582140420 606224 :LKoen!~LKoen@81.255.219.130 QUIT :Remote host closed the connection
< 1582140536 293657 :LKoen!~LKoen@lstlambert-657-1-123-43.w92-154.abo.wanadoo.fr JOIN :#esoteric
< 1582140712 852704 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582140768 869663 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :arseniiv: ooh, a box packing thing.... I don't know
< 1582140865 903696 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: You should try this months' Ponder This problem, it has a similar (but more awkward) binpacking flavour.
< 1582140891 104514 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582140971 642713 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582140978 130627 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: It's something that /should/ be NP-hard but will be awkward to actually prove NP-hard.
< 1582140986 224903 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :mmhm
< 1582140986 821765 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(The biased coin problem.)
< 1582140997 196830 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :int-e: why should it be NP-hard?
< 1582141077 466347 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582141082 829150 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582141176 62258 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(Though obviously I may just lack imagination. My "awkward to prove" includes the possibility that it's actually false for some incredible reason.)
< 1582141205 772564 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :❝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
< 1582141220 896015 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :no no no I won’t
< 1582141221 514970 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582141256 855903 :int-e!~noone@int-e.eu PRIVMSG #esoteric :tow parts -> two equal parts
< 1582141298 829916 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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?
< 1582141307 21380 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(Deciding whether you can get equality is NP-complete, cf. https://en.wikipedia.org/wiki/Partition_problem)
< 1582141308 430539 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :not that that helps much
< 1582141366 176201 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582141435 892137 :int-e!~noone@int-e.eu PRIVMSG #esoteric :b_jonas: The downside is that the number of pieces you're working with is exponential in the input size.
< 1582141471 868799 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582141479 145169 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :I should get back to that problem some day by the way
< 1582141584 267980 :imode!~linear@unaffiliated/imode JOIN :#esoteric
< 1582141693 970547 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.)
< 1582141742 38957 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :yes, but only sqrt(n) of those numbers can count
< 1582141751 935790 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :well, O(sqrt(n))
< 1582141768 527373 :int-e!~noone@int-e.eu PRIVMSG #esoteric :?
< 1582141786 749608 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :all the other types of boxes are small even if you take all the available ones together
< 1582141807 544547 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :because of Cramer's theorem
< 1582141830 320059 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :probably doesn't matter in whether it's NP-complete though
< 1582141843 690011 :int-e!~noone@int-e.eu PRIVMSG #esoteric :But they're still important for the optimum.
< 1582141863 533657 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :hopefully I infected you with not too hopeless a problem
< 1582141883 945868 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :hmm, maybe they can be if the optimum is exponentially close to 1/k so you have to approximate it very closely
< 1582141888 881268 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: Nah, I think it *is* hopeless.
< 1582141908 17980 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :but not if you only want to get within 10**(-6) of 1/k
< 1582141917 6086 :int-e!~noone@int-e.eu PRIVMSG #esoteric :b_jonas: Clearly the results about approximability do not carry over.
< 1582142172 503700 :LKoen!~LKoen@lstlambert-657-1-123-43.w92-154.abo.wanadoo.fr 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.”
< 1582142353 968466 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582142449 775501 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :that one counterexample I found was pretty close to the optimum, yeah
< 1582142456 802044 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :though maybe there are very bad ones
< 1582142476 400335 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :I’d be interested what could be done to find them BTW :D
< 1582142477 660878 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Presumably you can randomize a little and avoid the terrible cases.
< 1582142500 667561 :Phantom_Hoover!~phantomho@unaffiliated/phantom-hoover JOIN :#esoteric
< 1582142502 821357 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582142536 70203 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :unless of course your inputs are too secret
< 1582142664 102268 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582142723 431723 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582142770 816204 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582142770 942059 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :n’t be hard, I wonder why I hadn’t stumbled upon it myself)
< 1582142774 704836 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I also don't have the right theoretical background on this.
< 1582142792 214838 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :arseniiv: that one is much easier
< 1582142809 770988 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: Welcome to the wonderful world of entropy coding.
< 1582142819 986683 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582142835 713054 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :you can do better than this, arithmetic coding is probably optimal
< 1582142856 722681 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1582142939 286875 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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 :)
< 1582142955 805505 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582142956 989681 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :(that was an answer to the older post)
< 1582142981 358506 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric : arseniiv: that one is much easier => yeah I know! :)
< 1582142983 91715 :MDude!~MDude@97-127-171-136.cdrr.qwest.net JOIN :#esoteric
< 1582142989 961118 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :you can get an arbitrarily long random output, nobody will notice that the seed is only 256 bits long
< 1582142997 182505 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :s/256 bytes/256 bits/
< 1582143009 346078 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :you can use 512 bits if you're particularly paranoid
< 1582143030 669374 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :yeah, probably better use 512 bits
< 1582143083 758628 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric : 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
< 1582143100 469673 :int-e!~noone@int-e.eu PRIVMSG #esoteric :ACTION shrugs.
< 1582143112 379345 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I'd use some kind of range coder.
< 1582143147 434639 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582143214 470375 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582143266 120958 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582143288 423546 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582143344 761841 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :the easiest way to do that is do pairs of coin flips, and rethrow for HH and TT
< 1582143355 13016 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :and then use the HT and TH results as your fair flip input
< 1582143361 330387 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582143362 610054 :spruit11!~unknown@ip56522cc1.speed.planet.nl PRIVMSG #esoteric :Neat.
< 1582143387 371936 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :arseniiv: yes, that's how arithmetic coding works
< 1582143392 109505 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric : 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
< 1582143421 691425 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :so now I see how that person gave an answer almost immediately: they probably knew arithmetic coding too
< 1582143473 740417 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric : and then use the HT and TH results as your fair flip input => definitely cool thing
< 1582143491 30054 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :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
< 1582143536 815478 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: this is a sketch: http://paste.debian.net/1131148/
< 1582143561 814 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :it's an example of steganographic typography: I use a known pre-existing text verbatim, and hide information in its presentation
< 1582143570 667823 :int-e!~noone@int-e.eu PRIVMSG #esoteric :arseniiv: (It's not code because I (deliberately) didn't include the policy for balancing refills and making choices.)
< 1582143600 665270 :b_jonas!~x@catv-176-63-14-111.catv.broadband.hu PRIVMSG #esoteric :sadly it's not very impressive because I managed to hide very little information
< 1582143629 474867 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582143678 396841 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :(when optimizing, that relates to a binary digits of 1/k)
< 1582143771 288930 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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,...
< 1582143777 208736 :int-e!~noone@int-e.eu PRIVMSG #esoteric :...keeping r around 2^32 * max(k) is probably good enough.
< 1582143804 288980 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :mhm
< 1582143814 73609 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(*waves hands*)
< 1582143838 585757 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :I just can’t absorb too much at once :D
< 1582143934 96186 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :wait, is it bounded-space after all?
< 1582143945 511676 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :int-e: ^
< 1582143949 995056 :int-e!~noone@int-e.eu PRIVMSG #esoteric :Well, that's up to the user...
< 1582143961 425268 :int-e!~noone@int-e.eu PRIVMSG #esoteric :if you just keep adding flips you'll run out of space.
< 1582143993 6721 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(imagine an arbitrary precision type for "int")
< 1582144031 592472 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :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
< 1582144085 16047 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :but that one isn’t good because we can’t tweak it, and a normal arithmetic coding is tweakable
< 1582144099 503454 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :(that one = tree one I described)
< 1582144099 796502 :int-e!~noone@int-e.eu PRIVMSG #esoteric :what do you want to tweak?
< 1582144137 27774 :arseniiv!~arseniiv@136.169.210.57 PRIVMSG #esoteric :and your sketch shows how we can keep the buffer the length we want
< 1582144167 371298 :int-e!~noone@int-e.eu PRIVMSG #esoteric :You can get arbitrary (rational) distributions with a fairly minor tweak...
< 1582144223 472562 :int-e!~noone@int-e.eu PRIVMSG #esoteric :The add_flip can be generalized to adding an arbitrary uniform choice (multiply by number of choices c instead of 2; add value [0.. 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
< 1582144316 222832 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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..