Реализация быстрого алгоритма обратного квадратного корня в Go (и JS)
Быстрый обратный квадратный корень — это алгоритм, который использует несколько сокращений для быстрого вычисления оценки 1 ⁄ √x
(обратного квадратного корня).
Он использует стандартное представление чисел с плавающей запятой IEEE 754 в памяти, чтобы избежать деления и итерации для получения ответа, вместо этого используя простые манипуляции с битами, вычитание и магическое число.
Почему?
Обратный квадратный корень широко используется в векторной математике и компьютерной графике для вычисления нормалей и углов, для освещения, затенения и многих других. Вычисление обратного квадратного корня может быть дорогостоящим, метод быстрого обратного квадратного корня является достаточно точной и дешевой альтернативой.
Этот метод прославился благодаря тому, что Джон Кармак использовал его в Quake III Arena, но он был популярен в индустрии компьютерной графики за несколько лет до Q3A.
Хорошо, давай
0x5F3759DF было исходным магическим числом для 32-битных чисел с плавающей запятой, по-видимому, обнаруженным методом проб и ошибок и уточненным до 0x5F375A86 Крисом Ломонтом.
0x5FE6EB50C7B537A9 — это магическое число для 64-битных чисел с плавающей запятой, обнаруженное позже Мэтью Робертсоном.
32-битный алгоритм
import "math" const magic32 = 0x5F375A86 func FastInvSqrt32(n float32) float32 { // If n is negative return NaN if n < 0 { return float32(math.NaN()) } // n2 and th are for one iteration of Newton's method later n2, th := n*0.5, float32(1.5) // Use math.Float32bits to represent the float32, n, as // an uint32 without modification. b := math.Float32bits(n) // Use the new uint32 view of the float32 to shift the bits // of the float32 1 to the right, chopping off 1 bit from // the fraction part of the float32. b = magic32 - (b >> 1) // Use math.Float32frombits to convert the uint32 bits back // into their float32 representation, again no actual change // in the bits, just a change in how we treat them in memory. // f is now our answer of 1 / sqrt(n) f := math.Float32frombits(b) // Perform one iteration of Newton's method on f to improve // accuracy f *= th - (n2 * f * f) // And return our fast inverse square root result return f }
https://github.com/arccoza/go-fastinvsqrt
64-битный алгоритм
import "math" const magic64 = 0x5FE6EB50C7B537A9 func FastInvSqrt64(n float64) float64 { if n < 0 { return math.NaN() } n2, th := n*0.5, float64(1.5) b := math.Float64bits(n) b = magic64 - (b >> 1) f := math.Float64frombits(b) f *= th - (n2 * f * f) return f }
Представление?
Вот некоторые цифры по сравнению со встроенным в Go math.Sqrt, обернутым в функцию invSqrt64
:
goos: linux goarch: amd64 pkg: github.com/arccoza/go-fastinvsqrt #Go Native BenchmarkInvSqrt64_1-4 149562032 7.81 ns/op BenchmarkInvSqrt64_2-4 153053457 7.77 ns/op BenchmarkInvSqrt64_3-4 150307755 7.82 ns/op BenchmarkInvSqrt64_4-4 153308527 7.80 ns/op BenchmarkInvSqrt64_5-4 199944013 5.96 ns/op # Fast inverse square root 32 bit BenchmarkFastInvSqrt32_1-4 694597858 1.77 ns/op BenchmarkFastInvSqrt32_2-4 634092076 1.69 ns/op BenchmarkFastInvSqrt32_3-4 706532166 1.69 ns/op BenchmarkFastInvSqrt32_4-4 700042736 1.70 ns/op BenchmarkFastInvSqrt32_5-4 698131202 1.79 ns/op # Fast inverse square root 64 bit BenchmarkFastInvSqrt64_1-4 447052143 2.39 ns/op BenchmarkFastInvSqrt64_2-4 506831372 2.26 ns/op BenchmarkFastInvSqrt64_3-4 524493175 2.26 ns/op BenchmarkFastInvSqrt64_4-4 525436268 2.47 ns/op BenchmarkFastInvSqrt64_5-4 470687276 2.28 ns/op PASS ok github.com/arccoza/go-fastinvsqrt 23.582s
Не плохо ?.
Опять же, в JavaScript
Почему нет? Таким образом, JavaScript, являющийся динамическим языком, не имеет типизированных значений, поэтому единственный способ манипулировать частью памяти сначала как с плавающей запятой, затем как с целым числом, а затем снова с плавающей запятой — это использовать типизированные массивы.
На самом деле вместо этого мы напрямую используем ArrayBuffer и DataView, поэтому мы можем обращаться к одним и тем же байтам как к разным типам.
const m = 0x5F375A86, // Creating the buffer and view outside the function // for performance, but this is not thread safe. buffer = new ArrayBuffer(4), view = new DataView(buffer) function fastInvSqrt (n) { var f, n2 = n * 0.5, th = 1.5 view.setFloat32(0, n) view.setUint32(0, m - (view.getUint32(0) >> 1)) f = view.getFloat32(0) f *= (th - (n2 * f * f)) f *= (th - (n2 * f * f)) return f }
https://github.com/arccoza/js-fastinvsqrt
А производительность… ужасная ?. Ничего удивительного, да ладно, вы можете сами проверить здесь: https://jsbench.me/vjk61wfui5/1