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()1:

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

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 Arena2. 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.

  1. floatFromBits() is not a Kotlin API, but it does what Float.fromBits() does. I’ll explain why in a future post. ↩︎

  2. Quake III Arena was released in 1999. ↩︎