Improve the accuracy of fastCbrt()
Using brute-force numerical methods, we can find a better magic
constant for fastCbrt(). This new constant improves the max
error across various ranges:
- 8.3446500E-7 -> 5.9604645E-7 in the range -1f..1f
- 6.6757200E-6 -> 4.7683716E-6 in the range -256f..256f
- 1.0681152E-4 -> 3.8146973E-5 in the range -65_536f..65_536f
- 2.1362305E-4 -> 1.5258789E-4 in the range -16_777_216..16_777_216f
Test: MathHelpersTest.kt
RelNote: N/A
Change-Id: I1149d7c77fe1e770eb20a2169ea655fdc02cf72e
diff --git a/compose/ui/ui-util/src/androidUnitTest/kotlin/androidx/compose/ui/util/MathHelpersTest.kt b/compose/ui/ui-util/src/androidUnitTest/kotlin/androidx/compose/ui/util/MathHelpersTest.kt
index ab429d6..cfa2ead 100644
--- a/compose/ui/ui-util/src/androidUnitTest/kotlin/androidx/compose/ui/util/MathHelpersTest.kt
+++ b/compose/ui/ui-util/src/androidUnitTest/kotlin/androidx/compose/ui/util/MathHelpersTest.kt
@@ -28,8 +28,8 @@
class MathHelpersTest {
// `f = 16777216f` is the first value where `f + 1 == f` due to float imprecision, so that's
// where testing floating point errors becomes interesting
- val testStart = 16777216L
- val testEnd = testStart + 1000
+ private val testStart = 16777216L
+ private val testEnd = testStart + 1000
@Test
fun testLerpLargeFloats() {
@@ -118,14 +118,14 @@
@Test
fun testZeroFastCbrt() {
- val zeroError = 8.35E-7f
+ val zeroError = 5.97E-7f
assertTrue(fastCbrt(0.0f) <= zeroError)
assertTrue(fastCbrt(-0.0f) >= -zeroError)
}
@Test
fun testFastCbrtError() {
- val maxError = 1.76E-6f
+ val maxError = 1.193E-6f
for (i in 0..65_536) {
val v = i / 8_192.0f // v is in the range 0f..8f
val error = abs(fastCbrt(v) - cbrt(v))
diff --git a/compose/ui/ui-util/src/commonMain/kotlin/androidx/compose/ui/util/MathHelpers.kt b/compose/ui/ui-util/src/commonMain/kotlin/androidx/compose/ui/util/MathHelpers.kt
index b96decc..3b08ee1 100644
--- a/compose/ui/ui-util/src/commonMain/kotlin/androidx/compose/ui/util/MathHelpers.kt
+++ b/compose/ui/ui-util/src/commonMain/kotlin/androidx/compose/ui/util/MathHelpers.kt
@@ -123,10 +123,10 @@
* - Zero, returns a value close to 0 (~8.3e-14) with the same sign
*
* The maximum error compared to [kotlin.math.cbrt] is:
- * - 8.3446500E-7 in the range -1f..1f
- * - 6.6757200E-6 in the range -256f..256f
- * - 1.0681152E-4 in the range -65_536f..65_536f
- * - 2.1362305E-4 in the range -16_777_216..16_777_216f
+ * - 5.9604645E-7 in the range -1f..1f
+ * - 4.7683716E-6 in the range -256f..256f
+ * - 3.8146973E-5 in the range -65_536f..65_536f
+ * - 1.5258789E-4 in the range -16_777_216..16_777_216f
*/
fun fastCbrt(x: Float): Float {
// Our fast cube root approximation is implemented using the binary
@@ -219,20 +219,18 @@
// Rhapson method. One round proved not precise enough for our needs, and
// more rounds don't improve the results significantly given our use cases.
//
- // Note: the constant 0x2a555555 we computed earlier is only a standalone
+ // Note: the constant 0x2a555555 we computed above is only a standalone
// approximation that doesn't account for the subsequent Newton-Rhapson
// refinements. The approximation can be improved for Newton-Rhapson by
- // debiasing it. To debias 0x2a555555 we follow the solution used by the
- // now famous "Quake 3 inverse square root". Instead of using 0x5f400000
- // as the "magic constant" (following our derivation above, you can compute
- // the constant for an inverse square root using (1 - -1/2) * I(1)), the
- // Quake 3 solution uses 0x5f3759df. To improve our constant we simply
- // apply the same ratio:
- //
- // magic = 0x2a555555 * 0x5f3759df / 0x5f400000
- // = 0x2a517d40
+ // debiasing it. To debias 0x2a555555, we just use a brute-force method to
+ // minimize the error between cbrt() and this function. Doing so gives us
+ // a new constant, 0x2a510554L, which greatly improves the maximum error:
+ // - 6.2584877E-6 -> 5.9604645E-7 in the range -1f..1f
+ // - 5.0067900E-5 -> 4.7683716E-6 in the range -256f..256f
+ // - 4.0054320E-4 -> 3.8146973E-5 in the range -65_536f..65_536f
+ // - 1.6021729E-3 -> 1.5258789E-4 in the range -16_777_216..16_777_216f
val v = x.toRawBits().toLong() and 0x1ffffffffL
- var estimate = floatFromBits((0x2a517d40L + v / 3).toInt())
+ var estimate = floatFromBits((0x2a510554L + v / 3).toInt())
// 2 rounds of the Newton-Rhapson method to improve accuracy
estimate -= (estimate - x / (estimate * estimate)) * (1.0f / 3.0f)
