mlochbaum

7 ms·

1.
by mlochbaum 4mo ago
This is one of the best uses I've found for Singeli[0]. Here's how I implemented an AVX2 transpose kernel similar to that in transpose_Vec256_kernel, for generic type and vector/kernel size (I use unpack instructions rather t
2.
by mlochbaum 4mo ago
It's possible to get O(N^(3/2)/log N) in an ordinary interpreter with some changes to the code, assuming linear-time ~ with hashing. The idea is to leave the primes in ⍵ and stop when it stops changing, which will happen at t
3.
by mlochbaum 4mo ago
That's not O(N log log N), it's more like N^2. Prime sieves are hard to implement well with immutable arrays for obvious reasons; there are some cool methods but they're definitely harder. I'm ashamed to be part of a com
4.
by mlochbaum 5mo ago
It's very strange to see handwriting lumped in with typewriting, to be described as limited relative to screens! Iverson notation was a 2D format (both in handwriting and typeset publications) making use of superscripts, subscripts,
5.
by mlochbaum 6mo ago
I don't think this really describes neon_prefixsum_fast as a whole? The algorithm does use a Hillis-Steele sum on sums of 4 values, but each of these is computed with a sequential sum, interleaving those with a transposed order. In ter
6.
by mlochbaum 7mo ago
More on not being able to find π, as I'm piecing it together: given only the field structure, you can't construct an equation identifying π or even narrowing it down, because if π is the only free variable then it will work out to
7.
by mlochbaum 7mo ago
I was interested in how it would make sense to define complex numbers without fixing the reals, but I'm not terribly convinced by the method here. It seemed kind of suspect that you'd reduce the complex numbers purely to its field
8.
by mlochbaum 8mo ago
Ooh, I've run into this one before! I'm a big fan of interval index[0], which performs a binary search, so Josh's suggestion is the one I prefer as well (the implementation might sometimes optimize by transforming it into a t
9.
by mlochbaum 9mo ago
It was the subject of quite some debate, see "Panel: Is J a Dialect of APL?" at http://www.jsoftware.com/papers/Vector_8_2_BarmanCamacho.pdf . Ken and Roger backed off this stance after witnessing the controv
10.
by mlochbaum 11mo ago
I think the article expresses no position. Most source code for array languages is not, in fact, inspired by APL. I encourage you to check a few random entries at [0]; Kap and April are some particularly wordy implementations, and even A+ m
11.
by mlochbaum 11mo ago
Dunno why electroly is dragging me into this but I believe you've misread the article. When it says "His languages take significantly after APL" it means the languages themselves and not their implementations.
12.
by mlochbaum 11mo ago
It looks like a weirdo C convention to APLers too though. Whitney writes K that way, but single-line functions in particular aren't used a lot in production APL, and weren't even possible before dfns were introduced (the classic
13.
by mlochbaum 1y ago
Ordinarily I'd make fun of the Germans for giving such an ugly name to a nice concept, but I've always found "comfortable" to be rather unpleasant too (the root "comfort" is fine).
14.
by mlochbaum 1y ago
It's just. So gross. Say it. Sudden interruption of slime coming up your throat. Like walking out the door into a spiderweb. Alphabetically I was mistaken but in every way that matters I was right.
15.
by mlochbaum 1y ago
Well, do you know how it works? Don't judge a book by its cover and all. Although none of these are entirely aiming for elegance. The first is code golf and the other two have some performance hacks that I doubt are even good any more,
16.
by mlochbaum 1y ago
The point that the article is addressing (but you have to ignore the image and study the equations to see this!) is that this sort of shifting can't equalize everything. In the span of 3 white keys C to E at the front, you have 2 black
17.
by mlochbaum 1y ago
And the reason +˝ is fairly fast for long rows, despite that page claiming no optimizations, is that ˝ is defined to split its argument into cells, e.g. rows of a matrix, and apply + with those as arguments. So + is able to apply its ordina
18.
by mlochbaum 1y ago
The relevant operations for matrix multiply are leading-axis extension, shown near the end of [0], and Insert +˝ shown in [1]. Both for floats; the leading-axis operation is × but it's the same speed as + with floating-point SIMD. We d
19.
by mlochbaum 1y ago
To be clear, you are referring to the preface to "An Introduction to Array Programming in Klong", right? Having just checked it, I find this to be a very strange angle of attack, because that section is almost exclusively about wh
20.
by mlochbaum 1y ago
Oddly enough, the biggest mistake in how I presented BQN early on was thinking only APL insiders would be interested, when in fact the APLers went back to APL and people who hadn't tried other array languages or hadn't gotten far
21.
by mlochbaum 1y ago
Search for "teaching" at https://aplwiki.com/wiki/APL_conference . I count at least five papers about teaching non-APL topics using APL. The language is not only possible to read, it's designed for it.
22.
by mlochbaum 1y ago
"already": APL dates back to about 1966, and even K from 1993 predates Numpy and Julia. But yes, we do not live in caves and are familiar with these languages. Klong has even been implemented in Numpy, see https://githu
23.
by mlochbaum 1y ago
Author of BQN here, I agree with how section "What about APL?" describes the APL family as not fundamentally better (although details like indexing are often less messy). I outlined a system with lexically-scoped named axes at ht
24.
by mlochbaum 2y ago
The queue method is popular, but there's a much faster (branch-free) and in my opinion simpler way, known as the van Herk/Gil-Werman algorithm in image processing. It splits the input into windows and pairs up a backward scan on o
25.
by mlochbaum 2y ago
I'd forgotten about patience sorting! Not that I was ever exactly familiar with it. JesseSort seems nearly identical, except that it allows insertion to either side of the lists, tries the previous index before doing a binary search, a
26.
by mlochbaum 2y ago
Whoa, hey Tim! Very much agree on no "best" sorting algorithm. The generic-comparison case is one I keep idly considering, although more focused on long lists than short ones. There's been a lot of improvement lately in sorti
27.
by mlochbaum 2y ago
Ah, the README prior to commit b98f724 does claim O(n log(1.5 ln(n))) asymptotic runtime. This is based on a flawed analysis assuming rainbow endpoints will be evenly distributed, which the paper presents before describing the problem that
28.
by mlochbaum 2y ago
The analysis would make a lot more sense if it dropped every big O and computed an expected number of comparisons. Of course, the real issue is that the whole thing relies on an empirically-determined length of √8√n for the number of lists
29.
by mlochbaum 2y ago
So the idea is that you'll eventually arrange n elements into ideally about √n sorted lists, organized so that the endpoints of these lists are also ordered (the "rainbow" shape). A new element goes on the end of one of those
30.
by mlochbaum 2y ago
All right, just threw me off a little that you'd consider speculating or backwards decoding as I wouldn't expect them to be easier, or significantly faster (or maybe you consider parity-independence to be speculation? I can see it

More ›