01:52:30 -!- Lord_of_Life has quit (Ping timeout: 255 seconds).
01:54:28 -!- Lord_of_Life has joined.
01:56:13 -!- amby has quit (Quit: so long suckers! i rev up my motorcylce and create a huge cloud of smoke. when the cloud dissipates im lying completely dead on the pavement).
02:09:05 <esolangs> [[Macro]] N https://esolangs.org/w/index.php?oldid=123795 * BestCoder * (+333) Created page with "Macro is a programming language that uses macros to do computation = Macro = == Stuff to know == === Macro === a -> b #turn a to b === Selector === ~a ~b ~a -> ~b ~a ~b #turns something1 something2 something1 to something2 something1 something2 === Parenthesis === 5(4
02:10:07 <esolangs> [[Macro]] https://esolangs.org/w/index.php?diff=123796&oldid=123795 * BestCoder * (+58)
02:11:05 <esolangs> [[Brainfuck+2]] M https://esolangs.org/w/index.php?diff=123797&oldid=122777 * EvyLah * (+60) Brainfuck+3 was taken
05:41:12 <esolangs> [[Mode Spam]] M https://esolangs.org/w/index.php?diff=123798&oldid=123714 * EvyLah * (+0) hold on I forgot to change from I to O
05:42:05 <esolangs> [[Mode Spam]] M https://esolangs.org/w/index.php?diff=123799&oldid=123798 * EvyLah * (+127)
05:50:06 -!- Noisytoot has quit (Excess Flood).
05:52:57 <esolangs> [[Mode Spam]] https://esolangs.org/w/index.php?diff=123800&oldid=123799 * EvyLah * (-36) .
06:13:22 -!- Noisytoot has joined.
09:02:38 <esolangs> [[Brainfuck+3]] M https://esolangs.org/w/index.php?diff=123801&oldid=90631 * None1 * (+4) /* Implementations */
09:29:06 -!- Koen_ has joined.
10:13:02 <esolangs> [[Special:Log/newusers]] create * Artyxa * New user account
10:14:17 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=123802&oldid=123595 * Artyxa * (+48) /* Introductions */
10:14:55 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=123803&oldid=123192 * Artyxa * (+12)
10:16:54 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=123804&oldid=123803 * Artyxa * (+14)
10:19:22 <esolangs> [[Expansion]] N https://esolangs.org/w/index.php?oldid=123805 * None1 * (+2130) Created page with "{{lang|Expansion|a=User:None1}} ==Syntax== ''source_string1''=''target_string1'' ''source_string2''=''target_string2'' ... ''source_stringn''=''target_stringn'' *''memory_string'' Every source string must be surrounded by square brackets, and except the beginning a
10:23:35 <esolangs> [[Expansion]] https://esolangs.org/w/index.php?diff=123806&oldid=123805 * None1 * (+306)
10:23:59 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=123807&oldid=123736 * None1 * (+16) /* E */
10:26:25 -!- tromp has joined.
10:26:37 <esolangs> [[User:None1]] https://esolangs.org/w/index.php?diff=123808&oldid=123638 * None1 * (+52) /* My Esolangs */
10:26:55 <esolangs> [[User:None1]] M https://esolangs.org/w/index.php?diff=123809&oldid=123808 * None1 * (+1) /* My Esolangs */
11:06:34 <esolangs> [[Special:Log/newusers]] create * KalDima * New user account
11:11:27 -!- tromp has quit (Read error: Connection reset by peer).
11:20:54 -!- amby has joined.
11:22:06 -!- amby has quit (Remote host closed the connection).
11:22:56 -!- Sgeo has quit (Read error: Connection reset by peer).
11:23:24 -!- amby has joined.
11:28:01 -!- wib_jonas has joined.
11:30:39 <wib_jonas> so you know there's this famous algorithm that you can use to detect if a linked list is looping, without using extra storage: have two iterators traversing the list, but one of them at double speed by stepping it twice each time you step the slow one, compare them after each step, if they ever become equal again after the start then there's a
11:31:23 <wib_jonas> but yesterday I learned that there's a more complete version of this, which you can use to find the first element that's part of the loop, and this one seems magical to me, it sounds like there's no way it should work.
11:34:22 <wib_jonas> so you just traverse with two pointers from the start, stepping the second one twice each time, like { x = y = begin; do { x++; y++; y++; } while (x != y); } then once they're equal start stepping them slow but also step a third pointer from the start, and compare after each step, like { z = begin; while (x != z) { x++; z++; } } and when they're
11:34:22 <wib_jonas> first equal they'll magically point to the first element of the loop.
11:34:51 <wib_jonas> have you heard of this algorithm? I expect some of you have. do you find it magical, like a weird coincidence that this happens to work?
11:53:10 -!- __monty__ has joined.
11:56:02 -!- FreeFull has joined.
13:01:26 <esolangs> [["quote]] N https://esolangs.org/w/index.php?oldid=123810 * Cleverxia * (+8591) Created page with "<nowiki>"quote is an esolang that can only do inputs, prints and repetition. </nowiki> ==Commands== <code>"..."</code> prints the quoted things. <code>q</code> does the escaping (<code>q"</code> is character <code>"</code>, <code>qn</code> is newline). <code>u</code
13:03:35 <esolangs> [[User:Cleverxia]] https://esolangs.org/w/index.php?diff=123811&oldid=123525 * Cleverxia * (+36) /* Current Esolangs I've created */
13:04:24 <esolangs> [["quote]] https://esolangs.org/w/index.php?diff=123812&oldid=123810 * Cleverxia * (+66)
13:33:53 -!- tromp has joined.
14:19:19 -!- craigo has joined.
14:30:16 -!- GregorR has quit (Quit: Ping timeout (120 seconds)).
14:30:26 -!- GregorR has joined.
14:43:03 -!- GregorR has quit (Ping timeout: 268 seconds).
14:43:21 -!- GregorR has joined.
15:10:30 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
15:10:52 <esolangs> [[Buttons]] N https://esolangs.org/w/index.php?oldid=123813 * AnotherUser05 * (+72) Created page with "{{WIP}} '''Buttons''' is a 2D esolang created by [[User:AnotherUser05]]."
15:14:55 -!- tromp has joined.
16:02:47 <esolangs> [[Buttons]] https://esolangs.org/w/index.php?diff=123814&oldid=123813 * AnotherUser05 * (+1148)
16:03:13 <esolangs> [[User:AnotherUser05]] https://esolangs.org/w/index.php?diff=123815&oldid=123772 * AnotherUser05 * (+14) /* B */
16:03:38 <esolangs> [[GolfSpace]] M https://esolangs.org/w/index.php?diff=123816&oldid=68257 * PythonshellDebugwindow * (+83) Categories
16:04:01 -!- craigo has quit (Ping timeout: 264 seconds).
16:17:21 <esolangs> [[4est]] https://esolangs.org/w/index.php?diff=123817&oldid=118833 * BoundedBeans * (+3) Fixed example of ^Preprocess
16:22:14 <esolangs> [[4est]] https://esolangs.org/w/index.php?diff=123818&oldid=123817 * BoundedBeans * (+131) Added NLEscapeDelayStart(,->,<-), renamed NLEscapeDelayStart to NLEscapeDelayStart<->
16:29:59 -!- __monty__ has quit (Ping timeout: 264 seconds).
16:45:32 -!- amby has quit (Remote host closed the connection).
17:08:52 -!- craigo has joined.
17:15:26 -!- Thelie has joined.
17:19:26 -!- wib_jonas has quit (Quit: Client closed).
17:41:49 -!- Thelie has quit (Ping timeout: 256 seconds).
17:54:33 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
18:11:02 -!- tromp has joined.
18:37:14 -!- Joao[3] has joined.
18:39:15 -!- Sgeo has joined.
18:51:54 <esolangs> [[Esolang:Sandbox]] https://esolangs.org/w/index.php?diff=123819&oldid=123804 * Artyxa * (+3)
18:55:02 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
18:55:31 <esolangs> [[Esolang:Sandbox]] M https://esolangs.org/w/index.php?diff=123820&oldid=123819 * Artyxa * (+130)
18:59:08 -!- tromp has joined.
19:37:44 -!- Koen_ has quit (Remote host closed the connection).
19:40:24 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
19:41:03 -!- benji has quit (Quit: ZNC - https://znc.in).
19:41:53 -!- benji has joined.
19:42:58 -!- tromp has joined.
20:05:05 <esolangs> [[Buttons]] M https://esolangs.org/w/index.php?diff=123821&oldid=123814 * AnotherUser05 * (+1) /* Syntax */
20:06:06 <esolangs> [[Buttons]] M https://esolangs.org/w/index.php?diff=123822&oldid=123821 * AnotherUser05 * (+5) /* Syntax */
20:07:22 -!- Thelie has joined.
20:10:21 <esolangs> [[Buttons]] M https://esolangs.org/w/index.php?diff=123823&oldid=123822 * AnotherUser05 * (-68) /* Cat Program */
20:15:00 <esolangs> [[Buttons]] https://esolangs.org/w/index.php?diff=123824&oldid=123823 * AnotherUser05 * (+60) /* Syntax */
20:15:38 <esolangs> [[Buttons]] https://esolangs.org/w/index.php?diff=123825&oldid=123824 * AnotherUser05 * (+20) /* Cat Program */
20:26:32 -!- ais523 has joined.
20:26:41 <ais523> b_jonas: I'd heard of it but couldn't remember the details
20:27:26 -!- amby has joined.
20:28:22 <ais523> but it isn't very surprising that it works: the distance that each of the first two pointers move before they meet has to be a multiple of the cycle length, so starting another pointer at that time puts the pointer a multiple of cycle lengths apart, and thus they'll always be at the same place whenever they're both on the cycle
20:28:55 <ais523> because they obviously can't be in the same place when they aren't on the cycle, that means that the instant they first meet will be the instant the cycle starts
20:29:21 <int-e> when a cycle is detected, slow is at index n, and fast is at index 2n, and the cycle length divides n... so you're starting at 0 again and at will check ahead by a multiple of the cycle length.
20:29:32 <int-e> as for names... tortoise and hare?
20:29:55 <ais523> the same algorithm has more than one common name
20:30:01 <ais523> tortoise and hare algorithm is one of them
20:32:59 <ais523> I used it at work once, because I needed to test some code that had a special case when there was a hash collision in the first 64 bits of a cryptographic hash
20:33:27 <shachaf> I remember someone used this algorithm to find hash collisions and it surprised me for a bit at first.
20:33:28 <esolangs> [[Spin4]] https://esolangs.org/w/index.php?diff=123826&oldid=123605 * Michael * (+20)
20:33:51 <ais523> so I needed a test case for that, i.e. a 64-bit collision against a sound hash function – that means trying around 4 billion possibilities and that's within range for brute force on a modern computer
20:33:56 <shachaf> So you have f^n(0) = f^2n(0)
20:34:05 <ais523> and the memory-efficient way to do it is to just iterate hashes until you find a repeat
20:34:11 <shachaf> But the latter is also f^n(f^n(0))
20:34:29 <shachaf> I think that's the core of it maybe?
20:34:53 <ais523> yep, the idea is that you start with something that isn't a valid output from the hash function (but is a valid input)
20:35:06 <shachaf> If you take n steps from 0 you'll reach the same point as if you take n steps from f^n(0)
20:35:18 <shachaf> So you can do it one at a time until you see the collision.
20:35:22 <ais523> so once you see the same hash twice, it's guaranteed that at least two copies of it came from different preimages
20:35:53 <shachaf> In practice I think the distinguished point method is usually much better.
20:36:09 <shachaf> Also typing all this on a phone keyboard is awful
20:36:13 <ais523> well, it worked (and the search didn't even take that long)
20:36:18 <int-e> shachaf: sure, mostly because it can be parallelized
20:36:58 <shachaf> int-e: Right, though it also doesn't require as many computations of the function.
20:37:06 <int-e> (it's for collisions, of course... not cycles) lambdas vs. rhos...
20:37:21 -!- ais523 has quit (Quit: quit).
20:37:41 <shachaf> Right, if you want a cycle I guess it's harder to parallelize!
20:37:46 <int-e> shachaf: right but that's a small constant factor. the parallelization is the more important win.
20:39:19 <int-e> Anyway I suspect we discussed all this at length a few years ago in the context of maybe breaking Data.Typeable? But 2^64 hashes just isn't a casual project, and the fast differential attacks don't seem to apply.
20:40:34 <shachaf> Man, how expensive are 2^64 hashes on modern GPUs?
20:42:57 <int-e> dunno, here's a data point: https://gist.github.com/Chick3nman/e1417339accfbb0b040bcd0a0a9c6d54#file-h100_pcie_v6-2-6-benchmark-L33
20:43:27 <int-e> 6.7 years of that... enjoy
20:47:46 <shachaf> Apparently that GPU only costs a few tens of thousands of dollars.
20:47:58 <int-e> That seems too slow actually... my 1060 reports 13147 MH/s.
20:52:57 <b_jonas> *nod* yes, all those things you say above
20:53:18 <int-e> or maybe the H100 just sucks for integer arithmetic
20:53:53 <int-e> I see a report for 3080 where it's 54940.5 MH/s
20:55:03 <int-e> anyway... even if it were 10 times faster it still wouldn't quite be a hobby project :P
20:56:28 <shachaf> I think my friend has a few 3090s he's not really using right now.
20:57:16 <shachaf> But I guess that's not really enough.
20:59:20 <shachaf> How much does a 3080 year cost?
21:00:23 <shachaf> Not going to compute it on my phone, but it sounds like you'd need ~10 of them?
21:01:00 <int-e> To do this in a year? Yeah it's in that ballpark. There's a lot of uncertainty of course because hashcat is not looking for collisions.
21:01:24 <shachaf> You'd need 10 GPU years, I mean.
21:02:10 <int-e> But it can easily be off by a factor of 2, maybe even 3.
21:03:04 <int-e> (Our f() has to re-encode a hash as UTF-32 made up of identifier friendly letters somehow. And probably has to hash 2 blocks...)
21:03:38 <shachaf> Sounds like a 5-figure project probably?
21:04:28 <shachaf> That's a bit much just to be able to comment on my bug report telling them to switch to another hash.
21:04:34 <b_jonas> is this something that can just be changed in a later ghc version? or does ghc come with some strong cross-version binary compatibility guarantees that make that hard?
21:04:53 <int-e> nah they can just change this
21:05:15 <int-e> ghc doesn't even have ABI guarantees for the same library compiled twice by the same compiler
21:06:50 <b_jonas> int-e: ok, but maybe they also have some kind of serialization thing for writing data into a file and the format for that needs to stay compatible, at least in the sense that it can read back existing files
21:07:06 <shachaf> On the previous topic, there's also another algorithm for finding cycles that's supposed to be better, right?
21:07:31 <shachaf> Better than the tortoise and hare one, I mean.
21:08:03 <int-e> shachaf: there's a version that uses exponential backup, checking f(2^n) = f(2^n + k) for 0 < k < 2^n. (different f)
21:08:05 <b_jonas> shachaf: sure, if the stepping is expensive then store some or all the elements that you encounter in a hash table and look the new ones you meet
21:08:23 <b_jonas> but even that can only save time by a constant factor
21:12:55 <shachaf> It's kind of funny that people call the distinguished point algorithm "Pollard's Rho", given that it doesn't find a Rho, and that Pollard's original algorithm isn't able to use distinguished points.
21:13:54 <int-e> shachaf: I've seen the letter lambda being used (the picture being that you have two strands of iterated f-s that merge together)
21:16:56 <shachaf> Yes, I think that's better.
22:12:22 -!- PoserKiller has joined.
22:18:21 -!- Koen_ has joined.
22:27:20 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
22:45:28 -!- craigo has quit (Quit: Leaving).
23:03:44 -!- hppavilion[1] has joined.
23:10:26 -!- Thelie has quit (Quit: Leaving.).
23:16:39 <esolangs> [[Macro]] M https://esolangs.org/w/index.php?diff=123827&oldid=123796 * None1 * (+23)
23:18:29 -!- PoserKiller has quit (Quit: Client closed).
23:23:52 <esolangs> [[Hello world program in esoteric languages (nonalphabetic and A-M)]] https://esolangs.org/w/index.php?diff=123828&oldid=123561 * None1 * (+34) /* Exp */
23:50:28 <esolangs> [[Special:Log/newusers]] create * Kleinesfilmrllchen * New user account
23:58:49 <esolangs> [[Velato]] https://esolangs.org/w/index.php?diff=123829&oldid=123692 * Rottytooth * (+55) /* Commands */
23:59:29 <esolangs> [[Velato]] https://esolangs.org/w/index.php?diff=123830&oldid=123829 * Rottytooth * (-1) /* Commands */