quake_iii_inverse_quare_root_in_elixir_with_performance_test.livemc

# Quake III algorithm - Fast inverse square root using binary pattern matching + Performance Test!

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

## Section

```elixir
defmodule Quake do
  @moduledoc "https://en.wikipedia.org/wiki/Fast_inverse_square_root"

  # The magic constant from Quake III
  @magic_constant 0x5F3759DF

  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

  def inverse_sqrt(x) when is_float(x) and x > 0 do
    1.0 / :math.sqrt(x)
  end
end
```

```elixir
ExUnit.start(autorun: false)

defmodule InverseSqrtTest do
  use ExUnit.Case
  use ExUnitProperties

  describe "inverse_sqrt implementations" do
    property "fast_inverse_sqrt/1 and inverse_sqrt/1 produce similar results" do
      check all(num <- positive_float()) do
        fast_result = Quake.fast_inverse_sqrt(num)
        standard_result = Quake.inverse_sqrt(num)

        # Allow for small differences due to approximation
        assert_in_delta(
          fast_result,
          standard_result,
          0.2,
          "Results differ for input #{num}: fast=#{fast_result}, standard=#{standard_result}"
        )
      end
    end

    property "inverse_sqrt/1 satisfies mathematical properties" do
      check all(num <- positive_float()) do
        result = Quake.inverse_sqrt(num)

        # Property: result * result * num ≈ 1
        product = result * result * num

        assert_in_delta(
          product,
          1.0,
          0.2,
          "Mathematical property violated for #{num}: result=#{result}, product=#{product}"
        )
      end
    end

    property "fast_inverse_sqrt/1 satisfies mathematical properties" do
      check all(num <- positive_float()) do
        result = Quake.fast_inverse_sqrt(num)

        # Property: result * result * num ≈ 1
        product = result * result * num

        # May need larger delta for approximation algorithm
        assert_in_delta(
          product,
          1.0,
          0.2,
          "Mathematical property violated for #{num}: result=#{result}, product=#{product}"
        )
      end
    end

    property "both functions handle edge cases consistently" do
      check all(num <- edge_case_floats()) do
        fast_result = Quake.fast_inverse_sqrt(num)
        standard_result = Quake.inverse_sqrt(num)

        # Both should handle edge cases similarly
        case {fast_result, standard_result} do
          {fast, standard} when is_number(fast) and is_number(standard) ->
            # For some extremely small edge case floats, the difference
            # can be up to 150
            assert_in_delta(fast, standard, 150)

          _ ->
            flunk("Inconsistent edge case handling for #{num}")
        end
      end
    end

    property "performance characteristics" do
      check all(nums <- list_of(positive_float(), min_length: 100, max_length: 1000)) do
        # Measure execution time for both implementations
        {fast_time, fast_results} =
          :timer.tc(fn ->
            Enum.map(nums, &Quake.fast_inverse_sqrt/1)
          end)

        {standard_time, standard_results} =
          :timer.tc(fn ->
            Enum.map(nums, &Quake.inverse_sqrt/1)
          end)

        # Verify results are similar
        Enum.zip(fast_results, standard_results)
        |> Enum.each(fn {fast, standard} ->
          # If you want to see the actual value differences:
          # IO.puts("Fast: #{fast}, Standard: #{standard}, Diff: #{abs(fast - standard)}")
          assert_in_delta(fast, standard, 0.2)
        end)

        IO.puts(
          "Fast: #{fast_time}μs, Standard: #{standard_time}μs, Speedup: #{standard_time / fast_time}x"
        )

        assert true
      end
    end
  end

  # Custom generators
  defp positive_float() do
    gen all(num <- float(min: 0.0001, max: 1.0e10)) do
      num
    end
  end

  defp edge_case_floats() do
    frequency([
      {8, positive_float()},
      {1, constant(1.0)},
      # Very small numbers
      {1, float(min: 1.0e-10, max: 1.0e-5)},
      # Very large numbers
      {1, float(min: 1.0e5, max: 1.0e10)}
    ])
  end
end

ExUnit.run()
```