quake_iii_inverse_quare_root_in_elixir.livemc

# Quake III algorithm - Fast inverse square root using binary pattern matching

```elixir
Mix.install([
  {:kino, "~> 0.17.0"}
])
```

## Section

Implementation of the famous Quake III [fast inverse square root algorithm](https://en.wikipedia.org/wiki/Fast_inverse_square_root) using Elixir's binary pattern matching capabilities. Check out Peter Ullrichs's blog article [Binary Pattern Matching in Elixir](https://peterullrich.com/binary-pattern-matching-in-elixir)...

> This is just some fun Claude-generated AI slob ...

```elixir
defmodule Quake do
  @moduledoc """
  Implementation of the famous Quake III fast inverse square root algorithm
  using Elixir's binary pattern matching capabilities.

  https://en.wikipedia.org/wiki/Fast_inverse_square_root
  """

  # The magic constant from Quake III
  @magic_constant 0x5F3759DF

  @doc """
  Calculates the fast inverse square root of a number: 1/√x

  Uses binary pattern matching to reinterpret float bits as integer,
  perform bit manipulation, then reinterpret back to float.
  """
  def fast_inverse_sqrt(x) when is_float(x) and x > 0 do
    x_half = x * 0.5

    # Step 1: Extract the 32-bit float representation as binary
    <<i::unsigned-integer-32>> = <<x::float-32>>

    # Step 2: The magic bit manipulation
    # Subtract half the bits from the magic constant
    i_magic = @magic_constant - Bitwise.>>>(i, 1)

    # Step 3: Reinterpret the integer bits back as a float
    <<y::float-32>> = <<i_magic::unsigned-integer-32>>

    # Step 4: One iteration of Newton's method for refinement
    y * (1.5 - x_half * y * y)
  end

  @doc """
  Standard inverse square root for comparison
  """
  def inverse_sqrt(x) when is_float(x) and x > 0 do
    1.0 / :math.sqrt(x)
  end

  @doc """
  Demonstrates the algorithm with examples and returns a Markdown table
  """
  def demo do
    test_values = [4.0, 9.0, 16.0, 25.0, 100.0, 0.5, 1.5]

    header = "| x | Fast Inverse √ | Standard Inverse √ | Error % |\n"
    separator = "|---|----------------|--------------------|---------|\n"

    rows =
      Enum.map_join(test_values, fn x ->
        fast_result = fast_inverse_sqrt(x)
        standard_result = inverse_sqrt(x)
        error = abs(fast_result - standard_result)
        error_percent = error / standard_result * 100

        "| #{x} | #{Float.round(fast_result, 8)} | #{Float.round(standard_result, 8)} | #{Float.round(error_percent, 6)} |\n"
      end)

    header <> separator <> rows
  end

  @doc """
  Shows the binary pattern matching step by step
  """
  def explain(x) when is_float(x) and x > 0 do
    IO.puts("\nStep-by-step binary pattern matching for x = #{x}")
    IO.puts("=" |> String.duplicate(60))

    # Step 1: Float to binary
    <<i::unsigned-integer-32>> = binary = <<x::float-32>>
    IO.puts("\n1. Float as 32-bit binary:")
    IO.puts("   <<#{x}::float-32>> = #{inspect(binary)}")
    IO.puts("   Integer value: 0x#{Integer.to_string(i, 16)} (#{i})")

    # Step 2: Magic manipulation
    i_shifted = Bitwise.>>>(i, 1)
    i_magic = @magic_constant - i_shifted
    IO.puts("\n2. Magic bit manipulation:")
    IO.puts("   i >> 1 = 0x#{Integer.to_string(i_shifted, 16)}")
    IO.puts("   0x#{Integer.to_string(@magic_constant, 16)} - 0x#{Integer.to_string(i_shifted, 16)} = 0x#{Integer.to_string(i_magic, 16)}")

    # Step 3: Integer back to float
    <<y::float-32>> = <<i_magic::unsigned-integer-32>>
    IO.puts("\n3. Reinterpret as float:")
    IO.puts("   <<0x#{Integer.to_string(i_magic, 16)}::unsigned-integer-32>> = <<#{y}::float-32>>")
    IO.puts("   Approximation: #{y}")

    # Step 4: Newton refinement
    x_half = x * 0.5
    y_refined = y * (1.5 - x_half * y * y)
    IO.puts("\n4. Newton's method refinement:")
    IO.puts("   y * (1.5 - (x/2) * y * y) = #{y_refined}")

    actual = 1.0 / :math.sqrt(x)
    IO.puts("\n5. Comparison:")
    IO.puts("   Actual 1/√#{x} = #{actual}")
    IO.puts("   Error: #{abs(y_refined - actual)}\n")
  end
end
```

```elixir
# Run the demo
Quake.demo() |> Kino.Markdown.new()
```

```elixir
# Show detailed explanation for one value
Quake.explain(4.0)
```