This is an automated email from the ASF dual-hosted git repository.
git-site-role pushed a commit to branch asf-site
in repository https://gitbox.apache.org/repos/asf/groovy-dev-site.git
The following commit(s) were added to refs/heads/asf-site by this push:
new 8c4b9b2 2023/02/28 14:19:31: Generated dev website from
groovy-website@252e5c7
8c4b9b2 is described below
commit 8c4b9b26fa0d57f222dc50377c10af797530199a
Author: jenkins <[email protected]>
AuthorDate: Tue Feb 28 14:19:31 2023 +0000
2023/02/28 14:19:31: Generated dev website from groovy-website@252e5c7
---
blog/feed.atom | 10 +
blog/index.html | 4 +-
blog/quake3-inverse-square-root.html | 566 +++++++++++++++++++++++++++++++++++
3 files changed, 578 insertions(+), 2 deletions(-)
diff --git a/blog/feed.atom b/blog/feed.atom
index afbfd1e..c035ada 100644
--- a/blog/feed.atom
+++ b/blog/feed.atom
@@ -594,4 +594,14 @@
<published>2023-02-20T20:00:00+00:00</published>
<summary>Inspired by a recent update related to Antarctic timezones, this
post looks at some interesting Australian time zone facts.</summary>
</entry>
+ <entry>
+ <author>
+ <name>Paul King</name>
+ </author>
+ <title>Quake III Arena and the fast inverse square root algorithm</title>
+ <link href="http://groovy.apache.org/blog/quake3-inverse-square-root"/>
+ <updated>2023-02-28T00:05:18+00:00</updated>
+ <published>2023-02-28T00:05:18+00:00</published>
+ <summary>Inspired by a recent tweet, this blog looks at the fast inverse
square root algorithm made famous in Quake III Arena.</summary>
+ </entry>
</feed>
diff --git a/blog/index.html b/blog/index.html
index 80afc39..6e8bc2f 100644
--- a/blog/index.html
+++ b/blog/index.html
@@ -53,7 +53,7 @@
</ul>
</div>
</div>
- </div><div id='content' class='page-1'><div
class='row'><div class='row-fluid'><div class='col-lg-3' id='blog-index'><ul
class='nav-sidebar list'><li class='active'><a
href='/blog/'>Blogs</a></li><li><a href='australian-timezones'>Australian Time
Zones</a></li><li><a href='wordle-checker'>Checking Wordle with
Groovy</a></li><li><a href='groovy-null-processing'>Groovy Processing Nulls In
Lists</a></li><li><a href='groundhog-day'>Groundhog Day</a></li><li><a href='f
[...]
+ </div><div id='content' class='page-1'><div
class='row'><div class='row-fluid'><div class='col-lg-3' id='blog-index'><ul
class='nav-sidebar list'><li class='active'><a
href='/blog/'>Blogs</a></li><li><a href='quake3-inverse-square-root'>Quake III
Arena and the fast inverse square root algorithm</a></li><li><a
href='australian-timezones'>Australian Time Zones</a></li><li><a
href='wordle-checker'>Checking Wordle with Groovy</a></li><li><a
href='groovy-null-processin [...]
<div class='row'>
<div class='colset-3-footer'>
<div class='col-1'>
@@ -97,7 +97,7 @@
colors: am5.ColorSet.new(root, {})
}));
wc.data.setAll([
- { category: "calendar", value: 1 }, { category: "date", value:
3 }, { category: "groovy", value: 59 }, { category: "jsr310", value: 1 }, {
category: "time", value: 1 }, { category: "data science", value: 7 }, {
category: "eclipse collections", value: 7 }, { category: "kmeans", value: 3 },
{ category: "emoji", value: 3 }, { category: "virtual threads", value: 3 }, {
category: "scala integration", value: 1 }, { category: "clustering", value: 2
}, { category: "windows instal [...]
+ { category: "calendar", value: 1 }, { category: "date", value:
3 }, { category: "groovy", value: 60 }, { category: "jsr310", value: 1 }, {
category: "time", value: 1 }, { category: "data science", value: 7 }, {
category: "eclipse collections", value: 7 }, { category: "kmeans", value: 3 },
{ category: "emoji", value: 3 }, { category: "virtual threads", value: 3 }, {
category: "scala integration", value: 1 }, { category: "clustering", value: 2
}, { category: "windows instal [...]
]);
wc.labels.template.setAll({
paddingTop: 5,
diff --git a/blog/quake3-inverse-square-root.html
b/blog/quake3-inverse-square-root.html
new file mode 100644
index 0000000..db4db88
--- /dev/null
+++ b/blog/quake3-inverse-square-root.html
@@ -0,0 +1,566 @@
+<!DOCTYPE html>
+<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
+<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
+<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]-->
+<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]--><head>
+ <meta charset='utf-8'/><meta http-equiv='X-UA-Compatible'
content='IE=edge'/><meta name='viewport' content='width=device-width,
initial-scale=1'/><meta name='keywords' content='groovy'/><meta
name='description' content='Inspired by a recent tweet, this blog looks at the
fast inverse square root algorithm made famous in Quake III Arena.'/><title>The
Apache Groovy programming language - Blogs - Quake III Arena and the fast
inverse square root algorithm</title><link href='../img/favicon [...]
+</head><body>
+ <div id='fork-me'>
+ <a href='https://github.com/apache/groovy'>
+ <img style='position: fixed; top: 20px; right: -58px; border: 0;
z-index: 100; transform: rotate(45deg);'
src='/img/horizontal-github-ribbon.png'/>
+ </a>
+ </div><div id='st-container' class='st-container st-effect-9'>
+ <nav class='st-menu st-effect-9' id='menu-12'>
+ <h2 class='icon icon-lab'>Socialize</h2><ul>
+ <li>
+ <a href='http://groovy-lang.org/mailing-lists.html'
class='icon'><span class='fa fa-envelope'></span> Discuss on the
mailing-list</a>
+ </li><li>
+ <a href='https://twitter.com/ApacheGroovy'
class='icon'><span class='fa fa-twitter'></span> Groovy on Twitter</a>
+ </li><li>
+ <a href='http://groovy-lang.org/events.html'
class='icon'><span class='fa fa-calendar'></span> Events and conferences</a>
+ </li><li>
+ <a href='https://github.com/apache/groovy'
class='icon'><span class='fa fa-github'></span> Source code on GitHub</a>
+ </li><li>
+ <a href='http://groovy-lang.org/reporting-issues.html'
class='icon'><span class='fa fa-bug'></span> Report issues in Jira</a>
+ </li><li>
+ <a href='http://stackoverflow.com/questions/tagged/groovy'
class='icon'><span class='fa fa-stack-overflow'></span> Stack Overflow
questions</a>
+ </li><li>
+ <a href='http://groovycommunity.com/' class='icon'><span
class='fa fa-slack'></span> Slack Community</a>
+ </li>
+ </ul>
+ </nav><div class='st-pusher'>
+ <div class='st-content'>
+ <div class='st-content-inner'>
+ <!--[if lt IE 7]>
+ <p class="browsehappy">You are using an
<strong>outdated</strong> browser. Please <a
href="http://browsehappy.com/";>upgrade your browser</a> to improve your
experience.</p>
+ <![endif]--><div><div class='navbar navbar-default
navbar-static-top' role='navigation'>
+ <div class='container'>
+ <div class='navbar-header'>
+ <button type='button'
class='navbar-toggle' data-toggle='collapse' data-target='.navbar-collapse'>
+ <span class='sr-only'></span><span
class='icon-bar'></span><span class='icon-bar'></span><span
class='icon-bar'></span>
+ </button><a class='navbar-brand'
href='../index.html'>
+ <i class='fa fa-star'></i> Apache
Groovy
+ </a>
+ </div><div class='navbar-collapse collapse'>
+ <ul class='nav navbar-nav navbar-right'>
+ <li class=''><a
href='http://groovy-lang.org/learn.html'>Learn</a></li><li class=''><a
href='http://groovy-lang.org/documentation.html'>Documentation</a></li><li
class=''><a href='/download.html'>Download</a></li><li class=''><a
href='http://groovy-lang.org/support.html'>Support</a></li><li class=''><a
href='/'>Contribute</a></li><li class=''><a
href='http://groovy-lang.org/ecosystem.html'>Ecosystem</a></li><li class=''><a
href='https://groovy.apac [...]
+ <a data-effect='st-effect-9'
class='st-trigger' href='#'>Socialize</a>
+ </li><li class=''>
+ <a href='../search.html'>
+ <i class='fa fa-search'></i>
+ </a>
+ </li>
+ </ul>
+ </div>
+ </div>
+ </div><div id='content' class='page-1'><div
class='row'><div class='row-fluid'><div class='col-lg-3'><ul
class='nav-sidebar'><li><a href='./'>Blog index</a></li><li class='active'><a
href='#doc'>Quake III Arena and the fast inverse square root
algorithm</a></li><li><a href='#_introduction'
class='anchor-link'>Introduction</a></li><li><a
href='#_java_float_implementations' class='anchor-link'>Java Float
implementations</a></li><li><a href='#_java_double_implementat [...]
+<h2 id="_introduction">Introduction</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>In 1999, <a href="https://www.idsoftware.com/";>id Software</a> released
+<a href="https://en.wikipedia.org/wiki/Quake_III_Arena";>Quake III Arena</a>,
+a multiplayer first-person shooter.</p>
+</div>
+<div class="paragraph">
+<p><span class="image"><img
src="https://cdn.80.lv/api/upload/content/b4/images/612db4a5b4d6c/widen_1840x0.jpeg";
alt="Quake III" width="460"></span></p>
+</div>
+<div class="paragraph">
+<p>When the game’s source code was released to the world,
+it contained a previously unknown algorithm called the
+<a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root";>Fast Inverse
Square Root</a>.
+We don’t plan to explain the algorithm in depth but its significance at
the time
+is that it provided a very good approximation to the equation
+\$f(x) = 1/sqrt(x)\$
+which is used for vector normalization and other math behind the game which is
used extensively for numerous graphical aspects including 3D shading.
+The fast algorithm was 3-4 times faster at calculating the answer than using
the
+traditional math libraries and the results were within < 0.2%.</p>
+</div>
+<div class="paragraph">
+<p>Here is the code:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="c">float Q_rsqrt( float
number )
+{
+ long i;
+ float x2, y;
+ const float threehalfs = 1.5F;
+
+ x2 = number * 0.5F;
+ y = number;
+ i = * ( long * ) &y; // evil floating point
bit level hacking
+ i = 0x5f3759df - ( i >> 1 ); // what the f☼⁕k?
+ y = * ( float * ) &i;
+ y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
+// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can
be removed
+
+ return y;
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Why does it look strange? There are numerous parts which you wouldn’t
expect
+to be part of a square root calculation. There’s some tricks for
converting
+to and from float and long IEEE 754 32-bit representations, a "magic" constant,
+some bit shifting, and a touch of Newton’s method throw in for good
measure.</p>
+</div>
+<div class="paragraph">
+<p>The details have been explained in some detail in numerous blogs, e.g.
+<a href="https://suraj.sh/fast-square-root-approximation/";>Fast Square Root
Approximation</a>
+and
+<a
href="https://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/";>Understanding
Quake’s Fast Inverse Square Root</a>,
+and videos, e.g.
+<a href="https://www.youtube.com/watch?v=p8u_k2LIZyo";>Fast Inverse Square Root
— A Quake III Algorithm</a> and
+<a
href="https://80.lv/articles/quake-iii-arena-s-unknown-algorithm-explained/";>Quake
III Arena’s Unknown Algorithm Explained</a>.
+There are even sites which show the algorithm for
+<a href="https://github.com/itchyny/fastinvsqrt";>numerous languages</a>
(including Groovy).</p>
+</div>
+<div class="paragraph">
+<p>Not long after the game’s release, Intel added
+<a href="https://c9x.me/x86/html/file_module_x86_id_301.html";>SQRTSS</a> and
+<a href="https://c9x.me/x86/html/file_module_x86_id_283.html";>RSQRTSS</a>
+instructions to x86 processors.
+Here is one of the JDK enhancements to provide
+<a href="https://bugs.openjdk.org/browse/JDK-6452568";>SQRTSS support for float
Math.sqrt()</a>.
+There are later blogs which explain that, due to these and other hardware
advances,
+the algorithm is now mostly only relevant for historical folklore reasons, e.g.
+<a
href="https://levelup.gitconnected.com/death-of-quake-3s-inverse-square-root-hack-32fd2eadd7b7";>Death
of Quake 3’s Inverse Square Root Hack</a> and
+<a
href="https://www.linkedin.com/pulse/fast-inverse-square-root-still-armin-kassemi-langroodi/";>Is
Fast Inverse Square Root still Fast?</a>.</p>
+</div>
+<div class="paragraph">
+<p>Let’s have a look at a few alternatives for calculating the inverse
square root
+including two variants of the fast inverse square root algorithm.
+We’ll do this for Java and Groovy, and look at both <code>float</code>
and <code>double</code> implementations. We could go further and try different
numbers of iterations
+of the Newton’s method correction, but we’ll leave that as an
exercise for the reader. 😊</p>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_java_float_implementations">Java Float implementations</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>There are numerous places to see Java examples of the algorithm
+and numerous ways you could run a microbenchmark. We are using
+code somewhat similar to this
+<a href="https://gist.github.com/ClickerMonkey/adc35fece77eff67dfc3";>gist</a>.
+We could have been more elaborate and used
+<a href="https://github.com/openjdk/jmh";>jmh</a>, but we aren’t
+trying to do a comprehensive performance analysis here,
+we just want some rough ballpark numbers. Perhaps that is
+the topic for a subsequent blog.</p>
+</div>
+<div class="paragraph">
+<p>As with all microbenchmarks, you should exercise extreme caution
+before applying too much weight to the results. The numbers will be
+different on different machines, with different Java and Groovy
+versions and so forth. We used Groovy 4.0.8 and Java 17.0.2.</p>
+</div>
+<div class="paragraph">
+<p>We start with the most obvious implementation which is
+to use the <code>Math.sqrt</code> method which takes and returns a
<code>double</code>:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">public static float
invsqrt0(float x) { // Java
+ return 1.0f / (float)Math.sqrt(x);
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Compared to the C implementation above,
+Java doesn’t have the bit casting trick, but it does have its own
+methods for getting at the bit representation:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">public static float
invsqrt1(float x) { // Java
+ float xhalf = 0.5f * x;
+ int i = Float.floatToIntBits(x);
+ i = 0x5f3759df - (i >> 1);
+ x = Float.intBitsToFloat(i);
+ x = x * (1.5f - (xhalf * x * x));
+ return x;
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>As an alternative, we can use a byte buffer to mangle the bits back and
forth:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">private static
ByteBuffer buf = ByteBuffer.allocateDirect(4); // Java
+
+public static float invsqrt2(float x) {
+ float xhalf = 0.5f * x;
+ int i = buf.putFloat(0, x).getInt(0);
+ i = 0x5f3759df - (i >> 1);
+ x = buf.putInt(0, i).getFloat(0);
+ x = x * (1.5f - (xhalf * x * x));
+ return x;
+}</code></pre>
+</div>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_java_double_implementations">Java Double implementations</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>Again, we’ll start with the obvious implementation:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">public static double
invsqrt0(double x) { // Java
+ return 1.0d / Math.sqrt(x);
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Again, using the built-in methods for getting at the bit representation:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">public static double
invsqrt1(double x) { // Java
+ double xhalf = 0.5d * x;
+ long i = Double.doubleToLongBits(x);
+ i = 0x5fe6ec85e7de30daL - (i >> 1);
+ x = Double.longBitsToDouble(i);
+ x *= (1.5d - xhalf * x * x);
+ return x;
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>The code resembles the float version but the "magic" constant has
+changed for doubles.</p>
+</div>
+<div class="paragraph">
+<p>The byte buffer alternative:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">private static
ByteBuffer buf = ByteBuffer.allocateDirect(8); // Java
+
+public static double invsqrt2(double x) {
+ double xhalf = 0.5d * x;
+ long i = buf.putDouble(0, x).getLong(0);
+ //long i = Double.doubleToLongBits(x);
+ i = 0x5fe6ec85e7de30daL - (i >> 1);
+ x = buf.putLong(0, i).getDouble(0);
+ x *= (1.5d - xhalf * x * x);
+ return x;
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>We can also for comparison try the <code>Math.pow</code> method:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="java">public static double
invsqrt3(double x) { // Java
+ return Math.pow(x, -0.5d);
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>(We could have done this for <code>float</code> too but it doesn’t
add much to our analysis
+since it would call through to this double method anyway.)</p>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_groovy_float_implementations">Groovy Float implementations</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>All these examples are compiled with static compilation enabled.
+We want speed and aren’t doing any metaprogramming, so we don’t
+need Groovy’s dynamic capabilities.</p>
+</div>
+<div class="paragraph">
+<p>Our code looks similar to Java for the obvious case:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static float
invsqrt0(float x) {
+ 1.0f / Math.sqrt(x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Again, the code is similar to Java for the fast algorithm:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static float
invsqrt1(float x) {
+ float xhalf = 0.5f * x
+ int i = Float.floatToIntBits(x)
+ i = 0x5f3759df - (i >> 1)
+ x = Float.intBitsToFloat(i)
+ x *= 1.5f - (xhalf * x * x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>And again with the byte buffer:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">private static
ByteBuffer buf = ByteBuffer.allocateDirect(8)
+
+static float invsqrt2(float x) {
+ float xhalf = 0.5f * x
+ int i = buf.putDouble(0, x).getInt(0)
+ i = 0x5f3759df - (i >> 1)
+ x = buf.putInt(0, i).getDouble(0)
+ x *= 1.5f - (xhalf * x * x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>We can also try Groovy’s <code>**</code> operator (<code>power</code>
method):</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static float
invsqrt4(float x) {
+ (x ** -0.5).floatValue()
+}</code></pre>
+</div>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_groovy_double_implementations">Groovy Double implementations</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>The standard method should look familiar by now:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static double
invsqrt0(double x) {
+ 1.0d / Math.sqrt(x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>The fast algorithm:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static double
invsqrt1(double x) {
+ double xhalf = 0.5d * x
+ long i = Double.doubleToLongBits(x)
+ i = 0x5fe6ec85e7de30daL - (i >> 1)
+ x = Double.longBitsToDouble(i)
+ x *= (1.5d - xhalf * x * x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Incorporating the byte buffer:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">private static
ByteBuffer buf = ByteBuffer.allocateDirect(8)
+
+static double invsqrt2(double x) {
+ double xhalf = 0.5d * x
+ long i = buf.putDouble(0, x).getLong(0)
+ i = 0x5fe6ec85e7de30daL - (i >> 1)
+ x = buf.putLong(0, i).getDouble(0)
+ x *= (1.5d - xhalf * x * x)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Using <code>Math.pow</code>:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static double
invsqrt3(double x) {
+ Math.pow(x, -0.5d)
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Groovy’s <code>**</code> operator (<code>power</code> method)
again:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="prettyprint highlight"><code data-lang="groovy">static double
invsqrt4(double x) {
+ (x ** -0.5).doubleValue()
+}</code></pre>
+</div>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_results">Results</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>Here are the results of executing the above methods.
+We used a harness similar to the previously mentioned
+<a href="https://gist.github.com/ClickerMonkey/adc35fece77eff67dfc3";>gist</a>,
+but found the inverse square root of 100_000 random numbers
+instead of 10_000, and we used 1000 iterations in the timing loop
+and found the average execution time per 100_000 calculations.</p>
+</div>
+<table class="tableblock frame-all grid-all stretch">
+<colgroup>
+<col style="width: 33.3333%;">
+<col style="width: 16.6666%;">
+<col style="width: 16.6666%;">
+<col style="width: 16.6666%;">
+<col style="width: 16.6669%;">
+</colgroup>
+<tbody>
+<tr>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Algorithm
vs Implementation<br>
+(times m/s)</p></td>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Java
Float</p></td>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Java
Double</p></td>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Groovy
Float</p></td>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Groovy
Double</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">Math.sqrt</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.216</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.254</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.359</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.245</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Fast
inverse square root</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.230</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.236</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.357</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.127</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top"><p class="tableblock">Fast
inverse square root with byte buffer</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.337</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.364</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.486</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.187</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">Math.pow(x, -0.5d)</p></td>
+<td class="tableblock halign-left valign-top"></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">8.949</p></td>
+<td class="tableblock halign-left valign-top"></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">8.997</p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top"><p class="tableblock">x **
-0.5</p></td>
+<td class="tableblock halign-left valign-top"></td>
+<td class="tableblock halign-left valign-top"></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">0.737</p></td>
+<td class="tableblock halign-left valign-top"><p
class="tableblock">1.807</p></td>
+</tr>
+</tbody>
+</table>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_analysis">Analysis</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>For all the examples, using the byte buffer was always slower than the
original
+algorithm, so we can rule that out as an optimization. We can also rule out
using
+the <code>Math.pow</code> method. It is much slower than
<code>Math.sqrt</code>. Interesting though,
+Groovy’s <code>**</code> operator (<code>power</code> method) while
still a slower option was
+significantly better than the JDK library <code>pow</code> implementation.</p>
+</div>
+<div class="paragraph">
+<p>The Java fast algorithm was slower for float and only marginally faster
+for doubles. It seems unlikely in most scenarios that taking on the extra
+code complexity is worth the small gain in performance.</p>
+</div>
+<div class="paragraph">
+<p>The Groovy float implementations are a little slower. This is due to Groovy
+doing most of the calculations using doubles and converting back to floats
+in between steps. That is an area for possible optimization in the future.</p>
+</div>
+<div class="paragraph">
+<p>The Groovy double implementations are at least as fast as Java.
+Interesting, the fast algorithms seem to be even faster in Groovy.
+These do seem worthwhile investigating further if you really need the speed,
+but given the extra precision of doubles, you might want to run extra
+Newton method iterations and those iterations might eat into any time
saving.</p>
+</div>
+<div class="paragraph">
+<p>For interest, the errors for the fast algorithm for the random numbers
+was very close to 6E-5 for all implementations.</p>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_conclusion">Conclusion</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p>We’ve done a little microbenchmark using Java and Groovy for the
+fast inverse square root algorithm. The result?
+You probably don’t need to ever worry about the fast inverse
+square root algorithm anymore! But if you really have the need,
+it is still relatively fast, but you should benchmark your application
+and see if it really helps.</p>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_references">References</h2>
+<div class="sectionbody">
+<div class="ulist">
+<ul>
+<li>
+<p><a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root";>Fast
inverse square root on Wikipedia</a></p>
+</li>
+<li>
+<p><a
href="https://medium.com/hard-mode/the-legendary-fast-inverse-square-root-e51fee3b49d9";>History
behind the algorithm</a></p>
+</li>
+<li>
+<p><a href="http://www.lomont.org/papers/2003/InvSqrt.pdf";>Fast Inverse Square
Root paper</a></p>
+</li>
+<li>
+<p><a
href="https://www.slideshare.net/maksym_zavershynskyi/fast-inverse-square-root";>Behind
the Performance of Quake 3 Engine: Fast Inverse Square Root</a></p>
+</li>
+</ul>
+</div>
+</div>
+</div></div></div></div></div><footer id='footer'>
+ <div class='row'>
+ <div class='colset-3-footer'>
+ <div class='col-1'>
+ <h1>Groovy</h1><ul>
+ <li><a
href='http://groovy-lang.org/learn.html'>Learn</a></li><li><a
href='http://groovy-lang.org/documentation.html'>Documentation</a></li><li><a
href='/download.html'>Download</a></li><li><a
href='http://groovy-lang.org/support.html'>Support</a></li><li><a
href='/'>Contribute</a></li><li><a
href='http://groovy-lang.org/ecosystem.html'>Ecosystem</a></li><li><a
href='https://groovy.apache.org/events.html'></a></li>
+ </ul>
+ </div><div class='col-2'>
+ <h1>About</h1><ul>
+ <li><a
href='https://github.com/apache/groovy'>Source code</a></li><li><a
href='http://groovy-lang.org/security.html'>Security</a></li><li><a
href='http://groovy-lang.org/learn.html#books'>Books</a></li><li><a
href='http://groovy-lang.org/thanks.html'>Thanks</a></li><li><a
href='http://www.apache.org/foundation/sponsorship.html'>Sponsorship</a></li><li><a
href='http://groovy-lang.org/faq.html'>FAQ</a></li><li><a
href='http://groovy-lang.org/sea [...]
+ </ul>
+ </div><div class='col-3'>
+ <h1>Socialize</h1><ul>
+ <li><a
href='http://groovy-lang.org/mailing-lists.html'>Discuss on the
mailing-list</a></li><li><a href='https://twitter.com/ApacheGroovy'>Groovy on
Twitter</a></li><li><a href='http://groovy-lang.org/events.html'>Events and
conferences</a></li><li><a href='https://github.com/apache/groovy'>Source code
on GitHub</a></li><li><a
href='http://groovy-lang.org/reporting-issues.html'>Report issues in
Jira</a></li><li><a href='http://stackoverflow.com [...]
+ </ul>
+ </div><div class='col-right'>
+ <p>
+ The Groovy programming language is
supported by the <a href='http://www.apache.org'>Apache Software Foundation</a>
and the Groovy community.
+ </p><div text-align='right'>
+ <img src='../img/asf_logo.png'
title='The Apache Software Foundation' alt='The Apache Software Foundation'
style='width:60%'/>
+ </div><p>Apache® and the Apache
feather logo are either registered trademarks or trademarks of The Apache
Software Foundation.</p>
+ </div>
+ </div><div class='clearfix'>© 2003-2023
the Apache Groovy project — Groovy is Open Source: <a
href='http://www.apache.org/licenses/LICENSE-2.0.html' alt='Apache 2
License'>license</a>, <a
href='https://privacy.apache.org/policies/privacy-policy-public.html'>privacy
policy</a>.</div>
+ </div>
+ </footer></div>
+ </div>
+ </div>
+ </div>
+ </div><script src='../js/vendor/jquery-1.10.2.min.js'
defer></script><script src='../js/vendor/classie.js' defer></script><script
src='../js/vendor/bootstrap.js' defer></script><script
src='../js/vendor/sidebarEffects.js' defer></script><script
src='../js/vendor/modernizr-2.6.2.min.js' defer></script><script
src='../js/plugins.js' defer></script><script
src='https://cdnjs.cloudflare.com/ajax/libs/prettify/r298/prettify.min.js'></script><script>document.addEventListener('DOMContentLoa
[...]
+
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new
Date();a=s.createElement(o),
+
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+
+ ga('create', 'UA-257558-10', 'auto');
+ ga('send', 'pageview');
+ </script>
+</body></html>
\ No newline at end of file
![https://cdn.80.lv/api/upload/content/b4/images/612db4a5b4d6c/widen_1840x0.jpeg"](https://cdn.80.lv/api/upload/content/b4/images/612db4a5b4d6c/widen_1840x0.jpeg"){kind=link}