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
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^{2}. 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.

`floatFromBits()`

is not a Kotlin API, but it does what`Float.fromBits()`

does. I’ll explain why in a future post. ↩︎Quake III Arena was released in 1999. ↩︎