Реализация быстрого алгоритма обратного квадратного корня в 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
