benchmarks/math/barrett.cr

• View this file on GitHub
• Last update: 2021-10-16 11:24:12+09:00

Depends on

• src/math/barrett.cr

Code

require "benchmark"
require "../../src/math/barrett"

N = 1000000

private macro benchmark(mod)
  mod = {{mod}}u32

  b = rand(mod)
  expect = N.times.reduce(1u64) { |acc| acc * b % {{mod}} }

  puts "-------- mod: {{mod}} --------"
  Benchmark.ips do |x|
    x.report("a * b % mod") do
      a = 1u64
      N.times { a = a * b % mod }
      raise "" unless expect == a
    end

    x.report("a &* b % mod") do
      a = 1u64
      N.times { a = a * b % mod }
      raise "" unless expect == a
    end

    x.report("a * b % MOD") do
      a = 1u64
      N.times { a = a * b % {{mod}} }
      raise "" unless expect == a
    end

    x.report("a &* b % MOD") do
      a = 1u64
      N.times { a = a * b % {{mod}} }
      raise "" unless expect == a
    end

    x.report("bt.mul(a, b)") do
      bt = Barrett.new(mod)
      a = 1u32
      N.times { a = bt.mul(a, b) }
      raise "" unless expect == a
    end
  end
  puts
end

benchmark 1
benchmark 100000
benchmark 1000000000
benchmark 1000000007
benchmark 2147483647

require "benchmark"

# require "../../src/math/barrett"
struct Barrett
  getter mod : UInt32, inv : UInt64

  # Requires `1 <= mod < 2^31`
  def initialize(@mod)
    @inv = UInt64::MAX // @mod &+ 1
  end

  # Caluclates `a * b % mod`.
  #
  # Requires `0 <= a < mod` and `0 <= b < mod`
  def mul(a : UInt32, b : UInt32) : UInt32
    z = a.to_u64! &* b
    x = ((z.to_u128! &* @inv) >> 64).to_u64!
    v = (z &- x &* @mod).to_u32!
    v &+= @mod if @mod <= v
    v
  end
end

N = 1000000

private macro benchmark(mod)
  mod = {{mod}}u32

  b = rand(mod)
  expect = N.times.reduce(1u64) { |acc| acc * b % {{mod}} }

  puts "-------- mod: {{mod}} --------"
  Benchmark.ips do |x|
    x.report("a * b % mod") do
      a = 1u64
      N.times { a = a * b % mod }
      raise "" unless expect == a
    end

    x.report("a &* b % mod") do
      a = 1u64
      N.times { a = a * b % mod }
      raise "" unless expect == a
    end

    x.report("a * b % MOD") do
      a = 1u64
      N.times { a = a * b % {{mod}} }
      raise "" unless expect == a
    end

    x.report("a &* b % MOD") do
      a = 1u64
      N.times { a = a * b % {{mod}} }
      raise "" unless expect == a
    end

    x.report("bt.mul(a, b)") do
      bt = Barrett.new(mod)
      a = 1u32
      N.times { a = bt.mul(a, b) }
      raise "" unless expect == a
    end
  end
  puts
end

benchmark 1
benchmark 100000
benchmark 1000000000
benchmark 1000000007
benchmark 2147483647

Back to top page