What are some tricks and black magics you know?

Question

It could be anything that does a particular task but if you were to show it to someone that had never seen it they would be very surprised. Currently my favourite is the fast inverse square root, most popular example of it being used in quake. Particularly like it because of the magic number that's used in it. The source code in quake arena had a comment next to it saying "what the f***?" next to the line with the number. But the number could be any other, it's just there to minimize the error.

Answer 1

Stanford bit twiddling hacks:

http://www.graphics.stanford.edu/~seander/bithacks.html

I use a variation of binary population count from the AMD source in a couple codes:

https://code.sololearn.com/cpogCPP6rG33/?ref=app
https://code.sololearn.com/cZX2I8giW2zV/?ref=app

Answer 2

Here's an algorithm that produces the digits of pi digit by digit, in Haskell:

pi_spigot = g (1,0,1,1,3,3) where
g (q,r,t,k,n,l) = if 4*q+r-t < n*t then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l) else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

It completely blows my mind that you can even do that without some errors eventually sneaking in, and I still don't really get what's going on even though I have used it on occasion.

There's a paper about it [1], but I haven't worked through it to be honest.

Here it is in action: https://tio.run/##PU9LCsIwEN33FG/hIkmn0I8giJ5FCsY2JMY2HfT4cRpEBt5i3m9mHjdvQ8h5cbdtcdOLccUE1VFLncxAg8ZntslW2PcrJWLyFCloUboHjmatU8O4IBoGzzYi4lwyWrMSBFVqhNMEJnjC3b0LqYbdqjUYzS6LBAm1YbOlyYhU9UVignh38HX3869GnYyve10nIy4ltBQEWVTVc3RRjluSi4wDePRW8lv8f8z5Cw

[1] S. Rabinowitz and S. Wagon, A spigot algorithm for the digits of π, Amer. Math. Monthly 102 (1995) 195–203.