41–43 of 43 posts
Nice to see this getting the Jupyter Notebook treatment. The original book was already one of the better introductions to APL. Interactive examples make a huge difference for a language where half the learning curve is just building muscle memory with the symbols
Earlier quoted context omitted.
> At some point you get what APL is all about, and you can move on with life without too many regrets. Unfortunately, this seems to be a common experience. A lot of smart people only engage with APL via toy puzzles, like you did, and bounce off because that gives no insight about how to use the language in real life. IME, to really start getting APL you need to write and rewrite a full application 20 times. It helps…
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 community that won't cop to this. The algorithm iterates over numbers ⍺ from 2 to N, removing the multiples that are greater than ⍺ and no greater than N from p. If the removal with ~ has to inspect all…
It's a tad tricky to carefully analyze the asymptotics of my above prime generator, since the search space of Without (~) shrinks on each iteration. I think Merten's theorem gives an estimate of e^-γ/log(p_i), which we need to sum for all primes up to N. Taking prime density 1/log(n) and integrating N/(log x)^2 over our range is O(N^2/log N), I think.
> Mutating a bit array in place is pretty important to classical sieve performance.
Challenge accepted:
p⊣{x[⍵+n×⍳⌊N÷n←p⍪←x[⍵]]←0 ⋄ 1+⍣{(x⍪1)[⍵+1]≠0}⊢⍵}⍣{⍵=N-2}0⊣x p←(1↓1+⍳N)⍬