| --- Log opened Thu Sep 24 00:00:29 2009 |
| 00:09 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 00:25 | | Orthia [Orthianz@Nightstar-715cbcbb.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
| 00:42 | | You're now known as TheWatcher[T-2] |
| 00:44 | < Rhamphoryncus> | heh, for a moment I had a need for reduce in python |
| 00:44 | < Rhamphoryncus> | But I used an explicit loop instead.. which I immediately merged with the loop just before it |
| 00:46 | | Orthia [Orthianz@Nightstar-715cbcbb.xnet.co.nz] has joined #code |
| 00:47 | | You're now known as TheWatcher[zZzZ] |
| 00:50 | | * TheWatcher[zZzZ] ....s at http://www.sfgate.com/cgi-bin/article.cgi?f=/n/a/2009/09/23/national/w140345D22. DTL&tsp=1 |
| 00:50 | <@TheWatcher[zZzZ]> | 'A U.S. Census worker found hanged from a tree near a Kentucky cemetery had the word "fed" scrawled on his chest, a law enforcement official said Wednesday, and the FBI is investigating whether he was a victim of anti-government sentiment.' ... naw, y'think?! |
| 00:51 | <@TheWatcher[zZzZ]> | Oops, wrong channel >.> |
| 00:51 | < Finale> | nah |
| 00:52 | < Finale> | "Our job is to determine if there was foul play involved |
| 00:52 | < Finale> | he was hanged. no, it was a complete accident. |
| 01:06 | | Derakon[AFK] is now known as Derakon |
| 01:10 | < Rhamphoryncus> | You know what sucks? Having an off-by-one error in a length field, then having a matching off-by-one error in an assertion about said length field |
| 01:10 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: ] |
| 01:11 | < Finale> | O_o |
| 01:12 | < Rhamphoryncus> | assert 0 <= localoffset <= length |
| 01:13 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 01:13 | | mode/#code [+o Vornicus] by Reiver |
| 01:13 | < Rhamphoryncus> | Only off by one character |
| 01:34 | < Rhamphoryncus> | (should be 0 <= localoffset < length, if you're curious) |
| 01:50 | <@ToxicFrog> | Rhamphoryncus: can you do that in python? It doesn't turn into a comparison against a boolean? |
| 01:50 | <@ToxicFrog> | (if so, cool) |
| 01:54 | < Rhamphoryncus> | yeah, python chains those |
| 02:05 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has quit [[NS] Quit: Z?] |
| 02:06 | | Finale [c0cb88fe@Nightstar-14e5d099.mibbit.com] has quit [[NS] Quit: http://www.mibbit.com ajax IRC Client] |
| 02:15 | | Orthianz [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 02:17 | | Orthia [Orthianz@Nightstar-715cbcbb.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
| 02:31 | | * Vornicus wants to code! But is tired and headachey. |
| 03:00 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has quit [Client closed the connection] |
| 03:05 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
| 03:05 | | mode/#code [+o ToxicFrog] by Reiver |
| 03:11 | | Orthianz [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 03:22 | | Attilla [The.Attilla@FBC920.174237.BD7E36.E4F082] has quit [[NS] Quit: ] |
| 03:26 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 04:15 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 04:22 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 04:44 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 04:48 | | dmlandrum [dmlandrum__@Nightstar-15b281e2.sfldmi.ameritech.net] has quit [Ping timeout: 121 seconds] |
| 04:53 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 04:55 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 05:01 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 05:02 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: Leaving] |
| 05:04 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 05:04 | | mode/#code [+o Vornicus] by Reiver |
| 05:06 | | Syloqs_AFH [Syloq@NetworkAdministrator.Nightstar.Net] has quit [Connection reset by peer] |
| 05:06 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 05:14 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 05:30 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 05:45 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 06:00 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 06:09 | | thalass [thalass@Nightstar-b132a700.bigpond.net.au] has joined #code |
| 06:11 | < thalass> | ah now. Vim the bastard. I'm logged in as root, using vim to tinker with fstab so the second hard drive (/dev/sdb5) will be perminately mounted in /media/store. I add the line in, use the save command, and it says that the file already exists. So I override it with the w! command, and it seems fine. Then I go to quit and it claims nothing has been saved. Lo and behold it's true. |
| 06:11 | < thalass> | so it's not saving the changes I make |
| 06:12 | < Namegduf> | vim shouldn't have issues saving existing files. |
| 06:12 | < Namegduf> | Could you paste the message it gave? |
| 06:14 | < thalass> | (after using :w fstab) "E13: File exists (add ! to override) |
| 06:15 | < thalass> | (after using :w! fstab) ""fstab" 12L, 672C written" |
| 06:15 | < Namegduf> | Ah. |
| 06:15 | < Namegduf> | Why not just :w? |
| 06:15 | < thalass> | then after :q I get "E37: No write since last change (add ! to override) |
| 06:15 | < thalass> | ah you can do that? haha |
| 06:15 | | * thalass falls down |
| 06:16 | < Namegduf> | :w <filename> is designed to save a second copy of the file, so it doesn't count it as 'write since last change' on the main file itself, I'd guess. |
| 06:16 | < thalass> | hahaha I knew it would be something simple |
| 06:16 | < thalass> | I've only been using vim for... two hours or so |
| 06:16 | < Namegduf> | That's okay. |
| 06:16 | < Namegduf> | ":wq" is a quick 'save and quit' thing. |
| 06:16 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 06:17 | < thalass> | thanks |
| 06:19 | <@Derakon> | Actually, :x is "save and quit". |
| 06:20 | <@Derakon> | :wq also works, mind you. |
| 06:26 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 06:34 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 06:35 | | Chi [omegaboot@Nightstar-ac83c982.emhril.sbcglobal.net] has joined #code |
| 06:35 | | Alek [omegaboot@A2BA3E.D9488C.AC9733.17AB23] has quit [NickServ (GHOST command used by Chi)] |
| 06:35 | | Chi is now known as Alek |
| 06:44 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 06:50 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 06:50 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 06:55 | < Rhamphoryncus> | o.O never heard of :x |
| 06:56 | <@Derakon> | Heh. |
| 06:59 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #code |
| 07:05 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 07:08 | | Derakon is now known as Derakon[AFK] |
| 07:10 | | AnnoDomini [farkoff@Nightstar-403fac3e.adsl.tpnet.pl] has joined #code |
| 07:11 | | mode/#code [+o AnnoDomini] by Reiver |
| 07:17 | | Netsplit over, joins: thalass, @ToxicFrog, @Derakon[AFK], @jerith, @McMartin, ~Reiver, @Kazriko, GeekSoldier, @AnnoDomini, Namegduf |
| 07:17 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 07:17 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 07:17 | | mode/#code [+o Vornicus] by Reiver |
| --- Log closed Thu Sep 24 07:17:45 2009 |
| --- Log opened Thu Sep 24 07:17:52 2009 |
| 07:17 | | TheWatcher[zZzZ] [chris@Nightstar-b4529b0c.zen.co.uk] has joined #Code |
| 07:17 | | Irssi: #code: Total of 19 nicks [8 ops, 0 halfops, 0 voices, 11 normal] |
| 07:17 | | mode/#code [+o TheWatcher[zZzZ]] by Reiver |
| 07:18 | | Irssi: Join to #code was synced in 41 secs |
| 07:22 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #Code |
| 07:28 | | Vornicus is now known as Vornicus-Latens |
| 07:29 | | Vornicus-Latens [vorn@ServerAdministrator.Nightstar.Net] has quit [[NS] Quit: ] |
| 07:30 | | Vornicus [vorn@ServerAdministrator.Nightstar.Net] has joined #Code |
| 07:30 | | mode/#code [+o Vornicus] by Reiver |
| 07:30 | | Vornicus is now known as Vornicus-Latens |
| 07:34 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 07:49 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #Code |
| 07:54 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 08:10 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #Code |
| 08:53 | | You're now known as TheWatcher |
| 08:59 | | Rhamphoryncus [rhamph@Nightstar-a62bd960.abhsia.telus.net] has quit [Client exited] |
| 09:01 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 09:53 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has joined #Code |
| 09:54 | | Orthia [Orthianz@Nightstar-14e78741.xnet.co.nz] has quit [Connection reset by peer] |
| 10:21 | | Attilla [The.Attilla@FBC920.174237.BD7E36.E4F082] has joined #Code |
| 10:21 | | mode/#code [+o Attilla] by Reiver |
| 10:35 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has joined #Code |
| 11:13 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 11:41 | | * gnolam wanders off to best a pool table. |
| 13:01 | | Orthia [Orthianz@Nightstar-9576aa38.xnet.co.nz] has joined #Code |
| 13:26 | | * gnolam vomits hate all over quaternions. |
| 14:53 | | Orthianz [Orthianz@Nightstar-2a20c8f3.xnet.co.nz] has joined #Code |
| 14:55 | | Orthia [Orthianz@Nightstar-9576aa38.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
| 15:57 | | ASCII [none@Nightstar-a7d2ccfd.dyn.optonline.net] has joined #Code |
| 17:04 | | Rhamphoryncus [rhamph@Nightstar-a62bd960.abhsia.telus.net] has joined #Code |
| 17:08 | | Attilla [The.Attilla@FBC920.174237.BD7E36.E4F082] has quit [Ping timeout: 121 seconds] |
| 17:17 | | Attilla [The.Attilla@FBC920.642D35.0878D5.AE151E] has joined #Code |
| 17:17 | | mode/#code [+o Attilla] by Reiver |
| 17:49 | | Derakon[work] [Derakon@Nightstar-d44d635e.ucsf.edu] has joined #Code |
| 17:50 | | * Derakon[work] pulls up the Wikipedia page on the Traveling Salesman problem. |
| 17:50 | < Derakon[work]> | This is in fact for work. |
| 17:51 | < Derakon[work]> | (Biologists mark a set of sites on a slide that they wish to photograph; the goal is to minimize the tour time so that either more sites can fit into a minute's time, or strain on the microscope stage is reduced) |
| 17:53 | < Derakon[work]> | Fortunately, in general there are relatively few sites (less than 20, I'd think) and I don't need to find a perfectly optimal tour. |
| 17:53 | < Derakon[work]> | Just a better one than "the order in which the biologist chose the sites", which is what is currently used. |
| 17:56 | < Alek> | has anyone solved the Traveling Salesman in computer algorithm yet? |
| 17:57 | < Derakon[work]> | ...what is that question supposed to mean? |
| 17:57 | < Derakon[work]> | There's a trivial brute-force algorithm, if you don't mind O(n!). |
| 17:59 | < Derakon[work]> | If someone found a polynomial-time solution, they would win pretty much every science-based Nobel Prize simultaneously and then get assassinated. |
| 18:00 | <@McMartin> | Pretty much. |
| 18:00 | <@McMartin> | (How to get thrown out of a cryptography conference, episode 97: "So, suppose P=NP. What does that do for your scheme?") |
| 18:01 | | * McMartin gimbal-locks gnolam's soul, heads to work. |
| 18:07 | < Rhamphoryncus> | eh, if you relax your constraints and accept "pretty good" rather than "perfect" then most of those brute-force algorithms can be done much faster |
| 18:07 | < Derakon[work]> | Rhamphoryncus: yeah, mostly I'm just killing time while waiting to see if the random pokes I'm making to the microscope program will keep it from crashing. |
| 18:08 | < Derakon[work]> | ("Let's try sleeping for a quarter-second after every time we move the slide") |
| 18:11 | | * TheWatcher eyes these 'Use of uninitialized value in string eq at's in his error log, headscratches at how the code even got that far |
| 18:26 | | * TheWatcher args at WebService::Validator::HTML::W3C |
| 18:28 | < Derakon[work]> | It validates HTML with invalid Perl? |
| 18:30 | | Finale [c0cb88fe@Nightstar-14e5d099.mibbit.com] has joined #Code |
| 18:31 | < Derakon[work]> | "The fastest minimum spanning tree algorithm to date was developed by Bernard Chazelle, which is based on the soft heap, an approximate priority queue. [1] [2] Its running time is O(m ?(m,n)), where m is the number of edges, n is the number of vertices and ? is the classical functional inverse of the Ackermann function. The function ? grows extremely slowly, so that for all practical purposes it may be considered a constant no greater |
| 18:31 | < Derakon[work]> | than 4; thus Chazelle's algorithm takes very close to linear time." |
| 18:32 | <@TheWatcher> | No, it appears to freak out when handed utf-8 encoded strings |
| 18:32 | <@McMartin> | Actually, inverse Ackermann is even slower than various single-var functions that grow so slowly that they might as well be no larger than 4. |
| 18:32 | <@McMartin> | It's slower than any possible single-var function. |
| 18:32 | < Derakon[work]> | I find it highly amusing that the Ackermann function is even referenced in a serious algorithm. |
| 18:32 | <@McMartin> | Oh, it's actually p. common. |
| 18:32 | <@McMartin> | Union-find is as serious as you get and it's a similar running time. |
| 18:32 | < Finale> | why's that, Derakon? |
| 18:33 | <@McMartin> | But O (log* x) is generally easier to prove and, while it's also a higher lower bound than inverse Ackermann, it's generally way easier to prove. |
| 18:34 | <@McMartin> | (That's the function of "enter this number on a calculator. How many times can you hit the log button until you get an error back?" |
| 18:34 | < Derakon[work]> | ... |
| 18:34 | < Derakon[work]> | ;.; |
| 18:35 | < Derakon[work]> | I do find it highly appropriate that the abbreviation for the Ackermann function is "Ack(m, n)". |
| 18:35 | <@McMartin> | It grows more quickly than inverse Ackermann, but it's also "It's a constant that will never, ever get above about 4." |
| 18:35 | <@McMartin> | Heh |
| 18:35 | <@McMartin> | alpha really more like epsilon amirite |
| 18:52 | < Rhamphoryncus> | A(4, 4) is on the order of 2**(2**(10**19729))... according to wikipedia |
| 18:56 | < Rhamphoryncus> | aww, Qalculate doesn't have an ackermann function |
| 18:57 | < Derakon[work]> | Probably didn't want to either have their servers fall over, or crash your browser in Javascript. |
| 18:58 | < Rhamphoryncus> | Another spot on the same page says A(4, 4) is 2**(2**(2**65536)) - 3 |
| 18:58 | < Derakon[work]> | I want a 65536-bit computer~ |
| 18:58 | < Finale> | ahahahaha |
| 18:59 | < Finale> | what's ** mean? |
| 19:00 | < Rhamphoryncus> | power operator in python |
| 19:00 | < Finale> | so, ^ |
| 19:01 | < Rhamphoryncus> | that's bitwise xor ;) |
| 19:01 | < Derakon[work]> | ** is generally held to be unambiguous exponentiation. |
| 19:02 | < Derakon[work]> | ^ may mean exponentiation or may be a boolean operator depending on your context. |
| 19:02 | < Finale> | usually, it's exponentiation. >_> |
| 19:02 | < Derakon[work]> | Not in computer science, boyo. |
| 19:02 | < Finale> | wait, does power==exponent? |
| 19:03 | < Derakon[work]> | Think about that question for yourself and you should be able to answer it. |
| 19:03 | < Finale> | Dera: depends on the language or system, apparently. |
| 19:03 | < Finale> | Dera: I can't think straight right now. |
| 19:04 | < Finale> | you know what, never mind, I'm gonna go bash my head until I can think clearer. |
| 19:04 | < Rhamphoryncus> | looks like perl uses ** too |
| 19:06 | < Rhamphoryncus> | bc uses ^, but doesn't have bitwise operators |
| 19:06 | < Derakon[work]> | Yeah, bc is explicitly a calculator, not a programming language. :) |
| 19:07 | < Derakon[work]> | It doesn't like non-integer exponentiation or other such things, though, so I tend to use a Python REPL when I need to do arithmetic. |
| 19:10 | < Rhamphoryncus> | yeah, I use python or Qalculate |
| 19:10 | < Rhamphoryncus> | and here's one for you: ubunto *in* windows: http://www.andlinux.org/ |
| 19:34 | < Derakon[work]> | Hrm...it seems like I spend a lot of time writing constructs like this: http://paste.ubuntu.com/277322/ |
| 19:34 | < Derakon[work]> | There must be a better way to do this. |
| 19:35 | < Derakon[work]> | I could invoke sort() with a customized sort function, but typically I only care about the best option, so there's no point in sorting the rest. |
| 19:37 | < Derakon[work]> | I guess reduce() could do the trick? |
| 19:47 | <@McMartin> | It could, but you really might as well do a customized max function that just takes the list and the comparator. |
| 19:48 | <@McMartin> | (map, reduce, and range, IIRC, are sufficient to perform any algorithm that doesn't have free loops) |
| 19:48 | | * Derakon[work] googles for "free loop", gets lots of music and no CS. |
| 19:50 | < Derakon[work]> | It's times like these when I wish Python supported currying, so I wouldn't have to create a new function for each iteration through the loop that contains that construct. |
| 19:53 | <@ToxicFrog> | \o/ Curry! |
| 19:56 | <@ToxicFrog> | Re: TSP: I had good results with the ant farm algorithm two years ago |
| 19:58 | < Derakon[work]> | I'm going to check out how nearest-neighbor does first, just because it's so bloody simple to implement. |
| 19:59 | < Derakon[work]> | For a randomly-generated set of 20 points, it appears to be about 2-3x better than doing the points in generated order, which is what the microscope is currently doing. |
| 20:00 | < Derakon[work]> | (Granted, the biologist is unlikely to generate their points in random order) |
| 20:02 | <@McMartin> | Derakon[work]: while, break, continue |
| 20:02 | <@McMartin> | That is, it's all "for i = 1 to 10" |
| 20:02 | < Derakon[work]> | Ah. |
| 20:02 | <@McMartin> | Which is to say, recursively enumerable functions, not the full turing-decidable set of partial-recursive functions. |
| 20:02 | < Derakon[work]> | Loops with a fixed, a priori number of iterations. |
| 20:02 | <@McMartin> | (I think. It's been awhile.) |
| 20:18 | < Rhamphoryncus> | ... max() supports a key function |
| 20:19 | < Rhamphoryncus> | IOW, best = max(items, EvaluateMetric) |
| 20:19 | < Rhamphoryncus> | best = max(items, key=EvaluateMetric) |
| 20:20 | < Rhamphoryncus> | x_x some builtins don't support keyword arguments. That one requires it |
| 20:27 | < Derakon[work]> | The first reference I found for the max function didn't mention that, so I assumed it didn't exist. (http://pyref.infogami.com/max) |
| 20:28 | < Derakon[work]> | I should've just gone to http://docs.python.org/library/functions.html |
| 20:29 | < Derakon[work]> | ...and that doesn't help me for the microscope code, which is running Python 2.4. :\ |
| 20:29 | < Derakon[work]> | (It will be helpful for my own work though) |
| 20:30 | < Rhamphoryncus> | I did help(max) in the interpreter |
| 20:30 | < Rhamphoryncus> | and yeah, that sucks |
| 20:30 | < Derakon[work]> | I did not know about the help() function! |
| 20:31 | < Rhamphoryncus> | it works good for simple stuff like that. It sucks as for bigger APIs like random |
| 20:31 | < Rhamphoryncus> | I'd suggest writing a backported max() |
| 20:32 | | * Derakon[work] nods. |
| 20:32 | < Derakon[work]> | You wouldn't need the keyworded argument if max() didn't accept an arbitrary number of args. |
| 20:32 | < Derakon[work]> | Force it to only accept iterables and the second arg could be assumed to be an evaluation function. |
| 20:42 | < Rhamphoryncus> | of course. I actually like keyword arguments though |
| 20:42 | < Derakon[work]> | Sure, but having them be mandatory is a bit weird. |
| 20:43 | < Rhamphoryncus> | and a common usage is max(a, b) |
| 20:43 | < Rhamphoryncus> | naw, my problem was because I expected a builtin to not support it |
| 20:43 | < Derakon[work]> | Heh. |
| 20:43 | < Derakon[work]> | Point on that comman usage. |
| 20:43 | < Rhamphoryncus> | Even if it wasn't necessary for ambiguity I'd prefer to require a keyword here |
| 20:44 | < Rhamphoryncus> | consider, do you want sorted(a, b, c) or do you want sorted(a, key=b, reverse=c)? |
| 20:45 | < Rhamphoryncus> | 3.0 actually lets you require them using pure python code. def foo(x, *, y=None): ... |
| 20:46 | | AbuDhabi [farkoff@Nightstar-11c116b1.adsl.tpnet.pl] has joined #Code |
| 20:46 | | AnnoDomini [farkoff@Nightstar-403fac3e.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 20:50 | | Derakon[work] [Derakon@Nightstar-d44d635e.ucsf.edu] has quit [[NS] Quit: Leaving] |
| 21:37 | | Derakon [Derakon@Nightstar-d44d635e.ucsf.edu] has joined #Code |
| 21:37 | | mode/#code [+o Derakon] by Reiver |
| 21:37 | <@Derakon> | ] |
| 21:37 | | Derakon is now known as Derakon[work] |
| 21:38 | <@Derakon[work]> | Basic traveling-salesman optimization implemented and working. |
| 21:47 | | Orthianz [Orthianz@Nightstar-2a20c8f3.xnet.co.nz] has quit [Connection reset by peer] |
| 21:53 | | Orthia [Orthianz@Nightstar-2a20c8f3.xnet.co.nz] has joined #Code |
| 22:07 | | AnnoDomini [farkoff@Nightstar-11c116b1.adsl.tpnet.pl] has joined #Code |
| 22:07 | | mode/#code [+o AnnoDomini] by Reiver |
| 22:08 | | AbuDhabi [farkoff@Nightstar-11c116b1.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 22:09 | | * Derakon[work] idly ponders: given an NxN grid, what are the odds that there will be a duplicate in N randomly-generated points on that grid (integers only)? |
| 22:10 | <@Derakon[work]> | Seems to be pretty common with the 100x100 grid I was working with here. |
| 22:12 | <@Derakon[work]> | The odds of not getting a duplicate should be sum(1 - i/N^2) for i in (1..N), right? |
| 22:18 | <@McMartin> | Birthday paradox, I suspect |
| 22:21 | <@Vornicus-Latens> | Birthday problem; there's an approximation for it. Use N^2 and N for your inputs. |
| 22:22 | | Vornicus-Latens is now known as Vornicus |
| 22:22 | <@Derakon[work]> | Yeah, I recognized the Birthday Paradox. I was just curious what the actual numbers were like for my specific use case. |
| 22:23 | <@Derakon[work]> | Hrm...my math above is clearly wrong. E.g. if N = 3, then that says the odds of avoiding duplicates is 8/9 + 7/9. ?.? |
| 22:23 | <@Vornicus> | Approximation is sqrt(2d * ln(1 / (1 - p))); d is the number of possible values, p is the number of trials. |
| 22:24 | <@Vornicus> | erp, no, wrong equation. |
| 22:24 | | * Vornicus learns to read. |
| 22:25 | <@AnnoDomini> | Reading is tech. |
| 22:25 | | * AnnoDomini nods sagely. |
| 22:25 | <@Vornicus> | p(n, d) = 1 - e**(-(n(n-1))/2d) |
| 22:25 | <@Vornicus> | Approximately. |
| 22:27 | <@Derakon[work]> | >>> 1 - math.e**(-(10000*9999.0)/(2*100.0)) |
| 22:27 | <@Derakon[work]> | 1.0 |
| 22:28 | <@Vornicus> | Other way around. |
| 22:28 | <@Vornicus> | n is number if trials, d is the number of bins. |
| 22:28 | <@Derakon[work]> | Oh, whups. |
| 22:29 | < Rhamphoryncus> | I'm only good at calculating that stuff in the trivial case :) |
| 22:29 | <@Derakon[work]> | Hm, still get the same result for 1 - math.e**(-(100*99))/(2*10000.0) |
| 22:29 | <@Derakon[work]> | Oh, wait, misplaced paren. |
| 22:29 | <@Vornicus> | *snrrrrk* |
| 22:29 | <@Derakon[work]> | Division happened outside the exponent. |
| 22:29 | <@Derakon[work]> | Okay, approximated probability for a 100x100 grid with 100 trials is 39%. |
| 22:29 | <@Derakon[work]> | Nice. |
| 22:30 | < Rhamphoryncus> | ie the odds of two people not having the same birthday is 364/365. Odds of three people not having the same birthday is 364/365*363/365 |
| 22:31 | < Rhamphoryncus> | I've yet to find a trivial way to calculate 364*363*362 etc, other than writing a function |
| 22:32 | <@Vornicus> | technically it's Permute, which is indeed a function; really you want to use the approximation though! |
| 22:32 | <@Derakon[work]> | python -c 'print 364*363*362' |
| 22:33 | <@Derakon[work]> | :) |
| 22:35 | <@Vornicus> | (because 365! is rather large) |
| 22:37 | < Finale> | for n people, (364!/(364-n)!)/365(n-1) |
| 22:37 | < Rhamphoryncus> | Vornicus: thanks, perm(364, 3) works perfectly in Qalculate |
| 22:39 | < Rhamphoryncus> | hrm. I don't get the same odds as you |
| 22:39 | < Rhamphoryncus> | perm(100??2-1, 100-1)/(100??2)??100 = perm((100^2) - 1, 100 - 1) / ((100^2)^100) |
| 22:39 | < Rhamphoryncus> | ? 0.000060856596 |
| 22:39 | < Rhamphoryncus> | Probably doing something wrong |
| 22:40 | < Rhamphoryncus> | ah, off by 1 :) |
| 22:40 | <@Derakon[work]> | Hee. |
| 22:40 | < Rhamphoryncus> | 1-perm(100??2-1, 100-1)/(100??2)??99 = 1 - (perm((100^2) - 1, 100 - 1) / ((100^2)^99)) |
| 22:40 | < Rhamphoryncus> | ? 0.39143404 |
| 22:40 | < Finale> | wate something wrong in my equation. |
| 22:41 | | * Rhamphoryncus bumps the digits, hehe |
| 22:41 | < Finale> | for n people, (364!/(365-n)!)/365(n-1) perhaps? |
| 22:41 | < Rhamphoryncus> | = 51805863180918733462233002787948501620266931878852538998884137717323952141383643 74535795095308003566124032557995314799774720543618437441745557253574120597588001 94969320985868920282217174744514010550456216262728934892905974966571142197159600 46617993736026337980904868880534460166136327132684591468278604918745755300677483 4511354604493305565093995333399 / 13234889800848442797942539073119405657052993774414062500000000000000000000000 |
| 22:41 | < Rhamphoryncus> | 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000 |
| 22:41 | <@Derakon[work]> | Good god man! |
| 22:41 | < Rhamphoryncus> | *that* is why I use Qalculate :D |
| 22:42 | < Finale> | hm. works for 2 but breaks for 4. |
| 22:42 | < Finale> | what did I do wrong? |
| 22:43 | | * McMartin doesn't recommend mass murder, explosives, and self-immolation for everyone, but they've always worked for him. |
| 22:43 | <@Vornicus> | 's a lot of zeroes. |
| 22:43 | | * TheWatcher eyes Rhamph |
| 22:44 | <@TheWatcher> | Yeah, in any other channel, pasting something like that'd be very noughty. |
| 22:44 | < Finale> | not to mention it's undefined at n=1. -_- |
| 22:44 | | * Derakon[work] golf claps at TW. |
| 22:44 | | * Rhamphoryncus sneaks into TheWatcher's computer and resizes his terminal |
| 22:45 | <@TheWatcher> | ... ah, so this is what mimes in an invisible box feel like... |
| 22:47 | < Finale> | where n is at least 2, (365-1)(365-2)...(365-n)/365^(n-1)... |
| 22:48 | < Finale> | hmmmmm |
| 22:48 | < Finale> | NOW it works. |
| 22:49 | <@Vornicus> | numerator = denominator = 1; for k in range(n+1): numerator *= 365 - k; denominator *= 365 |
| 22:49 | < Finale> | for n people where n is a real whole number greater than 1, (364!/(365-n)!)/365^(n-1) |
| 22:49 | < Finale> | heyy... it actually also works for n=1 |
| 22:50 | < Finale> | for n people where n is a real whole number greater than or equal to 1, (364!/(365-n)!)/365^(n-1) |
| 22:50 | <@McMartin> | Yeah, 0! = 1 |
| 22:50 | <@McMartin> | n^0 = 1 for all nonzero n |
| 22:50 | | * Finale is pathetically proud of himself. >_> |
| 22:51 | < Rhamphoryncus> | Finale: likewise. I've been wanting "permute" for probably years now |
| 22:52 | < Rhamphoryncus> | It's actually a bit anticlimactic |
| 22:52 | <@McMartin> | Heh. In Haskell I wrote functions p and c |
| 22:52 | <@McMartin> | So that I can write 10 `c` 3 and get the combinatorial. |
| 22:53 | < Rhamphoryncus> | I do wonder how valuable arbitrary binary operators are for readability |
| 22:53 | < Finale> | ahahaha |
| 22:53 | < Finale> | and now I entered it into my calc as a callable function. |
| 22:54 | < Finale> | I go birthday(n) where n is the number of people, and it tells me the probability that they don't share a birthday. :P |
| 22:55 | < Finale> | for that matter, I can make it a double function - (switch,n) - to either give me the probability they don't share a birthday or the probability they do. :P |
| 22:55 | < Rhamphoryncus> | Stuff like a `?` b. Is that significantly better than a < b or a.issubset(b) |
| 22:55 | < Rhamphoryncus> | Although I had to look up the docs on .issubset() to know which way it went |
| 22:56 | <@Derakon[work]> | Rhamphoryncus: for general purposes, no, but in a specialized problem space (e.g. implementing a complicated mathematical algorithm) I could see it being useful. |
| 22:56 | <@AnnoDomini> | It's funny how in Civilization games, Writing is a technological advance, but there's no Reading. :P |
| 22:56 | <@Vornicus> | Finale: Now put 2**32 in there as your d. |
| 22:57 | < Rhamphoryncus> | Derakon[work]: I wonder if it'd be worth adding ? just so you can limit < to a total ordering |
| 22:57 | < Finale> | I could either figure out the opposite equation, or I could just go 1-result on the one I have. :P |
| 22:57 | < Finale> | Vorn........ |
| 22:58 | <@Vornicus> | (I regularly discuss the birthday problem with numbers of that size involved.) |
| 22:58 | < Finale> | d being which number? |
| 22:58 | <@Vornicus> | The number of bins. |
| 22:58 | < Finale> | days or people? |
| 22:58 | | * Finale hasn't had probability in over 10 years or so. |
| 23:03 | | * Finale spocks. |
| 23:04 | | Derakon[work] [Derakon@Nightstar-d44d635e.ucsf.edu] has quit [[NS] Quit: Leaving] |
| 23:06 | <@Vornicus> | Days |
| 23:07 | < Finale> | ah, yes. |
| 23:07 | < Finale> | I can actually rework the function to fit a variable there, I'm sure. |
| 23:11 | < Finale> | hrm. |
| 23:12 | | * Finale eyebrows. |
| 23:12 | < Rhamphoryncus> | hrm. Isn't there a rule of thumb for permutations that about half the size of the number of bins is about 50%? |
| 23:12 | <@Vornicus> | whut? |
| 23:12 | < Rhamphoryncus> | ie, 2**128 bins, you need about 2**64 of them filled |
| 23:13 | < Finale> | up to (2,2^8) where (people,bins) it works fine... at (2,2^9) it goes undef when asked for precision, but does show the fraction (in this case, 511!/(510!*512)) |
| 23:14 | | Orthia [Orthianz@Nightstar-2a20c8f3.xnet.co.nz] has quit [Connection reset by peer] |
| 23:16 | < Finale> | probably because the precision is so close to 1....... but seriously, it shouldn't undef, it should either go .999999999999999 or 1. |
| 23:16 | < Rhamphoryncus> | Sounds more like an overflow |
| 23:17 | < Finale> | very possible, yes. |
| 23:17 | < Finale> | this is an old year-2000 TI-89. |
| 23:18 | < Finale> | luckily it still does render the fraction. |
| 23:18 | < Finale> | which is helpful enough. :D |
| 23:18 | < Finale> | for many exponents beyond. |
| 23:18 | < Finale> | but 2^32 gives it trouble even there. |
| 23:19 | < Rhamphoryncus> | what is that specifically? Two people in 2**32 days? |
| 23:20 | < Finale> | something like that, I guess. |
| 23:20 | < Finale> | basically, yeah. |
| 23:21 | < Rhamphoryncus> | 1-perm(2??16-1, 2)/(2??16)??2 = 1 - (perm((2^16) - 1, 2) / ((2^16)^2)) |
| 23:21 | < Rhamphoryncus> | ? 0.000045775902 |
| 23:21 | < Rhamphoryncus> | took a few seconds |
| 23:21 | < Rhamphoryncus> | for 2**8 it says 0.011688232421875 |
| 23:22 | | Orthia [Orthianz@Nightstar-2a20c8f3.xnet.co.nz] has joined #Code |
| 23:30 | | Finale [c0cb88fe@Nightstar-14e5d099.mibbit.com] has quit [[NS] Quit: later.] |
| 23:49 | <@Vornicus> | http://en.wikipedia.org/wiki/Birthday_attack <---- |
| 23:50 | <@Vornicus> | The table gives you approximate... stuff. |
| 23:52 | < Rhamphoryncus> | yeah. 128 bits is questionable today |
| 23:57 | < Rhamphoryncus> | interesting. It seems to have a constant offset of log2(sqrt(pi/2)) |
| 23:58 | < Rhamphoryncus> | using their approximation anyway |
| --- Log closed Fri Sep 25 00:00:43 2009 |