00:04:12 -!- olsner has quit ("Leaving"). 00:10:46 MRyaaaaaaaaaaaaaaaaaaa 00:10:53 that is alll 00:12:13 -!- timotiis_ has quit ("leaving"). 00:14:20 * pikhq is a cruel bastard. . . 00:14:43 In the FRC: should you become temporally disjoint from the bus, you should calculate G while waiting for the bus to find you again. 00:14:46 >:D 00:15:09 shall i dare to ask what G is? 00:15:20 indeed i shall. 00:15:23 what is G? 00:15:30 Graham's number. 00:15:38 oops 00:15:52 * oerjan was hoping for the gravitational constant 00:16:09 Sorry, but I like the up-arrow notation. :p 00:20:23 -!- ais523_non-admin has quit ("Bye!"). 00:20:42 knuths arrays are basically the hyper operator? 00:21:14 oklokok: Pretty much. 00:21:19 Different notation for the same. 00:21:33 i invented the hyper oerator as a kid, thought it was a new idea until like last year :P 00:21:36 *operator 00:22:07 It's a fairly trivial concept to *grasp*. 00:22:09 i guess there's not much to invent 00:22:14 But a bit harder to use *usefully*. ;) 00:22:15 / grasp 00:22:48 well, i was mainly trying to find the hyper operations for reals as well 00:22:53 * pikhq should have done A(G, G). . . 00:23:03 but it seems it hasn't been done yet in a meaningful way 00:23:04 You were. . . Trying to extend hyper to the reals? 00:23:08 Bastard. 00:23:12 yeah, hasn't everyone 00:23:13 :D 00:23:50 Not I. 00:23:57 But, then, I'm only in high school. ;) 00:23:57 "The family has not been extended from natural numbers to real numbers in general for n>3, due to nonassociativity in the "obvious" ways of doing it." 00:24:10 well, this was when i was in elementary school 00:24:12 i'm your age 00:24:15 Ah. 00:24:31 it's not like i was a super math genius or anything 00:24:43 i just have a lot of weird ideas 00:25:05 hmm 00:25:15 I'm only a *moderate* genius at math. ;p 00:25:30 heh 00:25:37 i'm not practical enough for math 00:25:46 requires perfection, unlike say programming 00:26:37 * pikhq wonders what the derivative of ^{x}e is. . . 00:26:44 what does that mean? 00:26:49 Tetration. 00:26:51 lambda x : e? 00:26:54 oh. 00:27:04 Or e\uparrow\uparrow x. 00:27:07 * pikhq is a LaTeX junky. 00:28:33 -!- Judofyr has quit (Read error: 104 (Connection reset by peer)). 00:29:09 -!- Judofyr has joined. 00:29:16 what's x^x? 00:29:18 umm 00:29:21 D(x^x) 00:29:55 well, x^f(x) really, then just extend that 00:30:07 oh, right 00:30:32 hmm, i think i should wait until i'm *not* watching something 00:30:42 i'm not good at multitasking really 00:31:21 umm 00:31:22 what 00:31:28 e up up x? 00:31:44 right, i misparsed you still 00:31:44 Not familiar with Knuth's up-arrow notation? 00:31:53 In it: e^x = e\uparrow x. 00:31:58 yeah 00:32:02 Ah. 00:34:08 i think i got it, not derivable :P 00:34:44 e upup x where x = real doesn't exist, right? 00:34:49 Sure it is! It's a smooth curve and everything. 00:35:01 http://en.wikipedia.org/wiki/Image:Real-tetration.png 00:35:06 ah. 00:35:19 that's a matter of definition then, lessee 00:35:40 hmm 00:35:44 Just because it's not derivable in terms of elementry functions does *not* make it not derivable. ;p 00:36:03 it cannot be derivable if it does not have a definition for reals 00:36:12 it seems it does, but where is it? 00:36:17 :P 00:36:38 e upup x. 00:36:49 What part of that says it's *not* defined on the reals? 00:37:01 what't e upup 0.5? 00:37:03 *what's 00:37:17 e^{1/4}. 00:37:27 I think. 00:37:48 Nope. 00:37:52 i doubt that 00:37:56 It's not. 00:38:07 That's e^{{1/2}^2}. :p 00:38:42 the fact you can possibly extend the array-notation definition using your intuition doesn't make it a real definition. 00:38:59 the array-notation only works for integers with the definition there 00:39:46 well 00:39:49 You're confusing e^^x and hyper(e, x, x). ;P 00:40:06 i am not 00:40:25 e^^x = e^e^...^e where e is there x times 00:40:41 if x isn't an integer, that makes no sense 00:40:42 Yes. What about that definition prevents e^^x from being defined on the reals? 00:40:58 what is e^^0.5? 00:41:30 you can definitely define it for reals, i'm just saying the page doesn't do that. 00:41:58 for instance, you can just define e^^x where x isn't an integer to be zero. 00:42:32 exponentiation does real exponents using the inverse operation 00:42:48 perhaps that could also be created for the array notation 00:43:32 i'm just saying i'm physically not seeing a definition for real arrow-exponent 00:43:41 hmm 00:43:47 have i been saying "array"? 00:43:49 Repeated multiplication doesn't define, say, e^0.5, yet it still exists as a real. 00:43:52 Yes. 00:44:05 pikhq: as i said, defined via the inverse for reals 00:44:07 -!- BMeph has joined. 00:44:22 because you can use the inverse function for the denominator of the exponent. 00:44:48 Having trouble finding an *exact* definition, but it's *about* 1.5. 00:44:57 and define reals to be the limit of doing that where the rational number representing the exponent ...gets closer to the real exponent 00:45:15 that doesn't help at all 00:45:24 you could define it in many ways 00:45:44 Likewise, you could define 1+1=50. I fail to see how that's relevant. 00:45:59 Blargh. 00:46:11 it's relevant in that if it doesn't have a definition, the derivative doesn't have a definition 00:46:18 That Wikipedia page says there's no commonly accepted solution to extended tetration to the reals. 00:46:26 thought so 00:46:59 but it could prolly be done using something like the inverse function way exponentiation uses, as i already said two times i guess 00:47:10 i'll look into that after this episode 00:47:23 Yeah, I think I like the super-logarithm solution. 00:47:54 super-logarithm solution? 00:48:03 exponentiation uses the other inverse :) 00:48:30 True. 00:48:48 The problem being: the super-logarithm on the reals is not defined, either. XD 00:48:55 the only obvious equation to start with would seem to be e^^(x+1) = e^(e^^x) 00:49:25 oerjan: doesn't help, we still need e^x where x in [0..1] 00:49:28 eh 00:49:32 e^^x 00:49:51 hm... 00:51:16 there might be one solution that was particularly nice in some way 00:52:30 Define it in terms of the square-super-root. ssrt(x) = e ^ {W(ln(x))}, where W is the inverse of f(w)=we^w. . . 00:52:43 (can't prove: Wikipedia claims it to be so) 00:54:32 :) 00:54:52 Anyways, that provides a fairly *elegant* extension to the reals. 00:54:56 oerjan: You agree? 00:55:07 i do, that's what i suggested right away 00:55:12 hmm 00:55:25 is there a nice way to compute w? 00:55:33 Taylor series. 00:55:39 myah 00:55:48 i'm too lazy to google, sry :P 00:55:56 The Wikipedia page gives some C source code for W(x). ;) 00:56:31 aye 00:56:58 -!- Corun has joined. 00:57:51 -!- pikhq has set topic: - From Brainfuck to extending tetration to the reals.. 01:00:24 -!- oerjan has quit ("Good night"). 01:00:30 nightie 01:00:31 s 01:21:34 -!- Judofyr has quit (Read error: 104 (Connection reset by peer)). 01:21:58 -!- Judofyr has joined. 01:33:01 -!- sebbu has quit ("@+"). 01:38:16 -!- calamari has joined. 01:39:15 pikhq: I was curious, so I got the free HTML version of the posix spec and convereted it to PDF.. thousands on pages.. wow 01:39:19 on->of 01:39:40 calamari: Wow. 01:40:01 But that's specifying the behavior of all of UNIX. . . 01:40:18 I think there's a hidden spec out there 01:40:19 Just my collection of *man pages* would probably cover a thousand pages. 01:40:26 undefined of course 01:40:41 "what's good enough to get gcc working with configure scripts?" 01:40:45 (info pages? Hell, that's probably got the POSIX spec in there two times over) 01:41:13 probably a lot less strenuous a goal 01:41:26 Of course. 01:41:51 btw you mentioned that porting gcc over wasn't a big deal.. what's the process? 01:41:51 You need a shell, make, gcc, and libc. 01:42:32 Assuming you use an executable format that GCC supports? Port libc. Compile a GCC cross-compiler. Use that to make a GCC native compiler. 01:42:45 The 'port libc' part is the hard one. 01:43:41 thus newlib 01:43:53 * pikhq can't wait to one day do uname -a and get 'i686-pc-mykernel-newlib' 01:44:10 oh so you're doing it for your regular pc? 01:44:17 Yeah. 01:44:23 I was hoping this was some custom system you built out of parts or such 01:44:26 Although my *regular* PC is actually x86_64. 01:44:36 That makes it a bit harder. 01:44:42 You then have to retarget GCC. 01:44:48 A royal pain. . . 01:44:49 yep 01:45:04 But at least GCC just does RTL->assembly. . . 01:45:12 (for the architecture-specific stuff, that is) 01:45:16 it'd be a new backend 01:45:30 and assembler 01:45:36 Well, yeah. 01:45:55 I'm mostly saying 'Thank god GCC has all the frontends go to the same language.' 01:46:06 yeah 01:52:49 -!- Corun has quit (Read error: 110 (Connection timed out)). 02:07:36 http://www.atmel.com/dyn/products/product_card.asp?part_id=3755 02:07:50 ARM, so gcc is ready to go 02:08:58 -!- oklokok has quit. 02:21:22 Anyone up for a seemingly np complete problem? 02:32:19 -!- Tritonio_ has joined. 02:39:38 -!- Sgeo has joined. 02:40:53 Deformative: Sure. 02:41:01 Just because its NP doesn't mean it can't be solved. 02:41:09 Just that it can't be solved efficiently. ;) 02:41:39 Oh hi all 02:43:10 pikhq: You have a block of memory, and a new order, some locations are duplicated, some are no longer used, but they refill the same block, design an algorithm to find the least number of movements needed. 02:43:54 So you have [a b c d e f] and it needs to be transformed to an arbitrary new order, for example: [a b e e f c] 02:44:14 You have access to extra space. 02:44:29 Sorting algorithm. Lower bound is O(n log n). 02:44:41 It is _not_ sorting. 02:44:49 'Some locations are duplicated' 02:44:53 Whaddya know. It's not. 02:45:12 some are no longer used 02:45:20 Why would you need the minimum amount of movements? 02:45:40 It is a compiler that needs to generate optimal code. 02:46:08 Sorting does not need to remain in the same memory block. 02:46:22 The thing is: you don't necessarily need to generate *optimal* code, if that's too hard to do. What you need to do is produce *pretty good* code. . . 02:46:31 Which is usually a much easier problem. 02:46:42 Less fun. 02:46:59 And besides: finding the lower bound of your movement algorithm there won't help because *you still don't have said movement algorithm*. ;) 02:47:24 Huh? 02:47:30 Reread that. 02:47:38 So, a more *useful* question is "How can I efficiently move things around like this: ..." 02:47:55 I need the least number of movements. 02:48:06 Why do you need that? 02:48:20 Because it stays in the same block... 02:48:29 What you're asking for is the lower-bound of the efficiency of an algorithm that does that. 02:48:38 What you need is the algorithm itself. 02:49:15 Just like asking "How many steps does it take to sort a list?" is useless when you actually want to sort. 02:49:18 The algorithm does not need to re-arange, the algorithm generates code that will re-arrange. 02:50:17 Which is not that much different, algorithmically. . . 02:50:37 Yeah it is. 02:50:51 I still have no clue why you need to know the efficiency of such an algorithm, but not the algorithm itself. 02:50:53 Because you can bruteforce until you find the algorithm that has the least movements. 02:50:54 ;) 02:51:03 Oh. 02:51:07 You're doing it wrong. 02:51:08 ;) 02:51:18 Or you are understanding me wrong. 02:52:01 I suspect, though, that you could trivially adapt a sorting algorithm to that. 02:53:44 Alright, a language privative is to convert [a b c d] to [a a b d] the code generated should not do the same ineffective algorithm every time, the compiler should do a lot of work once so that it has a perfect algorithm every time it is run. 02:53:48 Does that make sense? 02:55:14 Are those two orders always the same between calls to the same language primitive with the same argument? (that is, would "transform(abcd, aabd)" do the same thing every time?) 02:56:09 Yes. 02:57:14 Hmm. 02:57:16 And the only allowed operation of movement? 02:57:33 * pikhq is still tempted to say 'sorting algorithm'. . . XD 02:57:41 It is manipulating arguments. My language is capable of using the same memory block to keep args in for every function, but a function has many of the same args as the function that called it. 02:58:40 So lets say foo( a b c d) calls bar(a a b d) 02:58:41 Deformative: Is the only allowed operation is a[i] = a[j]? 02:58:44 The compiler should optimize that. 02:58:46 Doing it wrong. . . Use the C calling convention on your system of choice, for crissake. 02:58:56 Dude. 02:59:11 That would take the whole esoteric part out of it. 02:59:24 Is this for tail recursion? 02:59:25 cherez: I am trying to generate optimal asm. 02:59:44 If I ever did PEBBLE->assembly, I'd use the C calling convention. . . 02:59:48 And movl is really the only call that should be needed. 02:59:56 That doesn't remove the esotericness of language. . . 03:00:05 It just makes your *compiler* purely insane. 03:00:06 cherez: Sortof, not exactly. 03:00:13 pikhq: Indeed. 03:00:14 Your implementation doesn't have to be esoteric. ;) 03:00:21 cherez: The language does not have return values. 03:00:25 And therefor the stack does not change. 03:00:26 Well, if every operation must overwrite, it's only possible if it's the same output or no variables are dropped. 03:00:47 cherez: He allows temporary storage. 03:01:03 My language is purely continuations. 03:01:09 No returning, no stack frame. 03:01:16 Ah. 03:01:21 Well, the C calling convention won't work. 03:01:23 Carry on. 03:01:29 So reordering the stack then jmp? 03:01:33 So c calling is hardly even feasible, and possibly the least optimal thing imaginable. 03:01:35 :D 03:01:39 cherez: Yes 03:01:51 I need the compiler to generate perfect algorithms that reorder the stack. 03:02:18 Once again: you need the compiler to generate *good* algorithms that reorder the stack, not perfect ones. 03:02:23 :p 03:02:28 yes. 03:02:35 But perfect is preferable. 03:02:42 Brute forcing should be possible. 03:02:49 So it should be able to find the perfect algorithm. 03:03:20 I think that you're going to have a max of however many arguments you have to each function. . . 03:03:25 I *think*. 03:03:34 s/max/min/ 03:03:50 -!- Tritonio_ has quit (Remote closed the connection). 03:04:02 No, a b c d ~> a b c d has no movements 03:04:10 The compiler needs to be able to figure that out. 03:04:23 True. 03:04:43 But it's obvious that the compiled code is going to be doing that in O(1). . . 03:05:21 Genetic algorithm? Stable sorting algorithm? 03:05:52 It should be like O(0) 03:05:54 With O(n) temporary storage, I'd think this is probably O(n) or O(n^2). 03:05:59 It is JUST a goto then. 03:06:17 No movement. 03:06:33 Deformative: O(0) means that nothing happens at all. ;p 03:06:40 If anything at all is done, then it's O(1). 03:06:43 Nothing does happen. 03:06:45 Nothing does happen. 03:06:46 No movement? 03:06:52 No jump? 03:06:52 It happens at compile time, not runtime. 03:06:55 A jmp is damn well something. 03:06:57 Just 'hlt'? 03:07:04 You can try to convince your program counter otherwise. 03:07:13 Well, I suppose it depends on the processor architecture. 03:07:16 jmp is not part of the translation algorithm. 03:07:37 The compiler does not generate any translation if it is not needed. 03:07:43 So yes, O(0) 03:07:51 Remember, the indexes DO NOT CHANGE 03:08:11 indices 03:08:25 It is all compile time. 03:08:35 So the program directly knows what to do. 03:09:22 * pikhq tosses Deformative "The Art of Computer Programming" 03:09:28 Have fun; I'm sure you can figure it out. 03:09:36 Heh. 03:09:44 I told you it is a weird problem. 03:10:12 The hard part is showing a solution is optimal. 03:10:16 Because you are not trying to solve the problem exactly, you are trying to design the perfect solution given limitless time. 03:10:41 I can think of quite a few ways to generate good algorithms, but I can't think how you could prove optimal. 03:11:02 Least number of movl ? 03:11:38 I can't think of a polynomial way that I can prove has minimum movl. 03:12:08 If you cannot even count them, how do you generate the code? :) 03:12:52 Well, I can easily see how you could write an O(n) algorithm to produce O(n) movl. 03:13:05 That's certainly countable. 03:13:21 But I'm also certain there are more efficient ways. 03:13:50 Let me try to get some of my ideas into words. 03:14:02 First, make a list of indices no longer needed. 03:15:19 Next make a list of indices that are at the same place in beginning and result. 03:16:54 Then generate every possible combination to reach the result, and in each combination count the movls. 03:17:21 To generate the combinations, you need to check over every single index and see where they need to go. 03:17:29 Eh, and here is where I am stuck. 03:17:55 Data can be moved to places where that data is no longer needed without any negative effects. 03:18:19 So that is constant in all of the possible combinations. 03:18:26 cherez: See where I am trying to go? 03:18:52 That is roughly the NP algorithm I came up with. 03:19:18 I'd say it's probably NP-Complete, but I'm not certain. 03:20:11 Yes, I just need to find an algorithm for generating all possible combinations. 03:20:33 Even if it is npcomplete, it will generate perfect code, so that is not a problem if the algorithm I come up with is bad. 03:20:53 It also risks *never completing*. 03:21:06 NP-complete algorithms take quite a bit of time. ;) 03:22:02 An algorithm is easy. 03:22:47 Make a queue of operation sets, put an empty set of instructions on it. 03:23:55 While the operations do not produce the desired result, for every possible action that can be taken, add a new operation set that is the one retrieved, plus the new possible action. 03:24:19 Basically just enumerating the possible actions and executing them in sequence. 03:25:22 Hmm... 03:26:22 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 03:27:53 Actually, I think that might be polynomial. 03:28:36 A huge polynomial, but polynomial all the same. 03:30:18 No, that's nonpolynomial. 03:30:42 O(((n^2)^n)^2) 03:30:52 Jebus. 03:31:06 Oh well. 03:31:25 The generated apps should be ridiculously fast. 03:31:30 Let's see, at each step there are O(n^2) branches, and there are at most O(n) steps. 03:32:51 So O(n^(2n)) total branches. 03:33:01 Thus as many vertices. 03:33:14 The search is O(v^2) 03:34:33 -!- adu has joined. 03:35:25 Well, I have exams tomorrow, so I should sleep. 03:35:44 I'll be back tomorrow or such. 03:35:57 hi 04:31:19 -!- andydude has joined. 04:31:41 -!- adu has quit (Connection timed out). 04:32:17 -!- andydude has changed nick to adu. 05:06:01 -!- Sgeo has quit (Remote closed the connection). 05:21:09 -!- Judofyr has quit (Read error: 110 (Connection timed out)). 05:55:24 -!- adu has quit (Remote closed the connection). 05:57:29 -!- adu has joined. 06:08:06 -!- calamari has quit ("Leaving"). 06:34:30 -!- adu has quit (Remote closed the connection). 07:15:32 -!- Judofyr has joined. 07:37:15 -!- Judofyr has quit. 07:38:24 -!- BMeph has quit ("calls it a night"). 07:59:59 -!- clog has quit (ended). 08:00:00 -!- clog has joined. 09:31:32 -!- oerjan has joined. 11:55:53 err, wtf, looks like *code* memory is corrupted, anyway the output makes no sense 12:09:49 Deewiant, there? 12:09:51 BAD: the top of the stack after y isn't equal to what 1y pushes 12:09:55 wtf does that one mean 12:10:00 isn't it obvious 12:10:01 it does y 12:10:03 and then it does 1y 12:10:10 and it expects the top 2 elements of the stack to be the same 12:11:59 hm 12:12:23 I'm trying to fix my y and I end up with heap or stack corruption :/ 12:12:32 * AnMaster fixed that part at least 12:12:33 isn't it fun to program in C ;-) 12:13:01 aha got it 12:13:15 ==12040== Conditional jump or move depends on uninitialised value(s) 12:13:15 ==12040== at 0x40565E: ExecuteInstruction (interpreter.c:197) 12:13:15 ==12040== by 0x405EBB: interpreterMainLoop (interpreter.c:440) 12:13:15 ==12040== by 0x405FC7: interpreterRun (interpreter.c:472) 12:13:15 ==12040== by 0x404C9D: main (main.c:121) 12:13:22 yay for valgrind :D 12:13:54 yay for not initializing variables by default 12:15:02 -!- oerjan has quit ("leaving"). 12:15:32 Deewiant, well no that wasn't the issue 12:15:45 it was an array index off by one issue 12:15:52 or rather 12:15:55 yay for not having array bounds checks ;-) 12:15:56 of by a lot 12:16:06 basically unsigned int 12:16:17 wrapped, and ended up with 71634721834 or something like that 12:16:23 whatever you say, I can spin it into a pro-D anti-C argument if I try hard enough :-P 12:16:28 (gdb) print tmp->top - request 12:16:28 $1 = 18446744073709551610 12:16:29 :D 12:16:34 Deewiant, indeed I know 12:16:38 still I'm slightly faster 12:16:41 fortunately, I don't have to try very hard ;-) 12:16:43 my y is not optimized 12:17:16 I'm convinced by now that the only significant difference is the function pointers versus switch-case 12:17:42 consider the noOperation function that I showed yesterday :-P 12:17:50 it's called through a function pointer every time z is hit 12:17:54 even though it's just {} 12:18:29 yes, and that's just silly 12:18:31 and I suspect PaX does some sort of checking related to function pointers, which results in extra slowdown on your comp 12:18:39 I think the code is cleaner this way 12:18:41 Deewiant, I don't think it does 12:18:51 PaX just does NX and such 12:18:55 AnMaster: I read some docs on PaX design and they mention something to that effect 12:19:03 my gcc does stack smash protection though 12:19:10 -fstack-protector-all 12:19:15 likely slows things down 12:19:22 something like that, anyway 12:19:59 real 0m0.610s <-- debug build 12:21:53 Deewiant, btw for ccbi mycology list command line arguments backwards 12:22:03 is it supposed to do it that way? 12:22:24 say ./ccbi mycology.b98 some other things 12:22:35 That the command-line arguments were: [ "things" "other" "some" "mycology.b98" ] 12:22:46 hrmh 12:23:00 not sure whether that's a CCBI or Mycology issue ;-) 12:23:03 while mine do: That the command-line arguments were: [ "mycology.b98" "some" "other" "things" ] 12:23:16 might be CCBI then 12:23:17 lessee 12:23:24 Deewiant, so I want to know if I should push them in the other order or not 12:23:42 I got no idea what one is correct on this thing 12:23:46 well it's an interpretation issue I think 12:23:51 The first string is the name of the Funge source program being run. 12:23:59 does "first" here mean topmost or the one that was pushed first 12:24:38 Deewiant, good question 12:24:42 so it's a UNDEF? 12:24:49 I'd say so, yes 12:25:00 most of y is strictly speaking UNDEF 12:25:08 maybe mycology should test it in "Here's how your interpreter deals with some possibilities unmentioned in the specification..." section? 12:25:28 (if you got room there) 12:25:41 naw, because that's uncontrollable - would need the user to pass some command line args 12:25:48 ah true 12:25:51 and to be frank there's a lot of "possibilities unmentioned in the specification" 12:25:59