00:26:47 -!- ATMunn has quit (Quit: lol rip).
00:28:38 -!- Bowserinator has quit (Quit: Blame iczero something happened).
00:33:09 -!- Bowserinator has joined.
00:35:19 -!- ATMunn has joined.
00:35:46 -!- adu has quit (Quit: adu).
00:54:11 -!- rain1 has quit (Ping timeout: 240 seconds).
00:57:21 -!- clog has joined.
01:21:12 -!- rain1 has joined.
01:28:26 -!- shinh_ has quit (Read error: Connection reset by peer).
01:29:20 -!- shinh_ has joined.
01:29:46 <esowiki> [[User:ZippyMagician/Ideas]] https://esolangs.org/w/index.php?diff=76438&oldid=76352 * ZippyMagician * (-2292) Fix a major issue in the docs
02:03:09 -!- adu has joined.
02:18:30 <tswett[m]> All right, here's my favorite OEIS sequence today.
02:18:37 <tswett[m]> http://oeis.org/A139138 - Numbers divisible by at least two of their digits. :D
02:34:16 <pikhq> Aw, that's a cute sequence
03:18:06 -!- adu has quit (Quit: adu).
03:20:01 -!- adu has joined.
03:48:35 -!- Lord_of_Life has quit (Ping timeout: 240 seconds).
03:50:00 -!- Lord_of_Life has joined.
05:22:46 -!- xelxebar_ has quit (Quit: ZNC 1.7.2+deb3 - https://znc.in).
05:23:10 -!- xelxebar has joined.
05:43:02 -!- shinh_ has quit (Remote host closed the connection).
05:43:33 -!- shinh_ has joined.
06:16:27 <esowiki> [[Grid]] M https://esolangs.org/w/index.php?diff=76439&oldid=71289 * Hakerh400 * (-10)
06:17:09 <esowiki> [[Subreal]] https://esolangs.org/w/index.php?diff=76440&oldid=76413 * RocketRace * (+754) Examples: Fib!
06:19:28 -!- adu has quit (Quit: adu).
06:40:01 -!- kritixilithos has joined.
06:55:40 -!- kspalaiologos has joined.
07:01:40 <esowiki> [[Subreal]] https://esolangs.org/w/index.php?diff=76441&oldid=76440 * RocketRace * (+46) /* Control flow operations */
07:14:14 <esowiki> [[Talk:E62qpodb593]] N https://esolangs.org/w/index.php?oldid=76442 * TwilightSparkle * (+314) Created page with "== Golfing language? == This looks too verbose to be a golfing language. Most golfing languages have straight-forward string outputting like <code>"Hello, World!"</code>, not..."
07:17:10 <esowiki> [[1+/Snippets]] https://esolangs.org/w/index.php?diff=76443&oldid=76425 * TwilightSparkle * (+90) /* Pop */
07:17:51 <esowiki> [[1+/Snippets]] M https://esolangs.org/w/index.php?diff=76444&oldid=76443 * TwilightSparkle * (-10) /* Easy */
07:39:13 <rain1> http://oeis.org/A087140
07:51:24 -!- BWBellairs has quit (Quit: Quit).
07:53:37 -!- BWBellairs has joined.
07:57:04 <esowiki> [[NoRAL]] https://esolangs.org/w/index.php?diff=76445&oldid=76407 * TheCoderPro * (+79) /* External resources */
08:07:58 -!- hendursa1 has joined.
08:09:43 -!- hendursaga has quit (Ping timeout: 240 seconds).
08:10:50 -!- Phantom__Hoover has joined.
08:22:37 <Taneb> Hmm, I imagine A139138 would increase roughly logarithmically
08:24:06 -!- imode has quit (Ping timeout: 260 seconds).
08:36:29 -!- Sgeo has quit (Read error: Connection reset by peer).
09:42:58 -!- Frater_EST has joined.
09:55:43 -!- b_jonas has quit (Quit: leaving).
10:27:20 <esowiki> [[Subreal]] M https://esolangs.org/w/index.php?diff=76446&oldid=76441 * RocketRace * (+26) Base 32!
10:40:19 <esowiki> [[Special:Log/newusers]] create * RealestLink * New user account
10:44:44 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=76447&oldid=76428 * RealestLink * (+237)
10:48:56 <esowiki> [[Esolang:Community portal]] https://esolangs.org/w/index.php?diff=76448&oldid=75596 * RealestLink * (+1) Fixed the invite link to "Compilers and Interpreters"
11:11:32 -!- salpynx has quit (Remote host closed the connection).
11:37:04 -!- wib_jonas has joined.
12:00:44 -!- craigo has quit (Ping timeout: 246 seconds).
12:32:19 <wib_jonas> question. have you designed or implemented some kind of network protocol, like HTTP or IRC or ssh but not something as well-spread but possibly just a toy application that only you use, and that intends to have a tcp server listening on a fixed port for a long time, whether to do all the communication or just for initiating a connection? if so,
12:32:19 <wib_jonas> have you tried to add a feature such that if someone accidentally connects to that tcp server with an entirely wrong client, such as a HTTP browser or telnet client, then the server will likely send them a human-readable message that tells them what they did wrong and optionally what this tcp server is for?
12:33:13 <esowiki> [[Special:Log/newusers]] create * Razetime * New user account
12:33:38 <wib_jonas> and if so, have you tried to optimize this such that you can send this reply possibly immediately as a fixed header, or at least after the other party sends just very little data to you and without having to wait for a long timeout?
12:36:37 <wib_jonas> Taneb: "I imagine A139138 would increase roughly logarithmically" => impossible, it is a strictly increasing sequence of integers that contains every integer that is congruent to 11 modulo 100
12:37:33 <esowiki> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=76449&oldid=76447 * Razetime * (+160) /* Introductions */
12:37:44 <esowiki> [[MAWP]] https://esolangs.org/w/index.php?diff=76450&oldid=76131 * Razetime * (+40) Added truth machine
12:40:20 <Taneb> wib_jonas: that is true
13:05:21 <esowiki> [[1+]] https://esolangs.org/w/index.php?diff=76451&oldid=76191 * TwilightSparkle * (-41) /* Commands and syntax */ Wrong
13:09:22 <esowiki> [[1+/Snippets]] https://esolangs.org/w/index.php?diff=76452&oldid=76444 * TwilightSparkle * (+124) /* Hard */
13:39:12 -!- hendursa1 has quit (Quit: hendursa1).
13:39:32 -!- hendursaga has joined.
13:46:05 <esowiki> [[MAWP]] https://esolangs.org/w/index.php?diff=76453&oldid=76450 * TwilightSparkle * (-447) /* Computational class */ The proof is completely wrong.
13:49:30 <esowiki> [[MAWP]] https://esolangs.org/w/index.php?diff=76454&oldid=76453 * TwilightSparkle * (+88) /* Computational class */
13:49:53 <esowiki> [[MAWP]] M https://esolangs.org/w/index.php?diff=76455&oldid=76454 * TwilightSparkle * (-2) /* Computational class */
14:08:06 -!- ais523 has joined.
14:08:45 <ais523> wib_jonas: I implemented such a service, but the outermost layer is TLS and if someone unexpected tries to connect, the TLS won't even work
14:08:52 <ais523> so there's no scope to do something like you're suggesting
14:09:10 <ais523> you would need to put such a fixed-error-message output into the TLS implementation rather than the application
14:09:18 <int-e> "Copyrighted material are also strictly prohibited." -- always a good laugh, that.
14:09:29 <ais523> I imagine other people in the same situation would have had the same issue
14:09:57 <wib_jonas> ais523: thank you. but will it fail also if someone connects with a different client that uses TLS, such as a HTTPS client or IRC client with TLS enabled?
14:10:25 <wib_jonas> or does TLS have a built-in high-level protocol marker that you're using for this?
14:11:05 <wib_jonas> and yes, for that you'd probably have to modify the TLS library to support this
14:11:11 <ais523> the server end wouldn't be able to see what the client end was sending due to a certificate error
14:11:30 <ais523> from the client end, I think it'd just see the connection closing
14:11:42 <wib_jonas> ais523: you don't need to see what the client is sending to send an error message
14:11:46 <ais523> I guess you could modify the TLS library to send something using the client's actual certificate even if it wasn't recognised
14:11:50 <wib_jonas> ais523: so you're using a client certificate?
14:11:55 <ais523> yes, client certificate
14:12:13 <ais523> I guess most people don't do that
14:12:18 <ais523> but it's a very simple way to do auth
14:13:06 <wib_jonas> sure, but you could also do it optionally, as in run a single Apache that listens on https, and some of the things it serve require a client cert, but just a hello world page or an error message doesn't
14:14:42 <ais523> I guess you could make it work
14:15:08 <ais523> although, I'm not going to for my project, because the amount of development effort required, and the risk of introducing a security bug, would be disproportionate to the benefit
14:15:26 <ais523> (especially as this was for work so I need to justify what I'm spending my time on)
14:15:37 <wib_jonas> it's not "make it work", if I want to serve something on https, as opposed to tls in general, than I will probably put it behind an Apache because it handles the peksy server-side details of HTTP
14:15:40 <int-e> Hmm, what's the story on the discord front? (This change, https://esolangs.org/w/index.php?diff=76448&oldid=75596 ... basically I'm wondering whether there are now two competing rooms/channels/whatever the name, or whether the former is gone)
14:16:44 <wib_jonas> int-e: I think discord links can expire after some time, maybe it expired?
14:17:35 <int-e> Just something to keep an eye for a while on I suppose.
14:17:46 <int-e> I'm not curious enough to actually try out discord for this.
14:18:03 <wib_jonas> it's a bit weird, they use time-limited invite links, but the links have so little entropy that you could brute-force yourself into random discords easily such that any discord can't be kept private from that
14:18:16 <uplime> int-e: they both look to go to the same discord server fwiw
14:18:18 <wib_jonas> I don't use discord so maybe this is not true and I just don't understand it
14:19:11 <wib_jonas> but I hear from other people who use discord (and just this morning I just found out that another IRC channel that I'm on had a bridge from discord and two more forums in two more chat protocols different from IRC or discord)
14:20:49 <int-e> uplime: thanks, that's reassuring
14:26:01 <int-e> does anybody know why the esowiki has lemons for its logo?
14:28:09 <ais523> and it was originally just picked from a list of placeholder images as a placeholder, but we grew to like it
14:29:32 <uplime> i think its a good logo personally
14:30:05 <wib_jonas> ais523: ah, like the colored wavy lines in the left side of my homepage, which were placeholders and I meant to replace them with better images, at least with wavy lines with different shapes, but nice vertical banners for this purpose aren't easy to find, and I was lazy, so I just have wavy lines there forever.
14:31:25 <wib_jonas> maybe another 12 years from now, when I do a major revision on that homepage ...
14:33:39 <wib_jonas> as for meaningless images that I never replace, I have another story. I sometimes set different desktop background images on different desktop computers just so it's easier to tell at a glance which computer I'm working on.
14:35:31 <ais523> I've started doing that with shell prompts
14:35:47 <ais523> it's easy to miss the hostname in the prompt if you aren't concentrating, so I've been making them different colors on different computers
14:36:01 <wib_jonas> now at my current job, I use some virtualized windows machines, and I even have some where I installed some software and then gave copies of the image to coworkers to use. I put different desktop backgrounds to them for the above mentioned reason, and now I also replace the background before I give a copy to a coworker, because they're sometimes
14:36:02 <wib_jonas> lazy to change the background and then I ended up with a vm that has the same background as vms that another coworker uses.
14:36:51 <wib_jonas> hmm, in fact, I should look for a replacement background image for that particular vm image right now, and replace it in my local copy the next time I boot it up, because that situation still hasn't got resolved;
14:38:26 <wib_jonas> though with the more recent image that I distributed, I was careful enough to change the background immediately, so now the latest vm has rape seed field as the background in my version buy cotton bale as the background in the distributed version.
14:39:09 <wib_jonas> oh yeah, the images also lead to easy naming the vm.
14:40:14 <wib_jonas> hmm yeah, in fact I should change the descriptive name of this vm instance (which is for information display purposes only, doesn't change anything, but easily visible even when the VM is not running) to include "rape seeed"
14:40:57 <wib_jonas> oh crap, I'm not allowed to change the descriptive name while the VM is running
14:42:10 <wib_jonas> so anyway, this also gives a possible solution for the hard problem of naming
14:42:32 <wib_jonas> admittedly the descriptive name of the VM also has some meaningful non-arbitrary parts
14:43:44 <wib_jonas> because, you know "I know, I'll call this vm 'win10' to distinguish from the previous vm which runs windows 7" then 6 months later "crap, now the next vm will be running windows 10 as well"
14:44:19 <int-e> ais523: cheers, I can stop wondering about a hidden meaning then :)
14:44:58 <wib_jonas> it's easier not to choose another rape seed photo as background for the next meaningless background image
15:02:01 -!- Sgeo has joined.
15:39:59 -!- xkapastel has joined.
15:49:03 -!- Lord_of_Life_ has joined.
15:50:41 -!- Lord_of_Life has quit (Ping timeout: 246 seconds).
15:51:53 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
16:13:13 <wib_jonas> of course I also have to choose a background that is not such a cliche that someone else would independently choose to use it as a desktop background, eg. I won't use a plain grass or wheat pasture hill or partly clouded sky unless it has some more specific recognizable feature.
16:14:08 <wib_jonas> A rape seed field is common enough in reality in Hungary that it feels pleasant and neutral enough for a background, but not cliche enough that I'll have coworkers with confusable rape seed fields as their desktop background.
16:14:15 -!- wib_jonas has quit (Quit: Connection closed).
16:18:57 <zzo38> wib_jonas: To your question from before, does NNTP count? However, I have not implemented any attempt to answer HTTP requests, and am not sure how.
16:24:53 -!- Arcorann has quit (Read error: Connection reset by peer).
16:27:23 -!- LKoen has joined.
16:30:13 <esowiki> [[MAWP]] M https://esolangs.org/w/index.php?diff=76456&oldid=76455 * LegionMammal978 * (+1) automaton is the singular form
17:03:25 -!- TheLie has joined.
17:27:35 -!- adu has joined.
17:36:43 -!- kritixilithos has quit (Ping timeout: 240 seconds).
17:38:15 -!- b_jonas has joined.
17:44:37 <zzo38> If the user does type HELP though then it does mention which RFC to read
17:46:35 -!- imode has joined.
17:53:41 -!- ais523 has quit (Quit: quit).
17:54:31 -!- kritixilithos has joined.
18:24:19 <esowiki> [[User:Osmarks/!lyriclydemoteestablishcommunism!]] N https://esolangs.org/w/index.php?oldid=76457 * Osmarks * (+2190) Created page with "{{Deletedpage}} {{infobox proglang |name= |paradigms=imperative |author=[[User:Heavpoot]] |year=[[:Category:2020|2020]] |memsys=No memory |dimensions=No dimensions |class=No..."
18:54:58 -!- kritixilithos has quit (Quit: quit).
19:04:27 -!- craigo has joined.
19:08:45 <esowiki> [[HELP (Preprocessor)]] https://esolangs.org/w/index.php?diff=76458&oldid=74795 * LegionMammal978 * (+78) added repo link
19:23:25 -!- adu has quit (Quit: adu).
19:28:35 -!- kspalaiologos has quit (Quit: Leaving).
19:29:19 -!- adu has joined.
19:44:38 <esowiki> [[Auo]] M https://esolangs.org/w/index.php?diff=76459&oldid=75196 * LegionMammal978 * (+15) /* External resources */ fixed it
19:53:42 -!- LegionMammal978 has joined.
19:54:15 -!- LegionMammal978 has quit (Remote host closed the connection).
20:07:33 <zzo38> Do you like the kind of random padding that I had made up for cryptographic use?
20:13:19 <shachaf> I don't know what padding you made up.
20:13:35 <zzo38> I mentioned it on this IRC before, probably a few days ago
20:19:35 -!- xkapastel has quit (Quit: Connection closed for inactivity).
20:21:06 -!- LKoen has quit (Quit: “It’s only logical. First you learn to talk, then you learn to think. Too bad it’s not the other way round.”).
20:24:46 <esowiki> [[Spite]] https://esolangs.org/w/index.php?diff=76460&oldid=75643 * LegionMammal978 * (-15) /* External resources */ fixed link
20:29:39 -!- adu has quit (Quit: adu).
20:36:20 -!- adu has joined.
20:37:41 -!- Melvar has quit (Ping timeout: 246 seconds).
20:38:05 -!- Melvar has joined.
20:46:53 <zzo38> I will repeat it, I suppose.
20:48:21 <zzo38> Start with one byte length of random data, and then random data, and then a checksum of the entire stream so far, and then the sequence number (which is the first sequence number is secret), and then the length of the payload data, and then the payload data; that makes one frame.
20:48:41 <zzo38> (Data can be arbitrarily split into frames)
20:50:27 -!- heroux_ has joined.
20:50:48 -!- adu has quit (Quit: adu).
20:51:39 -!- heroux has quit (Ping timeout: 240 seconds).
20:51:42 -!- heroux_ has changed nick to heroux.
20:52:53 <esowiki> [[Polynomial]] https://esolangs.org/w/index.php?diff=76461&oldid=75933 * LegionMammal978 * (-1642) don't use that it's broken
21:04:50 <esowiki> [[Main Page]] https://esolangs.org/w/index.php?diff=76462&oldid=76109 * LegionMammal978 * (-1) The About and Policy pages call it Esolang
21:33:20 -!- Phantom__Hoover has quit (Ping timeout: 256 seconds).
21:34:47 -!- xkapastel has joined.
21:39:32 -!- ais523 has joined.
21:43:21 -!- Frater_EST has quit (Read error: Connection reset by peer).
21:54:08 <int-e> b_jonas: Oh the July Ponder This challenge solutions is published. They list German as a possible way to get the Fibonacci sequence, from A = AH and H = HAH. (I found this, but I thought that being a native speaker was *not* an advantage in this case.)
21:55:07 <HackEso> The password of the month is still up for grabs.
21:55:16 <b_jonas> int-e: do you have a link handy?
21:55:19 <int-e> . o O ( Time for shachaf to have another panic attack. )
21:55:31 <int-e> b_jonas: this? http://www.research.ibm.com/haifa/ponderthis/solutions/July2020.html
21:55:39 <uplime> is there a datastructure better suited for representing an AST than say a linked list?
21:55:45 <int-e> b_jonas: or this? https://en.wikipedia.org/wiki/German_spelling_alphabet#Basic_alphabet
21:56:05 <int-e> shachaf: It's another month and I just queried the potm
21:56:27 <b_jonas> I thought the solution had more details
21:56:49 <int-e> shachaf: I do hope that you're not suffering from literal panic attacks.
21:57:04 <int-e> b_jonas: Yeah it's a bit disappointing that it doesn't.
21:57:51 <shachaf> `learn The password of the month is the same as last month's.
21:57:53 <int-e> > let f 'a' = "ah"; f 'h' = "hah" in take 10 $ map length (iterate (>>= f) "a")
21:57:55 <lambdabot> [1,2,5,13,34,89,233,610,1597,4181]
21:58:11 <int-e> b_jonas: it's not the Fibonacci sequence, it's every second term.
21:58:19 <int-e> > let f 'a' = "ah"; f 'h' = "hah" in take 10 $ map length (iterate (>>= f) "h")
21:58:21 <lambdabot> [1,3,8,21,55,144,377,987,2584,6765]
21:58:25 <int-e> and those are the other terms
22:00:43 <int-e> b_jonas: http://int-e.eu/~bf3/tmp/p2020-07.txt were my notes for the bonus part
22:04:32 <b_jonas> is there something that generalizes certain ordinal notations to let us compute with a certain subset of surreal numbers?
22:05:56 <b_jonas> obviously http://www.madore.org/~david/weblog/d.2011-11-13.1964.nombres-surreels.html answers that. I should have looked there first
22:23:43 -!- ais523 has quit (Quit: quit).
22:37:53 -!- TheLie has quit (Remote host closed the connection).
22:41:23 -!- hendursaga has quit (Ping timeout: 240 seconds).
22:42:46 -!- hendursaga has joined.
22:44:11 -!- tromp has quit (Remote host closed the connection).
22:50:36 -!- Arcorann has joined.
22:51:36 -!- Arcorann has quit (Remote host closed the connection).
22:52:02 -!- Arcorann has joined.
23:04:56 -!- ais523 has joined.
23:05:27 <ais523> looking for some stupid bit-twiddling tricks help: can anyone suggest an efficient way to identify the fifth-least-significant set bit in a number?
23:06:37 <b_jonas> ais523: sorry, uh, I'm too tired for that, look in Warren's Hacker's Delight 2nd ed, which is right here on my shelf but I'm going to bed and can't think clear enough to interpret the book
23:06:46 <ais523> hmm, actually, there's a shortcut in my problem: I know that all bits above it will be set (but the bit immediately below might also be set, so I can't just look for the top 0)
23:07:18 <b_jonas> ais523: in that case don't you just do a popcount and then a subtraction or something?
23:07:21 <ais523> so I can count the number of set bits and that probably gives the answer directly?
23:08:19 <ais523> this doesn't actually need to be efficient, but I can't bear to write the loop
23:08:57 <b_jonas> ais523: popcount then, and find an existing implementation of popcount for whatever you're writing this in, I can even help in that part if you need
23:09:23 <ais523> I'm writing in Rust which has popcount in the standard library, fortunately
23:11:35 -!- callforjudgement has joined.
23:11:42 -!- ais523 has quit (Disconnected by services).
23:11:44 -!- callforjudgement has changed nick to ais523.
23:15:52 <int-e> ais523: By "loop", do you mean four times x = x & (x-1), followed by x & -x?
23:16:32 <ais523> int-e: I was thinking about something stupider; that version, I /could/ bear to write, although it still seems less elegant than it needs to be
23:16:57 <ais523> oh, I figured it out, anyway, start with 0b10000 and then do an inverse select on the original number
23:17:04 <ais523> (inverse-select is a builtin on x86)
23:17:32 <ais523> although that probably isn't in Rust's standard library
23:17:33 <int-e> there's https://www.felixcloutier.com/x86/pdep (which apparently is really slow on Zen)
23:18:14 <int-e> (which would allow you to deposit 0x10 into the work you want to analyze to give you the 5th bit)
23:18:51 <ais523> ah right, pdep is what it's called
23:18:55 <int-e> maybe there's an intrinsic for that.
23:19:04 <ais523> that's the instruction I was thinking of, I remembered the instruction but couldn't remember the name
23:19:10 <shachaf> Do you need the index of the bit or just to have it set?
23:19:10 <int-e> (probably but I hate looking this up)
23:19:35 <ais523> pext/pdep aren't methods of u64 in Rust, at least
23:19:37 <ais523> shachaf: need the index
23:19:50 <int-e> what else... bsl in a loops (eww)
23:20:21 <int-e> but the index is just a popcount away from finding the mask
23:20:26 <ais523> my superoptimiser almost certainly isn't powerful enough to find this
23:20:37 <shachaf> Rust supports inline assembly now, right?
23:20:59 <ais523> you wouldn't use it in this situation anyway, if you want to write platform-specific code there are bindings to all the asm instructions individually
23:21:06 <b_jonas> "inverse-select is a builtin on x86" => only on cpus newer than the ones that have popcount though
23:21:25 <int-e> b_jonas: how does popcount solve this problem?
23:21:28 <b_jonas> ais523: I think they do have a library that contains most x86 intrinsics though
23:21:29 <ais523> in this case, pub unsafe fn _pdep_u64(a: u64, mask: u64) -> u64
23:21:31 <int-e> I don't think it does
23:21:56 <ais523> int-e: it solves it in the situation where you know that all the bits above the one you want are 1 bits (but some of the bits immediately below might be too)
23:21:59 <ais523> which is the case for me
23:21:59 <shachaf> int-e: I think it works here, since all the higher bits are set?
23:22:16 <int-e> ais523: I still don't see how
23:22:41 <ais523> int-e: you know that there are precisely four 1 bits below the one you want, so all but five 1 bits must be above
23:22:57 <b_jonas> the functions in the rust library are btw named the same as the intel compiler intrinsic functions, which all of intel, ms, gcc compilers have in a standard header
23:22:59 <int-e> okay, that was stupid.
23:23:07 <ais523> and there are no 0 bits above, thus knowing how many 1 bits are above gives you the number of bits above and thus the index of the bit you want
23:23:28 <b_jonas> I looked at it once, and found a few things missing that I reported, but haven't bothered to write the patch for it yet
23:23:56 <b_jonas> yeah, that stuff you said, _pdep_u64
23:24:05 <ais523> come to think of it, this might make an interesting codegolf problem
23:24:23 <ais523> (the "fifth-least-significant set bit" problem in the general case)
23:24:57 <shachaf> I'm looking for a reference on the first use of the reasonable precedence parsing algorithm (sometimes called "precedence climbing" or "Pratt parsing" or other names).
23:25:21 <shachaf> Someone attributes it to the BCPL compiler, but I can't find the code for that.
23:25:23 <int-e> Hmm. I wonder how the 1252 threashold in http://www.research.ibm.com/haifa/ponderthis/challenges/August2020.html was chosen.
23:25:43 <ais523> I have a book about compilers that uses BCPL for its examples, and talks about "operator-precedence parsing"
23:26:10 <ais523> from memory, "Understanding and Writing Compilers" by Bornat
23:26:14 <ais523> but I may have misremembered
23:26:18 <b_jonas> shachaf: reference on first use of the reasonable precedence parsing algorithm => look in TAOCP volume 5, TAOCP usually tells about the history
23:26:20 <int-e> (It seems too high to make this interesting. And the * bonus looks too hard.)
23:27:43 <int-e> ais523: I didn't realise how restrictive that additional constraint (no 0 bits above the one you want) really is.
23:27:58 <int-e> So... yeah, stupid.
23:28:22 <shachaf> The algorithm is so simple that it seems silly to give it a name, but also many people (including me) find it nonobvious before they see it.
23:28:57 <shachaf> But people write much more complicated precedence parsing code all the time.
23:29:20 <ais523> int-e: my guess is that the people setting the problem tried to solve it for some length of time and 1252 was their best score
23:29:36 <b_jonas> shachaf: those are some of the best algorithms, the ones that are trivial and beautiful after you understand it, but look like magic that nobody could possibly have invented before that
23:29:56 <shachaf> b_jonas: I don't have TAOCP unfortunately (except for two fascicles).
23:30:08 <ais523> ayacc will generate operator-precedence parsing code as an optimisation in some cases
23:30:10 <int-e> ais523: Yeah but the first thing I tried got it down to 1235.
23:30:13 <shachaf> b_jonas: I think Floyd's algorithm that we discussed the other day is like this.
23:30:23 <ais523> int-e: maybe you just got lucky?
23:31:12 <b_jonas> shachaf: no problem, nobody has volume 5 yet, it's not yet written, you have many years before it will be published, so since you already have to wait, it doesn't matter that you haven't bought it yet
23:31:32 <int-e> (This is hardly a spoiler, it's pretty much the most obvious attempt: I added a single losing position, and no winning position.)
23:31:56 <ais523> adding a losing position may cause some losing positions to become winning, though
23:32:07 <ais523> so the exact details would matter
23:32:20 <int-e> I tried all possibilities.
23:32:51 <ais523> the tortoise-and-hare cycle-finding algorithm is something I found very non-obvious before I saw it
23:33:16 <int-e> And yes, it turns some losing positions into winning positions. That is the point really, because the goal is to get as few losing positions as possible.
23:34:14 <shachaf> ais523: Oh, that wasn't the Floyd's algorithm I meant, I meant the one for sampling.
23:34:19 <shachaf> I suppose Floyd has many algorithms.
23:34:34 <ais523> shachaf: huh, that's coincidence, I thought of the algorithm itself without realising the Floyd connection
23:35:05 <ais523> (also, Wikipedia isn't sure that Floyd actually created the tortoise-and-hare algorithm)
23:35:30 <shachaf> Nevertheless I've heard people call it "Floyd's algorithm".
23:35:49 <shachaf> I like the Pollard's lambda algorithm for finding cycles.
23:35:53 <b_jonas> ais523: yeah. and the algorithm to find a birthday attack on a black box function with range 2**n with O(2**(n/2)) queries but with memory usage of only a O(2**(n/4)) sized hash table of values
23:36:01 <shachaf> It seems much more practical in situations where you can use it.
23:36:19 <int-e> https://en.wikipedia.org/wiki/Cycle_detection attributes it to Floyd
23:36:31 <b_jonas> and yes, the Pollard rho algorithm for prime factorization, which is based on that
23:36:41 <ais523> int-e: it states that it's often referred to as Floyd's algorithm, but starts by disputing that attribution
23:37:04 <b_jonas> oh yeah, Floyd's algorithm is also like that
23:37:05 <int-e> b_jonas: the point of that one is that it's parallelizable, right?
23:37:05 <shachaf> I suppose that for Pollard's rho factoring algorithm you have to use the "turtle and hare" method, you can't use the lambda trick, right?
23:37:09 <ais523> b_jonas: we're assuming that the function has an infinite domain, right?
23:37:24 <b_jonas> I mean Floyd's algorithm to compute each pair of distances in a graph with weighted edges
23:37:27 <shachaf> Because you don't actually have an identity you can distinguish.
23:37:34 <int-e> ais523: Funny, it doesn't do that in the initial description.
23:37:55 <b_jonas> int-e: that's just one point, but that part isn't too surprising, more surprising is that it needs less storage
23:38:34 <ais523> <b_jonas> I mean Floyd's algorithm to compute each pair of distances in a graph with weighted edges ← for TAEB::AI::Planar I created my own pathfinding algorithm designed to be efficient at doing that
23:38:42 <ais523> but also at updating the cache when the graph changed slightly
23:38:51 <int-e> Brent's variant is usually faster anyway.
23:39:05 <shachaf> Wait, let me remember how Pollard's factoring algorithm works.
23:39:18 <int-e> b_jonas: But that's a lot of memory...
23:39:40 <int-e> b_jonas: The basic cycle finding just needs to keep track of a couple of values.
23:39:42 <b_jonas> int-e: um, that depends on how large n is
23:39:53 <ais523> how fast is the birthday attack for finding collisions in a function where you start with a value that isn't in the range, then you repeatedly feed it its own output?
23:40:12 <ais523> that's O(n) memory, but I'm not sure what the efficiency is
23:40:18 <b_jonas> int-e: ok, then the point IS that it's parallelizable, you pay memory to be parallelizable
23:40:35 <int-e> b_jonas: Yes that was my point.
23:40:39 <fizzie> I found Floyd-Steinberg dithering unintuitive at first. But maybe I just initially saw it explained badly. On the other hand, there's a cute cat in the Wikipedia page about it.
23:41:03 <shachaf> ais523: This is what the "distinguished point"/lambda trick is about, right?
23:41:12 <b_jonas> I find this important because for a crypto hash of size n=256, you need 2**64 entries of storage instead of 2**128, and while 2**128 storage is something I can't imagine, 2**64 entries of storage is tantalizingly close to what Google could have in a few years if they really wanted to, whereas 2**128 entries of memory is something I can't imagine without our civilization being totally unrecognizable
23:41:14 <ais523> I assume it's O(2**(n/2)) because I've used it in practice to find a collision in SHA-256 truncated to 64 bits
23:41:26 <ais523> and that seems like it would take too long if it were O(2**64)
23:41:29 <int-e> ais523: It's expected to be O(2^(n/2)), but parallelizes badly (d parallel processes doing that end up taking O(2^(n/2)/sqrt(d)) time, I think)
23:41:49 <b_jonas> in particular, there's an estimate that all hard disk existing in year 2018 have a total capacity approximately 2**88 bits
23:41:59 <shachaf> You have a time/memory tradeoff that you can set however you want. There's no real reason to set it to the square root, is there?
23:42:19 <ais523> b_jonas: I can imagine 2**64 storage entries, however I can't imagine a system that can fill them in reasonable time
23:42:21 <b_jonas> and it's reasonable to assume that a large quantity of those hard disks are used by Google in their server rooms
23:42:25 <shachaf> You can set it based on how much storage you want to use.
23:42:31 <ais523> if these are random access and we assume we don't use most of them, it's believable
23:43:11 <b_jonas> ais523: yeah, it's still not a feasable attack yet, but the storage size is not the limit
23:43:19 <shachaf> fizzie: That's a pretty cute cat.
23:43:47 <b_jonas> shachaf: yes, it needn't be exactly the fourth root
23:43:54 <shachaf> The undithered version is a bit less cute.
23:44:18 <ais523> b_jonas: actually, I think Google almost certainly uses more than 2**-21 of the world's storage capacity, that's less than a millionth
23:44:29 <ais523> so Google probably had 2**64 bits of storage already in 2018
23:45:40 <int-e> ais523: https://crypto.stackexchange.com/questions/52231/what-is-the-best-and-fastest-algorithm-to-generate-a-hash-collision has some references
23:46:04 <b_jonas> ais523: yes, that's what I'm thinking too, but I also think 2**64 *bits* might not be enough, you need 2**64 half-entries, each 64 bits long, (or maybe quarter entries or so), so it's more like 2**70 bits
23:46:55 <b_jonas> but I'm not sure about either number here so I can't tell if Google has reached this yet
23:47:11 <fizzie> I'd check how much data is stored in [REDACTED], but it'd almost certainly be a confidential number.
23:47:45 <int-e> . o O ( so many [REDACTED] bytes )
23:48:10 <b_jonas> fizzie: yeah, though I've seen some estimates based on public data
23:48:47 <fizzie> It's pretty hard to find public information about that sort of thing, I think Amazon has also only publicly said how many *objects* there are in S3, not how many bytes.
23:49:45 <b_jonas> I was also wondering how many devices (smartphones) are there that run Android (2**31 right now, it turns out), and how much total GPU FLOPS, total CPU FLOPS, total storage, total RAM, and median RAM they have;
23:50:00 <shachaf> fizzie: I wonder how that changed since I had access to [REDACTED]
23:50:22 <fizzie> Well, curiosity got the better of me, and I checked [REDACTED]. I can in strictest confidence let you know it's still a number, it hasn't turned into any sort of weird concept that transcends numbers. Well, unless the interface hides that.
23:50:37 -!- salpynx has joined.
23:50:56 <b_jonas> though I do admit that an attack that backdoors a significant number of android devices such that it uses them for some meaningful computation would be very impractical.
23:51:12 <shachaf> Oh man, we should do some sort of millionaire problem.
23:51:14 <ais523> it wouldn't necessarily need to be a backdoor
23:51:16 <b_jonas> I was asking about this on another channel, but I haven't found out anyting other than the number of devices yet
23:51:41 <b_jonas> shachaf: yeah, that's what I was thinking of, to determine if the redacted problems are equal
23:51:59 <b_jonas> oh wait, you mean not whether the projects are the same but for which one uses more storage?
23:52:09 <ais523> there are apps that are installed on a high proportion of phones, if one of them decided to do some distributed computing (perhaps even with the users' permission) it could get a lot done
23:52:35 <fizzie> There was a ridiculous spike in capacity of Folding@home with the covid thing.
23:52:57 <fizzie> "With heightened interest in the project as a result of the COVID-19 pandemic,[7] the system achieved a speed of approximately 1.22 exaflops by late March 2020 and reaching 2.43 exaflops by April 12, 2020,[8] making it the world's first exaflop computing system."
23:53:20 <ais523> is exa one level above peta?
23:53:25 <b_jonas> ais523: yes, I know, but still it's hard to make them do a computation that does anything useful
23:53:49 <ais523> these are numbers so large that I find it hard to remember even what they're named
23:53:50 <fizzie> Exa is indeed one level above peta, and it's also the last level that sounds even borderline reasonable.
23:53:57 <fizzie> Because nobody's going to take zetta and yotta seriously.
23:54:06 <int-e> "IBM announced Thursday[don't you love such references in an online article without date] that after five years of work, its researchers have been able to reduce from about one million to 12 the number of atoms required to create a bit of data."
23:54:24 <b_jonas> ais523: yes, tera is 1000**4, peta is 1000**5, exa is 1000**6, zetta is 1000**7, yotta is 1000*8, the mnemonic is that the words are similar to tetra, penta, hexa, septa, octa
23:54:31 <b_jonas> with one consonant removed from each
23:54:44 <ais523> b_jonas: huh, was that intentional?
23:54:55 <ais523> it's a hard pattern to notice unless it's pointed out
23:55:30 <b_jonas> ais523: yeah, I didn't know it for a while and I kept confusing them all the time. I think it was intentional for at least for some of them, though perhaps not for tera
23:55:33 <ais523> and it doesn't generalize backwards, "giga" is nothing like "tri"
23:55:53 <int-e> well mega and giga are just large
23:55:53 <b_jonas> ais523: nor for the prefixes smaller than 1
23:56:01 <fizzie> I finally heard a mnemonic for stalactite/stalagmite that I can actually remember the other day: stalaGmites rise from the Ground, while stalaCtites hang from the Ceiling.
23:56:12 <b_jonas> int-e: and tera is like terra which is earth which is large... very helpful
23:56:17 <ais523> I learned that in school, I think
23:56:36 <fizzie> It doesn't work in Finnish, I'm sure they'd've told it to us too otherwise.
23:57:02 <b_jonas> fizzie: I didn't bother to remember the stalagmite thing, I don't do spelunking and will never do it in the future, so I don't think that nomenclature can ever matter for anything I do
23:57:17 <int-e> fizzie: statlacTITeS hang from the ceiling... that one works in german as well :P
23:57:34 <b_jonas> plus all my spelologist friends speak Hungarian and you can just use the Hungarian names which aren't so crazy
23:57:34 <int-e> (ignore the ceiling, it's all about hanging)
23:58:10 <b_jonas> they are combined from simple words and have obvious etimologies, just like rare words do in any sane language except English
23:58:14 <ais523> how many spelologist friends do you have?
23:58:18 <Arcorann> It's why people have proposed extending the prefixes with stuff like "xona"
23:58:25 <int-e> And I think I learned this as a teenager... not in school though, for some reason. :P
23:58:58 <b_jonas> ais523: depends on how you count "friend", they're all my mother's friends because she goes to caves a lot, although not as a spelologist, but as a teacher
23:58:59 <fizzie> int-e: Stephen Fry said the mnemonic he was taught in school was based on "tights hang down".
23:59:19 <fizzie> (This was in QI, which is where I got the ground/ceiling bit too.)
23:59:23 <Arcorann> I've heard a bunch of mnemonics, but I
23:59:33 <Arcorann> 'll always remember Hagrid in Harry Potter just failing
23:59:45 <esowiki> [[The Past]] https://esolangs.org/w/index.php?diff=76463&oldid=76129 * LegionMammal978 * (+253) fixed implementation
23:59:48 <int-e> Arcorann: aww, I was hoping for "I don't remember any of them"