←2014-12-29 2014-12-30 2014-12-31→ ↑2014 ↑all
00:03:50 <shachaf> I've never heard of such a card.
00:05:00 <int-e> http://magiccards.info/query?q=!Sublime+Archangel seems to qualify, technically.
00:05:44 <int-e> (but it's static, not triggered; not sure what zzo38 wants to do)
00:06:29 <shachaf> Fair enough.
00:07:08 -!- roasted42 has quit (Ping timeout: 265 seconds).
00:07:56 <zzo38> Well, I meant one that only applies to tapped creatures rather than all of them.
00:08:33 -!- roasted42 has joined.
00:08:56 <int-e> (the card is linked from http://mtgsalvation.gamepedia.com/Exalted ; I didn't remember what exaltation does)
00:10:49 <int-e> zzo38: I doubt that such ccards exist, but which do you want: "all tapped creatures gain exalted" or "whenever a creature is tapped, it gains "exalted"?"
00:15:47 <zzo38> First one
00:17:31 <zzo38> The other kind of card would be one causing all tapped creatures to lose exalted ability.
00:20:03 <int-e> http://gatherer.wizards.com/Pages/Search/Default.aspx?text=+[exalted] is short, doesn't look like it.,
00:26:46 <pikhq> Feels like they didn't do enough with Exalted.
00:31:37 <int-e> wtf ... youtube's players shows static noise on errors?!
00:31:55 <int-e> U-S-E-L-E-S-S !
00:38:44 -!- MoALTz__ has joined.
00:41:17 -!- MoALTz_ has quit (Ping timeout: 240 seconds).
00:45:26 -!- Phantom_Hoover has quit (Quit: Leaving).
00:47:17 -!- roasted42 has quit (Ping timeout: 240 seconds).
00:48:21 -!- roasted42 has joined.
00:51:34 <fizzie> int-e: It's supposed to have an explanation for the error on top of the noise.
00:52:10 <fizzie> (Although that doesn't make the animated noise part any more useful, that's certainly true.)
00:52:13 <int-e> fizzie: yeah I was looking at the comments.
00:52:48 <int-e> (I had downloaded the video separately)
00:53:18 * int-e is a bit starved for bandwidth; 16 kB/s isn't much.
01:09:58 -!- shachaf has quit (Changing host).
01:09:58 -!- shachaf has joined.
01:13:15 -!- Phantom_Hoover has joined.
01:13:54 -!- Phantom_Hoover has quit (Client Quit).
01:21:43 -!- boily has joined.
01:29:30 -!- roasted42 has quit (Ping timeout: 250 seconds).
01:35:58 * adu gives int-e some bandwidth
01:36:17 -!- roasted42 has joined.
01:41:20 -!- Sprocklem has joined.
01:52:33 -!- FreeFull has quit (Ping timeout: 256 seconds).
02:04:23 -!- tswett2 has joined.
02:04:46 <tswett2> So I think I found something interesting.
02:05:38 <tswett2> Define a "display" as a set of natural numbers, with the topology over displays being generated by the sets {s : s is a display containing n}, where n is a natural number.
02:06:37 <tswett2> Let ->> denote a continuous function. Then there's a certain "obvious" function encode :: (display ->> display) -> display, with a left inverse decode :: display -> (display ->> display).
02:07:47 <tswett2> Both encode and decode appear to be continuous.
02:08:35 -!- FreeFull has joined.
02:09:13 <tswett2> But lemme start over.
02:11:42 <tswett2> Define a "space" as a set of integers equipped with an equivalence relation.
02:11:53 <tswett2> Natural numbers, rather.
02:12:03 <tswett2> We'll assume that each natural number can be interpreted as a computer program.
02:12:34 <tswett2> Define RE as the set of all computer programs that enumerate natural numbers, with the equivalence relation being that the two programs enumerate the same set.
02:12:38 <int-e> computer program = partial recursive function?
02:12:58 <tswett2> Something like that.
02:13:34 <tswett2> Given spaces A and B, define A ->> B as the set of all computer programs which take a program in A and return a program in B, respecting the equivalence relation.
02:14:21 <tswett2> Two elements of A ->> B are equivalent if, for every input, the resulting outputs are equivalent.
02:15:15 <tswett2> Then there is a computer program encode :: (RE ->> RE) ->> RE with a left inverse which is a computer program decode :: RE ->> (RE ->> RE).
02:16:04 -!- roasted42 has quit (Ping timeout: 245 seconds).
02:18:10 -!- roasted42 has joined.
02:22:01 -!- Tod-Autojoined has changed nick to TodPunk.
02:24:45 <int-e> Ok, destroying the abstraction: encode takes a Gödel number g of a program transformation, and returns a program enumerating the singleton set { g }. Decode tkaes a program, runs it until the first element g is produced, then runs g as aprogram transformation.
02:26:09 <int-e> Ah, I did not clearly separate "Gödel number of a program" from "program".
02:26:26 -!- AndoDaan has joined.
02:28:30 <tswett2> Your definition of encode doesn't respect the equivalence relation.
02:28:57 <tswett2> Since given different Godel numbers that encode the same function, it'll return different functions.
02:29:02 <int-e> true\u.
02:29:28 <adu> what's a Gödel number?
02:30:07 <tswett2> I think int-e is using "program" to mean what I'd call a computable function and "Godel number of a program" to mean what I'd just call a program.
02:30:39 <tswett2> "Godel number of a program" just means a number which encodes a computer program, under a scheme such that every possible computer program is represented (in a computable way) by some number.
02:31:14 <adu> no, a program transformation
02:31:37 <tswett2> So lemme try to describe what encode and decode do, exactly.
02:32:44 <tswett2> encode takes a computer program f :: RE ->> RE. It then performs a computation simultaneously for every natural number n.
02:33:21 <tswett2> The computation begins by interpreting the number n as a pair (p, T), where p is a natural number and T is a finite set of natural numbers.
02:33:21 -!- AndoDaan has quit (Ping timeout: 272 seconds).
02:33:41 <adu> tswett2: what is RE?
02:34:03 <tswett2> RE is the set of all computer programs that enumerate natural numbers, with the equivalence relation being that the two programs enumerate the same set.
02:34:08 <adu> oh
02:34:34 <adu> sounds Turing-esque
02:34:51 <tswett2> The computation then proceeds by running f on T. If f(T) ever lists p, then encode(f) lists n.
02:36:00 <tswett2> "encode" is an injective function because every computer program RE ->> RE is defined entirely by its behavior on inputs which enumerate finite sets.
02:37:01 <adu> I'm interested in an abstract and yet concrete definition of a thing that can represent threads, coroutines, and continuations all at the same time
02:37:19 <tswett2> A Turing machine, perhaps?
02:37:24 <adu> perhaps
02:37:30 <tswett2> Now, decode takes a computer program s :: RE, and returns a new computer program decode(s) which takes another computer program t and finally returns a computer program decode(s)(t).
02:37:31 <nys> continuations can represent threads, coroutines, and continuations all at the same time
02:37:43 <elliott> nys: I'm going to need a citation for that last one
02:37:48 <vanila> how can continuations represent threads?
02:38:07 <nys> i thought you could do cooperative threading <.< >.>
02:38:14 <nys> somehow
02:38:27 <nys> maybe i need to crack out the ol scheme again
02:38:52 <tswett2> decode(s)(t) performs a computation simultaneously for all pairs (p, T), where p is a natural number and T is a finite set of natural numbers.
02:38:54 <adu> the ol scheme?
02:39:05 <adu> scheme is new, r7rs was just released
02:39:19 <nys> the brand spankin new scheme
02:39:24 <tswett2> Then, uh, lemme see.
02:40:41 <tswett2> Actually, lemme start over with this one.
02:40:44 <int-e> tswett2: I think we have to talk about termination a bit.
02:41:05 <tswett2> decode(s)(t) performs a computation simultaneously for all numbers n enumerated by s.
02:41:14 <adu> nah, the halting problem is so 20th century
02:41:45 <tswett2> The computation consists of interpreting the number n as (p, T), then waiting for t to spit out all elements of T, then spitting out p.
02:41:49 <adu> I think D. Knuth might be on to something with BDDs, it totally side-steps the halting problem
02:41:51 -!- roasted42 has quit (Ping timeout: 256 seconds).
02:41:58 <tswett2> int-e: do we?
02:42:07 <vanila> what is BDD?
02:42:18 <adu> vanila: binary decision diagram
02:42:26 <vanila> also I don't think the halting problem is actually a problem
02:42:31 <vanila> it's just a fact
02:42:34 <int-e> tswett2: a program that terminates without producing a number is equivalent to one that never terminates and never produces any number?
02:42:43 <adu> vanila: essentially a binary tree representation of a map from [Bool] -> [Bool]
02:42:45 <tswett2> int-e: yeah.
02:42:52 <vanila> hmm
02:43:06 <int-e> tswett2: ok. that part screws with my intuition.
02:43:15 <tswett2> You may as well say that no program ever terminates.
02:43:26 <tswett2> If a program would terminate, it instead hangs forever, spitting out nothing.
02:43:49 -!- roasted42 has joined.
02:43:55 <adu> D. Knuth, you know the guy who invented the arrow, tex, metafont, taocp, etc.
02:43:59 <adu> and MMIX
02:44:02 <vanila> Knuth is good
02:44:06 <vanila> He invented some algorithms too
02:44:10 <coppro> one or two
02:44:21 <vanila> actually three, at least
02:44:30 <vanila> LR parsing, KMP string matching algorithm, dancing links
02:44:36 <int-e> tswett2: ok, back to your decocde(s)(t).
02:44:48 <adu> https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
02:44:58 <adu> he invented the arrow
02:45:34 <tswett2> Now we just have to invent up-bow notation so that we can perform up-archery notation.
02:45:44 <adu> lolol
02:46:11 <coppro> tswett2: ++
02:48:52 <int-e> tswett2: the main property that you're exploioting seems to be that RE ->> RE only allows monotone functions (in terms of the encoded sets), plus a compactness property.
02:49:42 <tswett2> Lessee. I'm exploiting the monotone thing, yeah. As for compactness, lemme think.
02:49:59 <tswett2> I didn't notice any compactness going on here, but you probably know something I don't.
02:51:24 <tswett2> RE is certainly compact, because the only open set containing the empty set is the universal set.
02:52:06 <adu> tswett2++
02:52:40 <tswett2> Look at me, I'm talking about the topology of RE without ever having defined a topology for RE.
02:53:08 <nys> i wasn't saying that
02:53:11 <nys> but i was thinking it
02:53:45 <tswett2> One topology for RE is that topology I defined for "displays" above.
02:54:16 <tswett2> Namely, the topology for RE is generated by sets of the form {s : s is an element of RE enumerating n}.
02:54:23 <tswett2> Where n is a natural number.
02:57:52 -!- shikhin_ has quit (Ping timeout: 255 seconds).
02:58:46 -!- boily has quit (Quit: NERVOUS CHICKEN).
03:07:14 -!- scoofy has quit (Ping timeout: 244 seconds).
03:15:06 <int-e> tswett2: I'm just wrong. Continuity of the RE ->> RE part is what you need, for the claim that its determined by the behaviour on finite sets.
03:16:11 <tswett2> Right.
03:16:13 <int-e> (rather, that *is* the claim, afaiui)
03:16:50 <tswett2> Claim: the behavior of a computer program RE ->> RE is determined by its behavior on finite sets.
03:17:58 <tswett2> Um, lemme think how to prove this.
03:19:10 <tswett2> Suppose f is a computer program RE ->> RE, s is a computer program RE, and f(s) enumerates the natural number n.
03:20:28 <tswett2> Claim: there exists a finite set S such that S is a subset of the set enumerated by s, and f(S) also enumerates the natural number n.
03:20:49 -!- roasted42 has quit (Ping timeout: 255 seconds).
03:21:12 -!- bb010g has quit (Quit: Connection closed for inactivity).
03:21:33 <tswett2> Informal "proof": by something like Rice's theorem, the only way f can analyze its argument is by running it, and f(s) must enumerate n after running s for only finitely many steps.
03:22:39 -!- roasted42 has joined.
03:24:32 <tswett2> Since f is in RE ->> RE, for every computer program s' in RE that enumerates the same set as s, f(s') must also enumerate n.
03:25:05 <tswett2> Ooh, where is this going.
03:27:52 -!- AndoDaan has joined.
03:29:54 <tswett2> I need to prove that there's some computer program S in RE such that S enumerates a finite subset of the set enumerated by s, and S so closely matches some program s' that f can't tell the difference.
03:33:12 <tswett2> Let me start over.
03:33:27 <tswett2> Suppose that f is a computer program RE ->> RE, s is a computer program RE, and f(s) enumerates the natural number n.
03:34:05 <tswett2> Furthermore, assume that whenever t is a computer program in RE that enumerates a finite subset of the set enumerated by s, f(t) does not enumerate the natural number n.
03:34:18 <tswett2> Clearly s enumerates an infinite set.
03:34:30 <tswett2> Let M be an arbitrary Turing machine.
03:35:51 <int-e> Ah.
03:35:59 <tswett2> Given any computer program u in RE, let stop(u, M) be the program that alternates between running u and running M, halting whenever either one halts.
03:36:09 <int-e> You're going to run s and T in parallel. Right.
03:36:42 <tswett2> If M does not halt, then f(stop(s, M)) enumerates n, because stop(s, M) enumerates the same set that s does.
03:37:03 <tswett2> If, on the other hand, M does halt, then f(stop(s, M)) does not enumerate n, by our assumption about t.
03:37:34 <int-e> Right. Now a fixed point, and done. Thanks!
03:37:35 <tswett2> So we can solve the halting problem by simultaneously running f(stop(s, M)) and M, and seeing which thing happens first: f(stop(s, M)) enumerates n, or M halts.
03:44:04 <int-e> (and monotonicity works similarly: if U \subsetneq V are finite sets, then produce the elements of U, then run M, then product the remaining elements of V)
03:45:09 <tswett2> Oh, I meant to mention "the other topology" on RE.
03:46:34 <tswett2> Let the space Si be the set of all computer programs, with two programs being equivalent if and only if they both halt or neither one halts.
03:49:05 <tswett2> Then an open set of REs is defined by a function RE ->> Si; a RE is in the set if and only if its image halts.
03:49:25 <tswett2> Which isn't actually a topology, even though it's a lot like a topology.
03:50:12 -!- scoofy has joined.
03:50:49 <tswett2> You can't take the union of an arbitrary collection of those; you can only take the union of a recursively enumerable collection of them.
03:51:38 -!- roasted42 has quit (Ping timeout: 250 seconds).
03:52:54 -!- scoofy has quit (Quit: Leaving).
03:53:19 -!- roasted42 has joined.
04:00:47 <int-e> hmm recursive topology
04:01:10 <int-e> tswett2: does "Si" have a meaning?
04:02:11 <tswett2> It's the Sierpinski space.
04:03:09 <int-e> Ah, forgetting about all this extra structure. Yes, of course.
04:05:09 <adu> int-e: it also means yes in a couple languages
04:05:46 <int-e> adu: Really! But it seemed irrelevant to the discussion.
04:05:51 <nys> c'est si belle
04:05:51 -!- incomprehensibly has changed nick to glowcoil.
04:06:27 <int-e> да
04:07:23 <adu> תודה
04:08:04 <int-e> I should try to relearn russian
04:09:17 <adu> нет
04:18:37 -!- AndoDaan has quit (Ping timeout: 240 seconds).
04:21:39 <int-e> adu: вы не понимаете.
04:21:50 <int-e> meh, even most of the grammar is gone.
04:22:27 <int-e> (though there's little surprise there, russian has a lot of it)
04:32:29 -!- roasted42 has quit (Ping timeout: 265 seconds).
04:33:11 -!- roasted42 has joined.
04:48:07 -!- adu has quit (Quit: adu).
05:03:41 -!- vanila has quit (Quit: Leaving).
05:03:57 -!- tswett2 has quit (Ping timeout: 240 seconds).
05:06:35 -!- GeekDude has quit (Quit: {{{}}{{{}}{{}}}{{}}} (www.adiirc.com)).
05:14:38 -!- nys has quit (Quit: quit).
05:19:05 -!- Solace has joined.
05:21:09 <Solace> hmmmm
05:23:29 -!- roasted42 has quit (Ping timeout: 264 seconds).
05:25:16 -!- roasted42 has joined.
05:25:51 <Solace> How do you set ops/voiced and channel modes
05:29:01 <zzo38> Use the MODE command
05:29:13 <zzo38> See HELP CMODE for descriptions.
05:33:41 -!- augur_ has changed nick to augur.
05:51:15 -!- AndoDaan has joined.
06:01:27 -!- tswett has joined.
06:02:28 -!- shikhin has joined.
06:04:35 -!- adu has joined.
06:07:42 -!- roasted42 has quit (Ping timeout: 265 seconds).
06:09:17 -!- roasted42 has joined.
06:30:15 -!- MoALTz_ has joined.
06:32:37 -!- MoALTz has joined.
06:33:37 -!- MoALTz__ has quit (Ping timeout: 256 seconds).
06:35:08 <zzo38> I got Magic: the Puzzling for the Christmas present.
06:35:14 <zzo38> I figured out a few of them so far.
06:35:15 -!- MoALTz_ has quit (Ping timeout: 244 seconds).
06:55:27 -!- roasted42 has quit (Ping timeout: 258 seconds).
06:57:53 -!- roasted42 has joined.
06:58:26 -!- oerjan has joined.
07:29:09 -!- dts|pokeball has quit (Ping timeout: 256 seconds).
07:34:17 -!- roasted42 has quit (Ping timeout: 264 seconds).
07:35:50 -!- roasted42 has joined.
07:40:37 -!- Sprocklem has quit (Ping timeout: 240 seconds).
07:41:12 -!- Patashu has joined.
07:48:04 <b_jonas> zzo38: great
07:48:11 -!- MoALTz has quit (Quit: Leaving).
08:15:39 -!- roasted42 has quit (Ping timeout: 245 seconds).
08:18:24 -!- roasted42 has joined.
08:34:22 -!- roasted42 has quit (Ping timeout: 240 seconds).
08:39:23 -!- AndoDaan has quit (Ping timeout: 240 seconds).
08:39:24 -!- roasted42 has joined.
08:45:05 -!- roasted42 has quit (Ping timeout: 256 seconds).
08:49:00 -!- adu has quit (Quit: adu).
09:02:00 -!- AndoDaan has joined.
09:24:57 -!- ocharles_ has quit (Ping timeout: 258 seconds).
09:25:46 -!- ocharles__ has joined.
09:48:48 -!- shikhin_ has joined.
09:51:37 -!- shikhin has quit (Ping timeout: 240 seconds).
10:12:07 -!- supay_afk has changed nick to supay.
10:20:53 <oerjan> `echo hi
10:20:53 <HackEgo> hi
10:21:21 <AndoDaan> `echo `echo hi
10:21:21 <HackEgo> ​`echo hi
10:24:04 <oerjan> fizzie: the wiki - HackEgo link is broken
10:24:22 <AndoDaan> Oerjan, if I implement BCT in a language but hard code the instructions and init data-string instead of those being inputted, would that detract from its TC-ness?
10:24:40 <oerjan> AndoDaan: no. that's what i did for ///
10:25:10 <AndoDaan> Okay. I figured, but wanted to make sure.
10:25:13 <Jafet> Called a compiler?
10:25:39 <oerjan> but i don't hold much with this idea some others have of separating input from program when defining TC-ness.
10:26:59 * oerjan is wondering if that idiom he just used actually exists.
10:27:17 <AndoDaan> coined and minted.
10:27:31 <oerjan> TC-ness is _always_ essentially about compiling
10:27:52 <oerjan> it's just that you get to include the input as well as the program
10:28:30 <oerjan> AndoDaan: this applies to all output-only languages, at least.
10:28:33 <coppro> oerjan: you must have some way to distinguish input and program, however
10:28:41 <oerjan> coppro: no, you do not.
10:28:46 <AndoDaan> realtime event handling doesnt' change a language possibillities at all?
10:28:56 <oerjan> you compile a _computation_, not program.
10:29:28 <oerjan> AndoDaan: turing-completeness isn't about that.
10:29:33 <coppro> mm right the thing I was thinking when I said that is completely stupid
10:29:42 <coppro> the thing I was thinking before that is more right
10:29:44 <coppro> I will go with that
10:30:00 <Jafet> Realtime weapon change
10:30:35 <coppro> it works because of the halting problem
10:30:41 <AndoDaan> ^ very important, but not to TC-ness, i guess.
10:31:37 <coppro> No, I mean that the Halting Problem is what lets us ignore the machine/input distinction.
10:32:33 <coppro> A language is TC if, given a Turing machine with input, you can define some finite process which generates an instance of a program in that language, with input if applicable, which produces the same result.
10:32:48 <AndoDaan> Computer thrown toward the event horizon of a black hole. Time dilates to infinity, halting problem solved?
10:33:02 <coppro> You can't use the same definition for more restricted classes of computation, because you can always just run the computation and generate some other computation with the same result
10:33:45 <coppro> e.g. an NFA-plus-input can be transformed into a DFA-plus-input, because you can just run the NFA, get "accept" or "reject", and then create an accepting or rejecting DFA
10:34:00 <coppro> but a TM-plus-input can't be run
10:35:25 <AndoDaan> Non-Deterministic Finita Algorithm?
10:35:35 <AndoDaan> Automaton*
10:35:57 <Jafet> Well, we're not talking about finite automata
10:36:50 <oerjan> coppro: depends. NP-completeness works essentially the same way as TC, with "finite" replaced by "polynomial-time" or even "logarithmic space"
10:37:52 <oerjan> it works as long as the resources used for "compiling" are less than what you need to solve the problem.
10:39:00 <oerjan> on the other hand you have the circuit complexity classes, where you definitely need to distinguish the input.
10:40:16 <oerjan> (because you are trying to define classes that are _weaker_ than your compiler.)
10:42:15 <coppro> oerjan: right.
10:43:22 <coppro> btw, QTMs are shit
10:43:52 <oerjan> hm?
10:44:22 <AndoDaan> Quantum Turing Machines?
10:44:40 -!- ocharles__ has quit (Changing host).
10:44:40 -!- ocharles__ has joined.
10:44:42 -!- ocharles__ has changed nick to ocharles.
10:45:07 <oerjan> i assumed so, i don't know why he thinks they are shit though.
10:46:05 <AndoDaan> First correct guess I made here.
10:46:32 <AndoDaan> I'm getting learn-ned.
10:47:09 <oerjan> ocharles: hey are you the ollie charles of 24 days of haskell fame? great series!
10:47:29 <ocharles> oerjan: that's me!
10:47:32 <ocharles> thank you :)
10:47:44 <ocharles> did you catch this year's series?
10:48:08 <oerjan> i am in the process, i have a bit of reddit catchup to do
10:49:09 <oerjan> i'm up to the template haskell one
10:50:37 <ocharles> ah
10:50:49 <ocharles> i might do 12 in future years, cause no one can read 24 :P
10:51:12 <oerjan> well maybe not if they're all as long as the TH one
10:51:50 <ocharles> yea, the guest posts are longer
11:00:32 <fizzie> oerjan: Oh, right: it needs to be started manually, and Gregor started HackEgo last.
11:01:40 <fizzie> oerjan: In theory, it should be on now.
11:01:53 <oerjan> TOO LATE
11:01:57 <fizzie> TOO LITTLE
11:02:16 <oerjan> (i already did today's edits)
11:11:54 -!- zzo38 has quit (Ping timeout: 258 seconds).
11:14:16 -!- shikhin_ has changed nick to shikhin.
11:14:41 <Solace> ah yes
11:14:51 <Solace> I should use a VPS again
11:32:24 -!- SopaXorzTaker has joined.
11:32:24 -!- SopaXorzTaker has quit (Changing host).
11:32:24 -!- SopaXorzTaker has joined.
11:34:54 -!- Patashu has quit (Ping timeout: 258 seconds).
11:51:10 -!- rade has quit (Quit: Leaving).
11:52:59 -!- rade has joined.
12:49:16 -!- coppro has quit (Ping timeout: 258 seconds).
13:04:52 -!- tromp_ has joined.
13:05:49 -!- tromp__ has quit (Read error: Connection reset by peer).
13:08:56 -!- Phantom_Hoover has joined.
13:22:46 <AndoDaan> Where on the body would a "save your GODDAMN CODE!" tattoo be the most effective?
13:25:11 <oerjan> front of head hth
13:27:22 <AndoDaan> It does. In pointing out that Prison-Breaking it might be the way to go.
13:28:30 <oerjan> i don't believe putting a tattoo there is actually illegal in most western countries
13:30:07 -!- shikhin has quit (Ping timeout: 256 seconds).
13:36:47 -!- oerjan has quit (Quit: leaving).
13:48:43 -!- coppro has joined.
14:01:06 -!- kallisti has joined.
14:19:02 -!- Lymia has quit (Ping timeout: 245 seconds).
14:26:51 -!- Sprocklem has joined.
14:33:28 -!- shikhin has joined.
14:47:22 -!- boily has joined.
14:50:10 -!- Solace has quit (Quit: Connection closed for inactivity).
14:50:57 -!- nycs has joined.
14:50:57 -!- nycs has changed nick to `^_^v.
14:53:52 -!- Lymia has joined.
14:57:52 -!- GeekDude has joined.
15:08:41 -!- mitchs has joined.
15:31:30 <HackEgo> [wiki] [[Talk:Budget]] N http://esolangs.org/w/index.php?oldid=41560 * AndoDaan * (+385) Asking if esolangs.org's the right place for budget.
15:37:35 -!- SopaXorzTaker has quit (Remote host closed the connection).
15:38:08 <fizzie> 2See.
15:38:13 <fizzie> s/^2//
16:00:45 <Vorpal> fizzie, does a zero length write with W in SOCK make any sense ever?
16:01:11 <Vorpal> cfunge checks the length is zero or greater, but I think it should check it is 1 or greater
16:01:21 <Vorpal> Going through bugs found with coverity
16:01:44 <Vorpal> Deewiant, your opinion would also be interesting ^
16:04:49 <rade> Anyone familiar with the CompCert C compiler?
16:04:50 <rade> http://compcert.inria.fr/
16:10:11 <boily> I'm not, but it seems like a very interesting concept.
16:11:15 <rade> I wonder if the CompCert C compiler addresses this issue: http://cm.bell-labs.com/who/ken/trust.html
16:12:17 <Taneb> rade, do you trust your verification?
16:12:48 <Taneb> Do you trust that if what you are verifying is true then you can trust the compiler?
16:13:15 <Jafet> The "I didn't read my compiler code" issue can only be solved by reading your compiler code
16:15:21 <rade> Taneb, it's supposedly mathematically proved itself. I think this removes the need to trust it. Still, the design of the compiler's proof could be lacking, I guess.
16:15:34 <rade> you have to choose what to prove in the design and implementation
16:15:40 <Taneb> rade, there's still a LOT of things you need to trust
16:16:20 <Taneb> Like, do you trust the compiler you used to compile it CompCert?
16:16:48 <rade> couldn't CompCert technically compile itself?
16:17:15 <rade> I don't know if it does, though
16:17:26 <FireFly> Yes, but you need to bootstrap it
16:17:30 <Taneb> You'd have to bootstrap it from somewhere
16:17:39 <Jafet> You have to trust even more things than the compiler source
16:17:41 <FireFly> If not, you need to obtain the CompCert compiled pre-compiled already from somewhere
16:17:51 <FireFly> Which of course means you need to trust that source
16:18:10 <FireFly> s/the CompCert/& C compiler/
16:18:26 <Taneb> Of course, how much do you trust your computer itself?
16:18:43 <rade> there's always bitflips, right?
16:18:46 <rade> I get your point
16:18:58 <rade> well, it's a step in the right direction, at least
16:19:06 <rade> the less you have to trust the better
16:19:11 <Taneb> It's certainly a step in a direction
16:19:46 <Jafet> You need to trust: the clight semantics, the cambridge x86/arm semantics, the coq binary you used to run the proof
16:19:58 <Jafet> The coq specification of compcert
16:20:25 <b_jonas> depends on which computer
16:23:08 -!- mihow has joined.
16:25:53 <Deewiant> Vorpal: man 3p write says "If nbyte is zero and the file is not a regular file, the results are unspecified." man 3p send and sendto don't say anything about the zero-length case. SOCK.W is probably meant as a thin wrapper around one of these, and indeed RC/Funge-98 uses send(). Given that it seems to be unspecified I'd allow it; maybe the programmer knows something we don't, at least on the specific
16:25:55 <Deewiant> platform he's using, and expects a certain result.
16:26:33 <Vorpal> Deewiant, well it causes uninitialized memory in cfunge
16:26:49 <Vorpal> And the easiest way to fix it is to check for 1 or more rather than 0 or more
16:26:50 <Deewiant> If the "unspecified" means "error out" on the execution platform then your usual error checking should catch that and reverse the IP as usual.
16:27:49 <Vorpal> Oh and I use send() as well
16:28:20 <b_jonas> Deewiant: that exception is probably there because some packet-based sockets or devices could conceivably allow sending zero-length sockets, even though udp in particular doesn't allow that
16:30:27 <Vorpal> zero length packets, not sockets
16:30:31 <Vorpal> But yeah probably
16:30:33 <b_jonas> yes, sorry
16:31:01 <Deewiant> Vorpal: So send(some fd, null, 0, 0) is problematic, or what?
16:32:39 <Vorpal> Deewiant, well, first of all, I end up calling malloc(0), which is also implementation defined. On Linux that will in fact return a pointer (to 1 byte). Then I copy 0 bytes into that buffer from funge space. Which I then send with length 0.
16:32:58 <Vorpal> On some systems it will error out because malloc(0) can return NULL
16:33:18 <Deewiant> What will error out?
16:33:22 <Deewiant> Copying 0 bytes out of NULL should be fine
16:33:48 <Vorpal> Well, I check malloc return value. So it will error out because I check for successful allocation
16:34:11 <Deewiant> Well you should check it only if len > 0
16:35:34 <Vorpal> Hm send() with length 0 is not even documented
16:35:47 <Vorpal> So that seems like undefined behaviour, not just implementation defined.
16:37:05 <Deewiant> On Windows it's ok:
16:37:07 <Deewiant> Calling send with a len parameter of zero is permissible and will be treated by implementations as successful. In such cases, send will return zero as a valid value. For message-oriented sockets, a zero-length transport datagram is sent.
16:38:05 -!- tswett has set topic: oerjan doesn't hold much with that idea | but often spelled correctly. | https://dl.dropboxusercontent.com/u/2023808/wisdom.pdf http://codu.org/logs/_esoteric/ http://tunes.org/~nef/logs/esoteric/.
16:39:03 <Deewiant> https://bugzilla.kernel.org/show_bug.cgi?id=5731 is a bug about write() not writing a zero-length packet
16:39:34 <Vorpal> Deewiant, cfunge doesn't support native Windows anyway, so that seems irrelevant
16:40:26 <Deewiant> I'm just pointing out examples where this works or is expected to work
16:41:19 <Vorpal> Hm
16:41:27 <Vorpal> Makes sense
16:41:39 -!- nys has joined.
16:41:56 <Deewiant> You might be able to get away with not actually calling send() but not erroring either, if you want to be difficult about it
16:42:24 <Vorpal> Hah
16:45:39 <Vorpal> Deewiant, what about the buffer in this case though?
16:47:54 <Deewiant> What about it?
16:49:09 <Vorpal> Can it be null in this case?
16:50:18 <Deewiant> I don't see why not but I'd at least try it on Linux first
16:50:27 <Vorpal> Right
16:51:08 <Deewiant> Or check the source code of some libcs, etc
16:52:20 <b_jonas> who invents all these hundreds of crazy particles?
16:52:27 <b_jonas> um, sorry, wrong channel
16:53:38 <Vorpal> Deewiant, what do you use for randomness in CCBI(2) btw?
16:53:57 -!- AndoDaan has quit (Read error: Connection reset by peer).
16:54:21 -!- AndoDaan has joined.
16:54:24 <Deewiant> Vorpal: Re. Coverity, did you do the whole signup process and whatnot that they at least used to require, or do you have (or is there nowadays) some easier way to access it
16:55:23 <Vorpal> Deewiant, well I had to login with my github login, add the project and provide some info about it, including an indication that I was related to the project in some way.
16:55:27 <Deewiant> Looks like Mersenne Twister for randomness; I actually thought it was KISS
16:55:30 <Vorpal> Then they had to verify it
16:55:39 <Vorpal> Which took a couple of days, probably due to the holidays
16:55:56 <Deewiant> So in short it's still a hassle, ok. :-)
16:55:57 <Vorpal> Deewiant, it only supports C/C++, Java and C# though
16:56:08 <Vorpal> So CCBI won't have much use for it
16:56:12 <Deewiant> Oh, they have C#, didn't know
16:56:17 <Deewiant> I thought it was only C, C++, Java
16:56:18 <Vorpal> Apparently
16:56:32 <Vorpal> Maybe it is new? Who knows
16:56:40 <Deewiant> But yeah, CCBI is pretty much frozen anyway, just wondering
16:56:51 <Vorpal> Deewiant, Anyway, KISS? As in keep it simple stupid?
16:57:04 <Vorpal> Meaning random() from the standard library
16:57:17 <Vorpal> Or is KISS a separate badly named algorithm?
16:58:04 <Vorpal> Coverity complains that I use random(). So that was why I was wondering
16:58:17 <Vorpal> In other words: don't use cfunge to implement SSL?
16:58:42 <Deewiant> Can't find a good source for it but it's a different generator, one of Marsaglia's
16:59:12 <Deewiant> I ran both CCBI and cfunge through the dieharder tests at some point and cfunge got pretty poor results, random() would explain that
17:01:12 <Vorpal> Heh
17:01:26 <Vorpal> Deewiant, ? is even random() % 4 iirc
17:02:25 <Deewiant> The range of random() is probably a power of two so that % is probably fine
17:04:20 <Vorpal> 17 defects in total. Quite a few edge cases (mostly related to improper error handling, such as not freeing memory when the second of a series of malloc fails or similar). No really big issues for normal usage though. Also 4 false positives (all "high impact"). Plus 3 instances of random()
17:05:09 <Vorpal> Deewiant, the random() % n in FIXP D is probably worse
17:05:09 <Deewiant> Run the clang static analyzer and see if it catches the same ones (though I doubt it complains about random())
17:05:18 <Deewiant> Yeah that's not nice
17:05:24 <Vorpal> I have used clang static analyzer in the past
17:06:07 <Vorpal> In my experience it finds rather long and complicated chains of events mostly after the first time I used it. Most of them being impossible.
17:07:20 <Vorpal> Deewiant, but I don't have a modern llvm version on this machine I think, I might try it later though, but it should be clean from real defects at least as of clang a year or so ago
17:08:44 <Deewiant> Odd if it misses all of those "missing free" cases
17:08:46 <Vorpal> Hm also this is annoying, some weird issues in an implementation of strstr (I have copies of the glibc str* functions I need for funge-space sizes)
17:08:50 <Deewiant> But yeah it has false positives of its own
17:09:21 <Vorpal> Well, it did back then at least. Coverity also missed at least one. Though perhaps it only report the first issue of a kind in a given function?
17:09:37 <Deewiant> Could be
17:11:31 <tswett> > iterate (\x -> ((x ^ 2) `div` 100) `mod` 10000) 7835
17:11:32 <lambdabot> [7835,3872,9923,4659,7062,8718,35,12,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0...
17:12:21 <Vorpal> Hm?
17:13:13 <tswett> > iterate (\x -> ((x ^ 2) `div` 100) `mod` 10000) 7838
17:13:14 <lambdabot> [7838,4342,8529,7438,3238,4846,4837,3965,7212,129,166,275,756,5715,6612,7185...
17:13:22 <tswett> There we go.
17:14:26 <Vorpal> What is that sequence about?
17:14:57 <tswett> Middle-square pseudorandom numbers.
17:15:29 <Vorpal> Ah
17:16:35 <tswett> > iterate (msq 100) 1234
17:16:37 <lambdabot> [1234,5227,3215,3362,3030,1809,2724,4201,6484,422,1780,1684,8358,8561,2907,4...
17:16:45 <tswett> > iterate (msq 10000) 12345678
17:16:46 <lambdabot> [12345678,41576527,60759738,74576182,60692169,53937792,28540583,56487797,871...
17:16:53 <tswett> And so on and so forth.
17:19:07 <Vorpal> Deewiant, I did find an interesting issue actually, but again, if IP duplication fails, which requires OOM to happen.
17:21:15 <Deewiant> Yeah it's too bad that never actually happens; all that code just waiting to be executed
17:21:53 <Vorpal> Hah
17:22:01 <Vorpal> Deewiant, what should happen when t fails hm?
17:22:16 <Vorpal> The parent can hardly be reversed, that is undetectable from the child
17:22:32 <Deewiant> Reverse the parent but don't create a child
17:22:44 <Vorpal> Really?
17:22:48 <Deewiant> Why not?
17:22:58 <Vorpal> Well okay
17:23:01 <Deewiant> The program should notice that one of its threads is missing :-P
17:23:10 <Vorpal> Not like that code will ever be hit anyway
17:28:20 -!- nortti has changed nick to lawspeaker.
17:28:43 <Vorpal> Deewiant, not sure what to do about randomness though... Is it worth using urandom if that exists or something like that?
17:28:45 <Vorpal> Hm
17:29:12 -!- bb010g has joined.
17:29:20 -!- lawspeaker has changed nick to nortti.
17:29:39 <Deewiant> /dev/urandom is a bit slow if you don't need a CSPRNG
17:29:57 <Vorpal> True
17:30:34 <Vorpal> So what good options are there hm? Adding in another external library seems annoying
17:30:57 <Vorpal> And I don't know what algorithms are good
17:31:37 <Deewiant> I used to have the mersenne twister just rolled in as one file (since then it appeared in the standard library of the time)
17:31:46 <Deewiant> Most RNG's aren't that big, you can just drop them in
17:31:58 -!- myndzi has quit (Quit: .).
17:32:33 -!- myndzi has joined.
17:33:36 <Deewiant> E.g. xorshift* is quite good and something like 10 lines: https://en.wikipedia.org/wiki/Xorshift#Variations
17:33:50 <Vorpal> Why doesn't random() in libc use it then?
17:35:53 -!- myndzi has quit (Client Quit).
17:35:56 -!- myndzl has joined.
17:36:02 <Deewiant> man 3p random suggests that a specific algorithm is required
17:37:22 -!- myndzl has quit (Client Quit).
17:37:32 -!- myndzi has joined.
17:37:35 <Deewiant> Oh and there's arc4random in libbsd, which is good
17:37:52 <elliott> just use /dev/random and fuck everything
17:38:12 <Deewiant> But it's also a CSPRNG, I don't know how it compares to /dev/urandom in speed
17:38:45 <Vorpal> Ah
17:40:59 <Vorpal> Deewiant, Well, libbsd is not universal (cfunge does optionally use strlcpy/strlcat from it, if not found it uses it's own copy of those instead)
17:41:26 <Deewiant> Yes but you're allowed to depend on things :-P
17:41:52 -!- nortti has changed nick to lawspeaker.
17:42:01 -!- lawspeaker has changed nick to nortti.
17:42:11 -!- myndzi has quit (Client Quit).
17:42:29 -!- myndzi has joined.
17:42:31 -!- myndzi has quit (Remote host closed the connection).
17:42:40 <Vorpal> Yes, but no reason to do it if I don't need to. Anyway I want a fast algorithm
17:42:56 <Vorpal> Mersenne twister (while not a CSPRNG) is fast isn't it?
17:43:07 <Vorpal> and that xor thing
17:43:39 -!- myndzi has joined.
17:43:51 <elliott> Deewiant: it's fast enough that openbsd could make random() use it
17:44:55 <Deewiant> Yeah sure, /dev/random on Linux is the only thing that's actually "slow" in some absolute sense
17:45:08 <elliott> oh this is cfunge we're talking about :P
17:45:15 <elliott> better use xorshift for the speeeeeeeed
17:45:51 <Deewiant> /dev/urandom pushes some 17 MiB/s on this box and how likely is that to bottleneck even a randomness-heavy Funge program
17:45:52 <Vorpal> Hm arc4random doesn't allow initializing with a fixed seed to cause a repeat?
17:46:46 <Vorpal> That is annoying, since I use that feature for fuzz testing (to ensure I test the same program when I run it normally and then under valgrind)
17:46:48 <elliott> Deewiant: I guess if it doesn't slow down mycology or fungot he won't care
17:46:48 <fungot> elliott: you probably want anyway) to find where the code is not. it just means that if your program uses them to debug a hq9+ program if he can't help you
17:47:12 <Vorpal> elliott, hah
17:47:14 <Deewiant> Vorpal: You need to provide a dummy /dev/urandom for arc4random_stir :-P
17:47:22 <elliott> a dummy getentropy too
17:47:24 <elliott> if it's using that
17:47:27 <elliott> which I hope it is
17:47:39 <Vorpal> Deewiant, that sounds a lot more annoying than #define FUZZ_TESTING causing srandom() to use a static value
17:47:43 <boily> @metar CYQB
17:47:44 <lambdabot> CYQB 301700Z 25012G17KT 25SM FEW040 FEW170 M17/M24 A3033 RMK SC1AC1 AC TR SLP277
17:47:53 <Deewiant> elliott: The manpage just says "arc4random_stir() function reads data from /dev/urandom"
17:47:57 <elliott> (it probably even calls it directly sine I don't think there's any libc wrapper yet)
17:47:58 <Vorpal> elliott, is that a system call? I don't have a man page for it
17:48:11 <elliott> Deewiant: yeah but the openbsd people wanted getentropy added specifically I think
17:48:14 <elliott> at least, it comes from openbsd
17:48:15 <Deewiant> Vorpal: It's a rather recently added syscall
17:48:23 <Deewiant> Depending on your kernel you might not have it yet
17:48:25 <Vorpal> Oh that thing
17:48:28 <Vorpal> wasn't it openssl?
17:48:33 <elliott> Vorpal: it's /dev/urandom that works in a chroot etc. and doesn't use an fd and can block if the entropy pool hasn't been filled yet
17:48:35 <Vorpal> 3.13, who knows
17:48:46 <elliott> (not the same as /dev/random, /dev/random starts blocking again for ~no reason even once it has entropy)
17:48:47 <Deewiant> Vorpal: Re. fuzz testing you can of course define your randomness function to use a different RNG when fuzzing
17:49:31 <Vorpal> Deewiant, well yeah that works I guess, just revert to the old random() with fixed srandom() in that case
17:49:48 <Deewiant> elliott: TBH I don't see why they didn't fix /dev/random instead
17:50:27 -!- AndoDaan has quit (Quit: bbl).
17:50:31 <elliott> Deewiant: that still doesn't work inside chroots (think containerisation) and uses an fd
17:50:42 <Vorpal> Deewiant, that could be missing in a chroot, or you could have used up all your file descriptors
17:50:46 <elliott> there are actual cases of programs falling back to bad entropy when they run out of fds that openbsd ran into IIRC
17:51:11 <elliott> "bad entropy" is one of those "bad Xs" that means "not X"
17:51:13 <Deewiant> chroots could just populate their /dev appropriately... but yeah the fd issue is a good point
17:51:37 <elliott> also it's faster I think?
17:51:43 <elliott> since it skips a lot of overhead
17:51:51 <Deewiant> Yeah it should be
17:51:58 <elliott> I mean it's not like linux is exactly a paragon of syscall minimalism / everything is a file
17:52:03 <Vorpal> Oh god, cmake I hate you. Never again will I use cmake for a project.
17:52:05 <elliott> so they might as well just provide it this way
17:52:18 <Deewiant> Vorpal: What's a good alternative?
17:52:26 <Vorpal> Deewiant, well that is the issue, there isn't one
17:52:30 <Deewiant> elliott: I still wonder about my question though, just without the "instead"
17:52:38 <Vorpal> Deewiant, autoconf + tup maybe?
17:52:51 <Deewiant> Vorpal: auto* is not a good alternative in my mind :-P
17:53:06 <Vorpal> Deewiant, well it is easier to do some of the stuff I'm doing with that actually.
17:53:07 <elliott> Deewiant: I don't know. I guess whoever's in charge of /dev/random doesn't understand information theory?
17:53:32 <elliott> Deewiant: it's probably easier to keep it broken and hope everyone forgets about it than to force programs to check whether /dev/random is okay or not
17:53:52 <Deewiant> elliott: I think it's pretty clear that wasn't the case originally but by now and especially with getentropy you'd think something would change...
17:54:06 <Deewiant> Er, was the case* that that person didn't understand
17:54:08 <Vorpal> elliott, Why did it block even when there is entropy btw?
17:54:22 <elliott> Vorpal: because you can "run out of entropy" (you can't)
17:54:25 <Deewiant> elliott: I'd still fix it but call it deprecated, there are programs that read from only it
17:54:47 <Deewiant> Although maybe all the major ones are switching to getentropy as soon as it's available
17:54:58 <elliott> Vorpal: (I've seen that analogised as "running out of key" when encoding a lot of messages with a stream cipher)
17:55:36 <Vorpal> elliott, didn't it use entropy to seed a generator? Or did it just return the entropy directly as the random data?
17:55:43 <Vorpal> I guess the latter case could break stuff
17:55:46 <elliott> it feeds it through a CSPRNG yes
17:56:08 <Vorpal> Then you can't run out as far as I understand indeed (though I'm no expert in this area)
17:56:09 <elliott> it even keeps adding entropy later, which is harmless and sort of very minorly good but not really necessary at all
17:56:21 <elliott> it's just its entropy estimate goes down when you read from /dev/random
17:56:23 <elliott> for some reason
17:56:42 <Deewiant> Vorpal: http://www.2uo.de/myths-about-urandom/structure-no.png
17:56:54 <elliott> the problem with /dev/urandom is that it doesn't block when you *do* want it to (at boot, before there's a reasonable (~128 bits) amount of entropy)
17:57:11 <elliott> but /dev/random blocks after that too
17:57:25 <elliott> on e.g. FreeBSD, /dev/{u,}random are the same and block at boot and never otherwise
17:57:33 <elliott> linux will never do that though because backwards compatibility >_<
17:57:42 <Vorpal> Heh
17:58:18 <Vorpal> Deewiant, that looks like it sometimes just returns the entropy pool data raw?
17:58:19 <Deewiant> Hmm, alias /dev/{u,}random to sockets that talk to /dev/random on a FreeBSD box?
17:58:26 <Vorpal> Deewiant, hah
17:58:59 <elliott> /dev/random does go through the CSPRNG do, or at least so I've heard... if that diagram suggests otherwise I'd be inclined to not believe it
17:59:04 <elliott> *too
17:59:09 <Deewiant> Vorpal: Oh whoops wrong one, http://www.2uo.de/myths-about-urandom/structure-yes.png
17:59:29 <Deewiant> The one I linked earlier was the "what you might think" version
18:00:01 <elliott> nice
18:00:02 <Vorpal> Hm
18:00:08 <elliott> deliberately misleading diagram with no big red warning sign on it
18:00:19 <elliott> how many reddit/HN comments has it been linked from to support an argument
18:00:26 <Deewiant> It has "no" in the filename, you'd think that's enough
18:01:07 <Deewiant> It says "[a]n incorrect view" almost immediately before it on the HTML (in red, even) but yes, not in the image itself
18:01:38 <elliott> I feel like if you show people the wrong version first it's the one they'll remember...
18:02:24 <Deewiant> Maybe
18:03:58 -!- Sprocklem has quit (Ping timeout: 244 seconds).
18:05:26 <Jafet> "Counting entropy"
18:05:53 <elliott> there's a little gnome in the kernel who pushes a button whenever it sees a bit that surprises it <_<
18:06:36 <Jafet> I really, really don't want gnome in the kernel
18:20:33 <Vorpal> Jafet, don't worry, it will be systemd instead
18:24:01 <Vorpal> Deewiant, an issue with arc4random_uniform is that it is 32-bit, cfunge can have 64-bit cells.
18:25:02 <Vorpal> What would a good way to generate a 64-bit random value with arc4random be? For the case of whole bytes, arc4random_buf could be used.
18:25:14 <Vorpal> But I don't know for the case of [0,max]
18:25:26 <Vorpal> elliott, ^
18:25:28 <Jafet> arc4 is 8-bit
18:25:35 <Vorpal> u_int32_t
18:25:35 <Vorpal> arc4random_uniform(u_int32_t upper_bound);
18:25:40 <Vorpal> Doesn't look like it?
18:25:50 <Vorpal> Or the man page is lying
18:25:57 <Jafet> I see
18:26:21 <Jafet> You can, of course, construct a 64-bit random in parts
18:29:04 <Vorpal> Jafet, what is a good way to do it though? For a specific upper bound between 2^32 and 2^64?
18:29:18 <Deewiant> Vorpal: Use arc4random_buf to generate 64 bits in one go?
18:29:22 <Vorpal> Sorry, for an arbitrary rather than specific
18:29:40 <Vorpal> Deewiant, But I don't want to do % after to limit it to an upper bound. I'm asking for that specific case.
18:30:00 <Vorpal> How do I best limit it to a a range [0,n] for any n
18:30:01 <Deewiant> Well if your upper bound fits in less bytes then pass a smaller length to arc4random_buf
18:30:09 <Deewiant> And then you'll have to use %
18:30:23 <Vorpal> Deewiant, and if my n is a number that isn't a power of 2?
18:30:26 <Jafet> I suspect that this arc4random_uniform uses rejection sampling
18:30:31 <Vorpal> Ah
18:30:49 <Vorpal> So it takes an indeterminate amount of time perhaps.
18:30:58 <Vorpal> arc4random_uniform() will return a uniformly distributed random number less than upper_bound. arc4random_uniform() is recommended over construc‐
18:30:59 <Vorpal> tions like “arc4random() % upper_bound” as it avoids "modulo bias" when the upper bound is not a power of two.
18:31:02 <Deewiant> Vorpal: Then toss the result if it's in an uneven range
18:31:14 <Vorpal> Deewiant, fair enough
18:31:57 <Deewiant> (Is "rejection sampling" the fancy term for that?)
18:32:49 -!- adu has joined.
18:35:56 -!- dts|pokeball has joined.
18:36:49 <Jafet> If by "that" you mean rejection sampling, yes
18:37:56 <Jafet> You could just write a uint64_t version of http://svnweb.freebsd.org/base/head/lib/libc/gen/arc4random.c?view=markup#l270
18:38:58 <Jafet> I'm surprised that they actually allow an infinite loop there
18:39:14 <Deewiant> That's a clever min
18:39:52 <Jafet> (Or at least not-yet-known-to-be-finite, given that this is arc4 output.)
18:40:03 <Vorpal> Yeah that seems bad
18:40:19 <Vorpal> For cfunge it won't matter, but imagine what that will do to a real time system
18:40:28 <Vorpal> But then again I doubt freebsd is a real time OS anyway
18:41:24 <Jafet> I'm not sure if the kernel uses that function
18:41:51 <Vorpal> I think OpenBSD does at least
18:41:58 <Vorpal> Or maybe not that function, but arc4
18:42:07 <Vorpal> Pretty sure /dev/random on OpenBSD is arc4-based
18:49:37 -!- rade has quit (Ping timeout: 255 seconds).
19:04:49 -!- kallisti has quit (Ping timeout: 245 seconds).
19:14:17 -!- Guest36924 has joined.
19:15:11 <Guest36924> hello
19:16:21 -!- Guest36924 has left.
19:19:01 -!- nycs has joined.
19:20:39 -!- `^_^v has quit (Ping timeout: 245 seconds).
19:29:41 -!- shikhin_ has joined.
19:32:08 -!- rade has joined.
19:32:50 -!- shikhin has quit (Ping timeout: 250 seconds).
19:55:12 -!- shikhin_ has changed nick to shkhn.
19:56:50 -!- shkhn has changed nick to shikhin.
20:06:10 -!- nycs has quit (Quit: This computer has gone to sleep).
20:09:55 -!- nycs has joined.
20:44:05 -!- MoALTz has joined.
20:51:16 -!- oerjan has joined.
20:54:37 -!- augur has quit (Ping timeout: 240 seconds).
20:59:12 -!- augur has joined.
21:01:23 -!- augur_ has joined.
21:03:24 -!- nycs has changed nick to `^_^v.
21:05:04 -!- augur has quit (Ping timeout: 255 seconds).
21:12:00 -!- Patashu has joined.
21:26:55 -!- oerjan has quit (Quit: ZZZZ).
21:42:00 -!- zzo38 has joined.
21:48:30 -!- _2_Leenz2 has joined.
21:48:34 <_2_Leenz2> Haii
21:48:37 <Vorpal> <Jafet> You could just write a uint64_t version of http://svnweb.freebsd.org/base/head/lib/libc/gen/arc4random.c?view=markup#l270 <-- that is rather interesting code
21:48:47 <Vorpal> I wonder why it works actually
21:48:52 <Vorpal> Will have to look into that
21:49:00 <_2_Leenz2> Hai :D
21:49:44 <Vorpal> Jafet, specifically the claim that p > 0.5
21:49:51 -!- _2_Leenz2 has quit (Client Quit).
22:06:56 <int-e> Vorpal: simple math. if upper_bound <= 2^31 then min < 2^31 because min < upper_bound; otherwise, min < 2^31 becaues 2^32-upper_bound < 2^31.
22:07:45 <int-e> so (2^32-min) / 2^32 > 2^31/2^32 = 0.5
22:08:17 <Vorpal> Hm, that will scale to 64-bit I presume? I think it is way too late for me to implement this given that I can't figure this out
22:09:02 <int-e> sure.
22:09:12 <Vorpal> Just replace u_int32_t, and then use arc4random_buf(&my64bitint, 2) instead of arc4random()
22:09:53 <Vorpal> Deewiant, btw did you test that randomness thing with efunge too? If so, how did it fair?
22:09:56 <int-e> looks plausible (didn't check the API)
22:10:14 <Deewiant> Vorpal: Nah, only CCBI and cfunge
22:10:30 -!- Phantom_Hoover has quit (Ping timeout: 265 seconds).
22:10:38 <Vorpal> Deewiant, Do you still have the code for it?
22:11:01 -!- Phantom_Hoover has joined.
22:11:46 <Deewiant> Not sure but it would be pretty easy to recreate anyway
22:12:40 <Deewiant> $ cat rng.b98
22:12:43 <Deewiant> 4v > 0v >$'@*\88+*+\4*++,
22:12:44 <Deewiant> >#v? 1>\1-:!#^_
22:12:47 <Deewiant> > 2^
22:12:48 <Deewiant> > 3^
22:12:51 <Deewiant> I think that's it
22:13:02 <Deewiant> Seems to generate something pretty random-looking at least
22:13:27 <Vorpal> What test did you use did you say?
22:13:32 <Deewiant> dieharder
22:13:48 <Deewiant> http://www.phy.duke.edu/~rgb/General/dieharder.php
22:15:42 <HackEgo> [wiki] [[Budget]] http://esolangs.org/w/index.php?diff=41561&oldid=41559 * BCompton * (+10) Stub
22:16:28 -!- adu has quit (Quit: adu).
22:53:22 <Vorpal> In file included from ../../src/prng.c:33:0:
22:53:22 <Vorpal> void arc4random_addrandom(u_char *dat, int datlen);
22:53:25 <Vorpal> Massive fail :P
22:53:30 <Vorpal> err
22:53:33 <Vorpal> /usr/include/bsd/stdlib.h:52:27: error: unknown type name ‘u_char’
22:53:36 <Vorpal> That bit
22:54:23 -!- ^v has joined.
22:55:35 <Vorpal> Can't find a header with it either...
22:56:29 -!- tswett has quit (Ping timeout: 245 seconds).
23:03:42 -!- `^_^v has quit (Quit: This computer has gone to sleep).
23:04:47 -!- ^v has quit (Quit: Leaving).
23:07:06 -!- mihow has quit (Quit: mihow).
23:11:13 <Vorpal> Deewiant, arc4random is indeed very fast, I did some quick tests with it. It is slightly slower than the built in random() % 4
23:11:31 <Vorpal> I basically did "build/release/cfunge examples/prng.b98 | wc -c & sleep 5; killall cfunge; sleep 0.1; echo" a few times over and averaged the results
23:12:30 <Vorpal> 1548288.5 for arc4 (with 4 passed to proper modulo handling function) vs 1617920.9 for random() % 4
23:12:42 <Vorpal> That is not too bad at all
23:28:56 -!- adu has joined.
23:33:02 <zzo38> When trying to edit c2 wiki I get "Suspicious source (tor.ahbl.org)". Do you know what that is?
23:34:25 <Vorpal> zzo38, Oh, fun... I heard about this. Basically tor.ahbl.org *was* a DNS blacklist for Tor exit nodes. But it shut down recently. The result is that it returns that all IPs are exit nodes...
23:34:40 <Vorpal> You need to contact the admin of that wiki I suspect
23:38:38 <zzo38> SQLite uses ARCFOUR for random number generators. What do the numbers 1548288.5 and 1617920.9 mean exactly?
23:39:18 <Vorpal> zzo38, Should be obvious from the command line?
23:39:29 <Vorpal> build/release/cfunge examples/prng.b98 | wc -c & sleep 5; killall cfunge; sleep 0.1; echo
23:39:55 <Vorpal> It is the average of 5 runs of that
23:40:19 <zzo38> You didn't tell me it is the average.
23:40:22 <Vorpal> Highly unscientific measurement of course, but good enough to show that the performance is only slightly worse
23:40:29 <Vorpal> zzo38, I did
23:40:31 <Vorpal> <Vorpal> I basically did "build/release/cfunge examples/prng.b98 | wc -c & sleep 5; killall cfunge; sleep 0.1; echo" a few times over and averaged the results
23:40:37 <zzo38> O, OK
23:40:54 <Vorpal> I didn't tell you it was 5 times
23:41:21 <zzo38> The average of what, the output of wc -c or what, and what does prng.b98 do exactly?
23:42:08 <Vorpal> zzo38, that is the program Deewiant provided earlier
23:42:24 <zzo38> OK
23:42:26 <Vorpal> Just a few lines above
23:42:39 <Vorpal> zzo38, And yes the output of wc -c.
23:42:44 <Vorpal> What else is there?
23:42:47 <Vorpal> The job ID?!
23:42:53 <int-e> Vorpal: funny, I'd always do it the other way around; output a fixed number of characters and time that. (either by putting a loop in the program or by using head -c)
23:43:02 <zzo38> O, so is it checking how many characters it can output in 5 seconds?
23:43:21 <Vorpal> int-e, well that works too. Probably better too. Didn't want to rewrite the program though
23:43:34 <Vorpal> head -c would have worked yes
23:43:55 <zzo38> int-e: That is what confused me too, although I would have done yet another different way
23:44:04 <Vorpal> int-e, except what does that do with full buffering? Pretty sure full buffering is going on
23:44:14 <Vorpal> Err that was badly worded
23:44:57 <zzo38> Put the timing in the program itself or time how many times you can execute the program or something like that, is what I have done in my own cases
23:45:07 <int-e> Vorpal: well, are you sure your program flushes its buffer when its killed? it comes down to that... in any case I'd make sure the count is not too small
23:45:22 <zzo38> That is mainly the confusion I have had with it
23:45:47 <zzo38> Although it is obvious what you have done now, I just didn't notice quite at first
23:46:03 <Vorpal> int-e, well if it didn't I should get various multiples of fixed sizes every time, no?
23:46:32 <int-e> Vorpal: perhaps.
23:48:12 <Vorpal> Deewiant, dieharder does not run fast :/
23:50:31 <zzo38> If the range of the random numbers aren't a power of two then you need to do something else; what I have done in such case is to first take the number of bits needed, and then if the number is too big try again until it is not too big.
23:53:27 -!- pallokolmio has joined.
23:53:32 <zzo38> What is done by the card DIGGER in Pokemon cards is basically an optimization of this algorithm for the case: if random(0 to 2) < 2 then hits your own card else hits opponent's card. Since the bit1 is 0 then it is known true you needn't read the next bit.
←2014-12-29 2014-12-30 2014-12-31→ ↑2014 ↑all