Project

General

Profile

Actions

Bug #17257

closed

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

Added by universato (Yoshimine Sato) over 3 years ago. Updated over 3 years ago.

Status:
Closed
Target version:
-
[ruby-core:100348]

Description

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))
Actions #1

Updated by sawa (Tsuyoshi Sawada) over 3 years ago

  • Description updated (diff)

Updated by nobu (Nobuyoshi Nakada) over 3 years ago

  • 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?

Updated by universato (Yoshimine Sato) over 3 years ago

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

Updated by midnight (Sarun R) over 3 years ago

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.

Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

It's a bug.

Additional tests look good.

Updated by nobu (Nobuyoshi Nakada) over 3 years ago

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

Updated by midnight (Sarun R) over 3 years ago

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.

Updated by midnight (Sarun R) over 3 years ago

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.

Updated by universato (Yoshimine Sato) over 3 years ago

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

Updated by sawa (Tsuyoshi Sawada) over 3 years ago

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

Updated by midnight (Sarun R) over 3 years ago

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.

Updated by universato (Yoshimine Sato) over 3 years ago

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

Updated by mame (Yusuke Endoh) over 3 years ago

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);
         }
     }
Actions #14

Updated by mame (Yusuke Endoh) over 3 years ago

  • 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]

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0