Bug #17257: Integer#pow(0, 1) returns 1, which is incorrect

• Status: Closed
• Assignee: mrkn (Kenta Murata)
• Target version: -
• Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN

[universato (Yoshimine Sato)]

Ruby 2.5.8, 2.6.6, 2.7.1

p -1.pow(0, 1) #=> 1
p  0.pow(0, 1) #=> 1
p  1.pow(0, 1) #=> 1
p 1234567890.pow(0, 1) #=> 1

These return values should be 0.

Patch for test:

Let's add some boundary value tests to test_pow of test_numeric.rb.

integers = [-2, -1, 0, 1, 2, 3, 6, 1234567890123456789]
integers.each do |i|
  assert_equal(0, i.pow(0, 1), '[Bug #17257]')
  assert_equal(1, i.pow(0, 2))
  assert_equal(1, i.pow(0, 3))
  assert_equal(1, i.pow(0, 6))
  assert_equal(1, i.pow(0, 1234567890123456789))
  
  assert_equal(0,  i.pow(0, -1))
  assert_equal(-1, i.pow(0, -2))
  assert_equal(-2, i.pow(0, -3))
  assert_equal(-5, i.pow(0, -6))
  assert_equal(-1234567890123456788, i.pow(0, -1234567890123456789))
end

assert_equal(0,  0.pow(2, 1))
assert_equal(0,  0.pow(3, 1))
assert_equal(0,  2.pow(3, 1))
assert_equal(0, -2.pow(3, 1))

[sawa (Tsuyoshi Sawada)]

• Description updated (diff)

[nobu (Nobuyoshi Nakada)]

• Status changed from Open to Assigned
• Assignee set to mrkn (Kenta Murata)

I'm not sure if it should be 0.
As x.pow(y, m) equals multiplying x % m to 1 y times, isn't 1 ok when y == 0?

[universato (Yoshimine Sato)]

According to RDoC, x.pow(y, m) equals (x**y) % m.
In fact, x.pow(y, m) returns same value as (x**y) % m except for x.pow(0, 1).

p (12**0) % 1  #=> 0
p 12.pow(0, 1) #=> 1

[midnight (Sarun R)]

This is undefined
0.pow(0, 1)
https://www.wolframalpha.com/input/?i=0%5E0

This is clearly out of the space (thus a bug)
1.pow(0, 1)
https://www.wolframalpha.com/input/?i=%281%5E0%29+mod+1

It is practically pointless to mod by 1; I don't think this change will break anything in the wild.
Nobody would rely on 1%1 == 0.
The problem is what to do with 0 ** 0.

[marcandre (Marc-Andre Lafortune)]

It's a bug.

Additional tests look good.

[nobu (Nobuyoshi Nakada)]

I agree that the behavior and documentation may be inconsistent, and think one option is to fix the latter.

[midnight (Sarun R)]

So the proposal is to change the document from
"Returns (modular) exponentiation"
to
"multiplying x % m to 1 y times"?

IMHO % m is the space, ** y is the operation performed inside the space, so the result should be within the space.
If % m is the operation itself, that would be a different story.

[midnight (Sarun R)]

Wait a minute, I just changed my mind.
Actually since 0.pow(0) is mathematically undefined.

See WolframAlpha for references:
https://www.wolframalpha.com/input/?i=0%5E0

0.pow(0, 1) should be undefined too, so do 1.pow(0, 1).
Because inside the % 1 space, 1 == 0 and 12 == 0 too.

[universato (Yoshimine Sato)]

x.pow(y, m) doesn't equal multiplying x % m to 1 y times.

p 3.pow(2, 4) #=> 1
p 1 * (3 % 4) * (3 % 4) #=> 9 

It is the last to mod.
The result should be less than modulo.
Method pow should be simply defined as (x**y) % m.

And, 0.pow(0) is not necessarily undefined.
In many programming languages, 0 ** 0 returns 1 because it is useful.
For example, Python, R, C++, C#, Java, JavaScript, PHP, Perl, MATLAB, Octave, Haskell, Julia, Crystal and Ruby e.t.c.

For reference, Python has pow function like Ruby's pow.
Python defines pow(x, y, m) as (x**y) % m, and Python's pow returns 0 when modulo is 1.

print((12 ** 0) % 1) # 0
print(pow(12, 0, 1)) # 0

[sawa (Tsuyoshi Sawada)]

I cannot follow the discussion because of the expression "multiplying x % m to 1 y times." What does that mean?

[midnight (Sarun R)]

The point of undefinition is:
There is nothing definitely right or wrong.
Neither 0 nor 1 is wrong; it is just a different point of view.

You are thinking that 0 ** 0 == 1 is useful because you are looking from the perspective of x ** 0 == 1 for most of x
while 0 ** x == 0 is also true for most of x too, and it is as useful as x ** 0 == 1.

Weather 0 ** 0 should return 0 or 1 is subjective, and whatever the actual implementation is, it is not entirely wrong, same for little-endian vs. big-endian.
This is the reason why the value is undefined.
Regardless of mathematical definitions, I second for x.pow(y, 1) should return 0, as I said initially, % m is the space and every value inside % 1 space is 0.

Mathematical wise this is considered undefined behavior. Implementation wise there is an advantage that we follow other popular languages in this matter.

I just want to point out that people who oppose the behavior change has some merit.
Even if the current behavior sounds wildly wrong, most people are not going to care, because the value is mathematically undefined in the first place.
And no practical result will be obtained from % 1 space.

Anyway, x % 1 == 0 sound more "correct" to me too.

[universato (Yoshimine Sato)]

sawa (Tsuyoshi Sawada) wrote in #note-10:

I cannot follow the discussion because of the expression "multiplying x % m to 1 y times." What does that mean?

"multiplying x % m to 1 y times"の意味は、「1に対して(x % m)をy回乗じること(又は、その値)」ですかね。

想像以上に議論が活発で嬉しいですが慣れない英語で疲れたし読み誤っているかもしれないので、自分のために日本語で整理します。

nobuさんが、最初に#1で「x.pow(y, m)は1に(x % m)をy回乗じた値に等しいから、y == 0のときは1でいいのではないでしょうか」と言ってると思います。

そして、自分の#9を言い直すと「3.pow(2, 4)が1に対して、1に(3 % 4)を2回乗じた値は9であるため、x.pow(y, m)は1に(x % m)をy回乗じた値に等しいとは限りません。最後にmodを取る必要があるため、powの計算結果はm未満になるはずです。mod 1で1を返すx.pow(0, 1)の挙動に合わせるために、現状のシンプルな定義(x**y) % mからx.pow(0, 1)だけ例外的に1を返す特別な理由を付け加えたり変更することは難しいと思いました。」と言いたかったです。

midnightさんの#7の意見もおそらく同様で「ドキュメントを"1に(x % m)をy回乗じた値"に変更するのですか。私の考えでは、% mとは空間であり、その空間の中で累乗の計算**yが行われるから、計算結果は空間に収まるべきです(≒m未満になるべき)。」と言ってると思います。

......

あと話が変わりますが、「mod 1を使うケースは実用的でない」という意見もあり、半分同意です。ただ、正しければ必ず0を返すことは検算に役立つ利点があり、また今回あらゆるmodのケースを想定して最小正数の1でもテストしたらがpowで詰まったので決してmod 1を使うケースがないわけではなく、小さいけどmod 1で1を返すバグで変更されてもいいはずと思い、今回提案しました。また、変更するにあたってのデメリットも小さいはずと考えました。x.pow(0, 1)の挙動を積極的に使う人はいないはずで後方互換性の影響を気にしなくても大丈夫だと思います。また、コードの修正も基本的にはif(m == 1){ return 0; }を加えるだけだと想像しました。このあたりは、コードを書いた担当者のmrknさんの意見も聞きたいところです。その他の提案理由は、Pythonのmod_powは正しい動作をしてる気がするのに悔しい感じがします。

Sorry for writing only in Japanese

[mame (Yusuke Endoh)]

I agree that it is a bug. The pseudocode of modular exponentiation in Wikipedia includes if modulus = 1 then return 0 as the first check.

https://en.wikipedia.org/wiki/Modular_exponentiation#Pseudocode

I agree that there are few real use cases of modulo 1, so few one will be affected by this change. I'll fix it soon.

diff --git a/bignum.c b/bignum.c
index 65a50ea9ba..0515e2f0d6 100644
--- a/bignum.c
+++ b/bignum.c
@@ -7136,6 +7136,7 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num)
             long const half_val = (long)HALF_LONG_MSB;
             long const mm = FIX2LONG(m);
             if (!mm) rb_num_zerodiv();
+            if (mm == 1) return INT2FIX(0);
             if (mm <= half_val) {
                 return int_pow_tmp1(rb_int_modulo(a, m), b, mm, nega_flg);
             }
@@ -7145,6 +7146,7 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num)
         }
         else {
             if (rb_bigzero_p(m)) rb_num_zerodiv();
+           if (bignorm(m) == INT2FIX(1)) return INT2FIX(0);
             return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg);
         }
     }

[mame (Yusuke Endoh)]

• Status changed from Assigned to Closed

Applied in changeset git|8a39e6d6539bd37100cbbfb88916b853f444f771.

---

bignum.c (rb_int_powm): Integer#pow(0, 1) should return 0

... instead of 1 because it requires "modulo 1". [Bug #17257]