Who is John Quarmack?

In the Quake III Arena source code, there’s a famous code snippet:

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
	assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
	return y;
}

This code’s got it all. It’s got bit twiddling. It’s got secret calculus. It’s got cursing and confusion in the comments, naming “threehalfs” while not naming 0x5f35759df and, best of all, blatant violation of strict aliasing. I hate strict aliasing, and I love this code.

Sometimes I see this code attributed to legendary programmer John Carmack, but he’s on the record stating that he didn’t write it:

-----Original Message-----
From: John Carmack
Sent: 26 April 2004 19:51
Subject: Re: Origin of fast approximated inverse square root

At 06:38 PM 4/26/2004 +0100, you wrote:

>Hi John,
>
>There's a discussion on Beyond3D.com's forums about who the author of 
>the following is:
>
>float InvSqrt (float x){
>   float xhalf = 0.5f*x;
>   int i = *(int*)&x;
>   i = 0x5f3759df - (i>>1);
>   x = *(float*)&i;
>   x = x*(1.5f - xhalf*x*x);
>   return x;
>}
>
>Is that something we can attribute to you?  Analysis shows it to be
>extremely clever in its method and supposedly from the Q3 source.  
>Most people say it's your work, a few say it's Michael Abrash's.  Do 
>you know who's responsible, possibly with a history of sorts?


Not me, and I don't think it is Michael.  Terje Matheson perhaps?

John Carmack         

…but I digress. Why am I talking about this snippet?

Back in the late 90s, when the above code was written, games had to pull these kinds of shenanigans to get the performance they needed. Nowadays we have dedicated processor instructions that are faster and more accurate than the above snippet (e.g. see _mm256_rsqrt_ps in the intel intrinsics guide). There’s little room for these particular shenanigans.

…but what about quantum computers?

A key potential application of quantum computers is chemistry simulation. There’s a variety of ways of doing these simulations, but one popular way involves the computer storing $x$, $y$, and $z$ coordinates for each particle. In that style of simulation, something the computer needs to repeatedly compute is the eletric potential between particles:

\[V_E = \frac{Q}{r} \frac{1}{4\pi\epsilon_0}\]

I’m not a chemist. I can’t explain the intricacies implied by the above equation (nevermind the scarier ones they put in papers). But I understand that $r$ is the distance between two particles, and the square of the distance is the sum of the squares of the coordinate differences. Which implies…

\[V_e \propto \sqrt{\frac{1}{s}}, s = x^2 + y^2 + z^2\]

…this crucial chemistry calculation uses an inverse square root. Meaning that if you improve inverse square root calculations, you improve quantum chemistry simulations. More broadly, you don’t have to understand quantum chemistry to contribute to quantum chemistry simulation (trust me, I know).

Anyways, about that inverse square root. Technically I’m oversimplifying when I say the simulation has to compute it. That’s certainly sufficient but, strictly speaking, the simulations only need to phase by an amount proportional to the inverse square root. There’s a whole world of potential shenanigans that could achieve that effect without explicitely producing the inverse square root. And a true Quarmack would— oh wait, I haven’t explained the terrible pun in the title.

You probably noticed that the title of this post says John Quarmack (pronounced like “kwar-mak”, obviously). John Quarmack is not John Carmack. John Carmack is a legendary video game programmer (…who hopefully won’t be upset at my punnery). John Quarmack is an inside joke; a made up character whose defining attribute is being amazing at quantum circuits. A mythical being who can do to the quantum inverse square root what John Carmack didn’t do to the classical one.

Pragmatically, someone has to turn the quantum inverse square root into a pile of disgusting hacks. And, in my mind, whoever that is; that’s Quarmack. In fact, if you’re feeling particularly Quarmacky, the Google quantum team happens to be running a public Kaggle competition to improve the quantum inverse square root (and also a few other subroutines). There’s a 50K$ prize for first place.

This competition was triggered by seeing all the public improvements being made to elliptic curve circuits by amateurs (and their LLMs) over at ecdsa.fail. There’s clearly a lot of untapped potential out there in the world. Nascent Quarmacks, waiting to shine.

Who is John Quarmack…?

Maybe you’re John Quarmack.