Быстрый обратный квадратный корень в Go (и JavaScript) для развлечения

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

См. также:  TWTW # неделя Angular JS

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

Понравилась статья? Поделиться с друзьями:
IT Шеф
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: