Going Old School

While looking for optimization opportunities in various parts of Jetpack Compose, I recently discovered that calling the cube root function was taking a non-neligible amount of times in two areas of the Toolkit: when evaluating cubic Bézier easing curves and when interpolating colors through the OkLab color space.

Working on graphics projects taught me that approximations can often be powerful optimization tools, so I decided to come up with an approximation of cbrt()¹:

1fun fastCbrt(x: Float): Float {
2    val v = x.toRawBits().toLong() and 0x1ffffffffL
3    var estimate = floatFromBits(0x2a510554 + (v / 3).toInt())
4    estimate -= (estimate - x / (estimate * estimate)) * (1.0f / 3.0f)
5    estimate -= (estimate - x / (estimate * estimate)) * (1.0f / 3.0f)
6    return estimate
7}

This approximation provides good accuracy (for instance the maximum error in the range 0..1 is 5.96E-7) and decent performance improvements:

• Color interpolation is 8% faster
• 2D animations using cubic easing curves are 17% faster

The technique used in the snippet above is the same that was used in the now famous fast inverse square root of Quake III Arena². There are two steps to this algorithm:

• Guess a solution by treating the integer representation of a float as a logarithmic space. In log space, the cube root becomes a simple multiplication.
• Refine the solution using the Newton-Rhapson method. The implementation above does 2 rounds.

If you want a longer explanation of the technique, and a precise explanation of how 0x2a510554 was derived, please refer to the implementation of fastCbrt() in Compose where you will find a long comment that explains everything.

This technique can easily be generalized to work with any power. For instance, if we needed to find a fast approximation for the inverse cube root, we would need to derive a new magic constant and adjust the Newton-Rhapson steps.