Inconsistent modulo

[oprypin]

>> (-7) % 5
# Crystal: -2
# Ruby: 3
>> (-7.0) % 5.0
# Crystal: undefined method '%' for Float64
# Ruby: 3.0
>> (-7).modulo(5)
# Crystal: -2
# Ruby: 3
>> (-7).remainder(5)
# Crystal: undefined method 'remainder' for Int32
# Ruby: -2
>> require "big_int"; (-7.to_big_i) % (5.to_big_i)
# Crystal: 3

I suggest leaving % as is for performance, but making modulo wrap around like Ruby (possible implementation: (a % b + b) % b).

Wouldn't be bad to add remainder which is the same as current %.

[jhass]

We can have remainder, but % should be defined as modulo. That's what it is in other languages and having it behave differently is confusing.

See also http://llvm.org/docs/LangRef.html#srem-instruction

[oprypin]

I'm not sure what you mean.

C, Java, LLVM and many others give the same results as Crystal currently for %.
Ruby, Python do wraparound which is actually called "modulo"

[jhass]

I guess I still categorize Crystal more into the higher level languages that wrap around ;)

[asterite]

What should we do with this? I also found out that Ruby/Python behave different than C/D/Java/Crystal, I just don't know what's the correct thing to do. Maybe it's deciding what we want '%' to mean, either 'remainder' or 'modulo'?

[jhass]

As said I see Crystal closer to Ruby and Python, so having % do the modulo behavior would be IMO less confusing.

[oprypin]

The best meaning for % is with wraparound, but only if performance isn't taken into account. I'll stick with my previous suggestion, unless modulo with wraparound is less than 1.5 times slower than the current behavior.

[asterite]

You can always benchmark and see :-)

require "benchmark"

def modulo(a, b)
  (a % b + b) % b
end

FROM = -10_000
TO = 10_000

a1 = 0
a2 = 0

Benchmark.bm do |x|
  x.report("%") do
    a = 0
    (FROM..TO).each do |i|
      (FROM..TO).each do |j|
        next if j == 0
        a += i % j
      end
    end
    a1 = a
  end
  x.report("modulo") do
    a = 0
    (FROM..TO).each do |i|
      (FROM..TO).each do |j|
        next if j == 0
        a += modulo(i, j)
      end
    end
    a2 = a
  end
end

pp a1
pp a2

Gives:

             user     system      total        real
%        1.000000   0.000000   1.000000 (  1.005000)
modulo   1.800000   0.000000   1.800000 (  1.799956)

For what use one uses modulo with negative numbers?

[jhass]

Proving my bad math skills here, but did I get this right that modulo can be optimized to the remainder if the argument is positive? If so that seems to be worth the comparison here.

[oprypin]

I don't think this is the best possible implementation.

Modulo is used for cycling/wraparound like in https://github.com/BlaXpirit/crsfml/blob/master/examples/snakes.cr

Another example is keeping angles in 0...360 range. direction = (direction - turn_angle) % 360.0 and no nasty conditionals/loops.

[jhass]

Here's Ruby's http://rxr.whitequark.org/mri/source/numeric.c#2754

[asterite]

Just tried with this:

def modulo(a, b)
  if b == 0
    raise DivisionByZero.new
  elsif a > 0
    a.unsafe_mod(b)
  else
    (a.unsafe_mod(b) + b).unsafe_mod(b)
  end
end

and it's 1s vs 1.44s now. I have to try that Ruby implementation. But I think it would be OK to leave % as modulo and have a separate remainder method (like in Ruby).

[asterite]

Tried with this (seen here):

def modulo(a, b)
  if b == 0
    raise DivisionByZero.new
  elsif a > 0
    a.unsafe_mod(b)
  else
    a = a.unsafe_mod(b)
    a < 0 ? a + b : a
  end
end

and it's 1.008s for % vs 1.06s for modulo. I think we can use the "better" semantic at no cost :-)

[ysbaddaden]

👍

[asterite]

However:

# Ruby
13 % -4 #=> -3

# Crystal
modulo(13, -4) #=> 1

What's the reason for that?

This is starting to feel like a philosophical discussion :-)

[ssvb]

@asterite Maybe this variant then?

# 'a' and 'b' need to be two's complement signed integers of the same size
def modulo(a, b)
  if b == 0
    raise DivisionByZero.new
  elsif (a ^ b) >= 0
    a.unsafe_mod(b)
  else
    a = a.unsafe_mod(b)
    a == 0 ? a : a + b
  end
end

[jhass]

Here's Python's: https://github.com/python/cpython/blob/master/Objects/longobject.c#L2444

[oprypin]

@jhass That's basically BigInt. Nothing to see there 😐

Maybe this would be more relevant: https://github.com/python/cpython/blob/2.7/Objects/intobject.c#L583

[ssvb]

@BlaXpirit Thanks, this is an interesting link. They are also using xor to check if the operands have different sign, like in my modification of the @asterite's variant (which was just adapted to match Ruby's behaviour). Also cpython relies on the C language as a backend for implementing this operation and they have hints that there might be some portability issues between different platforms :-) But I don't think that this is something that we should worry about (as long as there is a good coverage for the modulo operation in the Crystal test suite). But I can run a quick test to check if this implementation works correctly on ARM hardware too.

[ssvb]

Here is the @asterite's benchmark program with a correctness test added:

require "benchmark"

# A slow reference implementation
def modulo_ref(a, b)
  a = a.to_i64
  b = b.to_i64
  (a % b + b) % b
end

# 'a' and 'b' need to be two's complement signed integers of the same size
def modulo(a, b)
  if b == 0
    raise DivisionByZero.new
  elsif (a ^ b) >= 0
    a.unsafe_mod(b)
  else
    a = a.unsafe_mod(b)
    a == 0 ? a : a + b
  end
end

# Correctness test

macro modulo_correctness_test_for_type(typename)
  ({{typename}}::MIN .. {{typename}}::MAX).each do |i|
    ({{typename}}::MIN .. {{typename}}::MAX).each do |j|
      next if j == 0
      next if i == {{typename}}::MIN && j == -1
      abort "problems with #{i} % #{j}" if modulo_ref(i, j) != modulo(i, j)
    end
  end
end

modulo_correctness_test_for_type(Int8)

# Benchmark

FROM = -10_000
TO = 10_000

a1 = 0
a2 = 0

Benchmark.bm do |x|
  x.report("%") do
    a = 0
    (FROM..TO).each do |i|
      (FROM..TO).each do |j|
        next if j == 0
        a += i % j
      end
    end
    a1 = a
  end
  x.report("modulo") do
    a = 0
    (FROM..TO).each do |i|
      (FROM..TO).each do |j|
        next if j == 0
        a += modulo(i, j)
      end
    end
    a2 = a
  end
end

pp a1
pp a2

The output on my system:

             user     system      total        real
%        0.010834   0.000000   0.010834 (  7.103003)
modulo   0.011841   0.000000   0.011841 (  7.768067)

A few notes:

• The (a % b + b) % b is not really correct unless 'a' and 'b' are casted to a larger type. For example, a = -127_i8 ; b = -128_i8 ; p (a % b + b) % b prints 1 instead of -127
• There is a signed integer division overflow problem to watch out, see Signed integer division overflow #575

[ssvb]

And most importantly, the casted to a larger type (a % b + b) % b really works in Crystal in the same way as a % b in Ruby, as can be tested with the help of the following two programs:

results_gen.rb

FROM = -1000
TO   = 1000

(FROM..TO).each do |i|
  (FROM..TO).each do |j|
    next if j == 0
    puts "#{i} #{j} #{i % j}"
  end
end

results_check.cr

STDIN.each_line do |line|
  a, b, ref = line.split.map { |x| x.to_i }
  abort "We have a problem with #{a} % #{b}" if (a % b + b) % b != ref
end

And running them as

$ ruby results_gen.rb | crystal results_check.cr

[asterite]

If you find anything wrong in the implementation or something to improve, please continue discussing here or send a pull request :-)