fastinvsqrt
所属分类：数学计算
开发工具：Makefile
文件大小：0KB
下载次数：0
上传日期：2022-09-26 13:51:54
上 传 者：
sh-1993
说明： 编程语言中的快速平方反比
(Fast inverse square root in programming languages)
文件列表:
Makefile (290, 2022-09-26)
script/ (0, 2022-09-26)
script/build.sh (140, 2022-09-26)
script/check_exec.sh (100, 2022-09-26)
script/clean.sh (151, 2022-09-26)
script/install.sh (247, 2022-09-26)
script/test.sh (1065, 2022-09-26)
script/validate.c (1221, 2022-09-26)
src/ (0, 2022-09-26)
src/asm/ (0, 2022-09-26)
src/asm/Makefile (417, 2022-09-26)
src/asm/fastinvsqrt.s (530, 2022-09-26)
src/c/ (0, 2022-09-26)
src/c/Makefile (412, 2022-09-26)
src/c/fastinvsqrt.c (437, 2022-09-26)
src/clojure/ (0, 2022-09-26)
src/clojure/Makefile (324, 2022-09-26)
src/clojure/fastinvsqrt.clj (324, 2022-09-26)
src/coffeescript/ (0, 2022-09-26)
src/coffeescript/Makefile (279, 2022-09-26)
src/coffeescript/fastinvsqrt.coffee (423, 2022-09-26)
src/cpp/ (0, 2022-09-26)
src/cpp/Makefile (425, 2022-09-26)
src/cpp/fastinvsqrt.cpp (413, 2022-09-26)
src/crystal/ (0, 2022-09-26)
src/crystal/Makefile (426, 2022-09-26)
src/crystal/fastinvsqrt.cr (230, 2022-09-26)
src/csharp/ (0, 2022-09-26)
src/csharp/FastInvSqrt.cs (534, 2022-09-26)
src/csharp/Makefile (468, 2022-09-26)
src/d/ (0, 2022-09-26)
src/d/Makefile (415, 2022-09-26)
src/d/fastinvsqrt.d (409, 2022-09-26)
src/elixir/ (0, 2022-09-26)
src/elixir/Makefile (485, 2022-09-26)
... ...
# Fast inverse square root in programming languages
[](https://github.com/itchyny/fastinvsqrt/actions)
[](https://api.github.com/repos/itchyny/fastinvsqrt/languages)
This is a repository for my challenge of *writing Fast inverse square root algorithm in many languages*.
Writing one algorithm in many languages is fun.
I wrote some codes in languages I have never experienced.
I learned the differences and similarities between the languages, how languages are influenced by others.
This challenge is just a passing point on my way.
Now I want to continue learning some languages I've never thought of writing before this challenge.
For example, I have never experienced Rust, OCaml and Erlang but now I think I should continue learning these languages.
## Why did I choose this algorithm?
Here is an implementation in C.
```c
float fastInvSqrt(float x) {
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1);
float y = *(float*)&i;
return y * (1.5F - 0.5F * x * y * y);
}
```
The pointer casting magic is the most important part of this algorithm.
I do not explain why the code works here, please refer to the other references [link](https://www.google.com/search?q=fast%20inverse%20square%20root).
First of all, the algorithm to choose should not be too easy and should not be too difficult.
If the problem was easy, I could write the codes after some glance on the language tutorials.
On the other hand, I could give up the challenge if it was too difficult.
Secondary, pointer casting is not such an easy task in some languages.
Some languages do not allow us to touch the pointer addresses of the variables.
For scripting languages, I have to look through the document whether I can get the byte pattern of floating point numbers.
Thirdly, I like the algorithm.
The algorithm is largely based on how the floating point number is represented on our computers.
When I came across this algorithm, I got very surprised that it effectively uses the casting pointers between different types of number.
## Some examples in languages
All the codes are included in the repository but I want to introduce some interesting implementations here.
### Groovy
Groovy is like an un-fancy Java.
```groovy
Scanner scanner = new Scanner(System.in)
while (scanner.hasNext()) {
try {
println fastInvSqrt(Float.parseFloat(scanner.nextLine()))
} catch (NumberFormatException e) {}
}
def fastInvSqrt(float x) {
int i = Float.floatToRawIntBits(x)
float y = Float.intBitsToFloat(0x5f3759df - (i >> 1))
y * (1.5F - 0.5F * x * y * y)
}
```
### Clojure
Clojure is also a JVM language so the `Float/floatToRawIntBits` function routes in the function of Java.
```clojure
(defn fast-inv-sqrt [x]
(let [i (Float/floatToRawIntBits x)
y (Float/intBitsToFloat (- 0x5f3759df (bit-shift-right i 1)))]
(* y (- 1.5 (* 0.5 x y y)))))
(doseq [line (line-seq (java.io.BufferedReader. *in*))]
(try (println (fast-inv-sqrt (read-string line)))
(catch java.lang.RuntimeException e ())))
```
### Crystal
This language looks like Ruby, but is one of the compiled languages.
The code of pointer casting looks pretty.
```crystal
def fastinvsqrt(x : Float32) : Float32
i = pointerof(x).as(Int32*).value
i = 0x5f3759df - (i >> 1)
y = pointerof(i).as(Float32*).value
y * (1.5 - 0.5 * x * y * y)
end
while line = gets
puts fastinvsqrt(line.to_f32)
end
```
### Rust
There are `f32::to_bits`, `f32::from_bits` to convert the number types keeping the bits.
```rust
use std::io::BufRead;
fn fast_inv_sqrt(x: f32) -> f32 {
let i = x.to_bits();
let j = 0x5f3759df - (i >> 1);
let y = f32::from_bits(j);
y * (1.5 - 0.5 * x * y * y)
}
fn main() {
let stdin = std::io::stdin();
for line in stdin.lock().lines().filter_map(|x| x.ok()) {
if let Ok(x) = line.parse() {
println!("{}", fast_inv_sqrt(x));
}
}
}
```
### Perl
The pack and unpack is useful in this challenge for scripting languages (PHP, Ruby, Python etc).
Somehow this code runs very fast as compiled languages.
```perl
use strict;
use warnings;
use feature qw(say);
while (<>) {
say fastInvSqrt($_);
}
sub fastInvSqrt {
my ($x) = @_;
my $i = unpack("l", pack("f", $x));
$i = 0x5f3759df - ($i >> 1);
my $y = unpack("f", pack("l", $i));
$y * (1.5 - 0.5 * $x * $y * $y);
}
```
### JavaScript
I thought it is impossible to implement in this language.
There's no difference between float and integer, 32-bit and 64-bit.
However, JavaScript has TypedArray, which we can read and write the numbers in specific bit widths.
```javascript
require('readline').createInterface({
input: process.stdin,
}).on('line', (line) => {
console.log(fastInvSqrt(parseFloat(line)));
});
function fastInvSqrt(x) {
const i = floatToUInt32(x);
const j = 0x5f3759df - (i >> 1);
const y = uint32ToFloat(j);
return y * (1.5 - 0.5 * x * y * y);
}
function floatToUInt32(x) {
const buf = Float32Array.of(x).buffer;
return new Uint32Array(buf)[0];
}
function uint32ToFloat(i) {
const buf = Uint32Array.of(i).buffer;
return new Float32Array(buf)[0];
}
```
### J
Just difficult to write, difficult to read.
```j
fastInvSqrt =: 3 : 0
i =. _2 ic 1 fc y
i =. (dfh'5f3759df') - _1 (33 b.) i
z =. _1 fc 2 ic i
z * (1.5 - 0.5 * y * z * z)
)
echo & fastInvSqrt & (0 & ".) & (-. & CRLF) ;. 2 &. stdin ''
exit ''
```
### F# #
F# is a .NET language so looking through the MSDN document gave me the way to convert to/from the byte arrays.
```fsharp
let fastinvsqrt(x: float32): float32 =
let i = System.BitConverter.ToInt32(System.BitConverter.GetBytes(x), 0)
let j = 0x5f3759df - (i >>> 1)
let y = System.BitConverter.ToSingle(System.BitConverter.GetBytes(j), 0)
y * (1.5F - 0.5F * x * y * y)
seq { while true do yield stdin.ReadLine() }
|> Seq.takeWhile ((<>) null)
|> Seq.iter (fun x -> try float32 x |> fastinvsqrt |> printfn "%f"
with :? System.FormatException -> ())
```
### Haskell
Haskell is a functional programming language with advanced features of type system mainly for the research of this field.
But it also provides an interface to read and write pointers.
```haskell
import Control.Monad ((<=<))
import Data.Bits (shiftR)
import Data.Traversable (mapM)
import Data.Word (Word32)
import Foreign.Marshal.Alloc (alloca)
import Foreign.Ptr (castPtr)
import Foreign.Storable (peek, poke)
import Prelude hiding (mapM)
import Text.Read (readMaybe)
main :: IO ()
main = mapM_ (mapM (print <=< fastInvSqrt) . readMaybe) . lines =<< getContents
fastInvSqrt :: Float -> IO Float
fastInvSqrt x =
alloca $ \ptr -> do
poke ptr x
i <- peek (castPtr ptr)
poke (castPtr ptr) $ 0x5f3759df - (i :: Word32) `shiftR` 1
y <- peek ptr
return $ y * (1.5 - 0.5 * x * y * y)
```
### Erlang
How cool the binary pattern match is.
I have never experienced this language but I think I want to learn more.
The test results show that the performance of this code is bad.
If you have any idea of improving the performance, please let me know from the issue tracker.
```erlang
-module(fastinvsqrt).
-export([main/0, fast_inv_sqrt/1]).
main() ->
case io:get_line("") of
eof -> ok;
{error, _} -> ok;
Line -> catch io:format("~f~n", [fast_inv_sqrt(parse_float(Line))]), main()
end.
fast_inv_sqrt(X) ->
<> = <>,
J = 16#5f3759df - (I bsr 1),
<> = <>,
Y * (1.5 - 0.5 * X * Y * Y).
parse_float(Str) ->
case string:to_float(Str) of
{error, _} ->
case string:to_integer(Str) of
{error, _} -> error;
{Int, _} -> float(Int)
end;
{Float, _} -> Float
end.
```
## Author
itchyny (https://github.com/itchyny)
Some codes were written by other people. Thank you so much.
- The credit of the Smalltalk version goes to sumim [#2](https://github.com/itchyny/fastinvsqrt/pull/2).
近期下载者：
相关文件：
收藏者：