[ruby-core:80702] [Ruby trunk Bug#13440] Integer.sqrt produces wrong results

Issue #13440 has been updated by stomar (Marcus Stollsteimer).


@nobu

Do you mind when I simplify the test and also reduce the number of tested values (50.000 seems more than necessary, even for 1000 cases, i.e. step 0.05, there would be more than 70 failures before the fix).

I'd change it like this:

``` diff
From 117e6af6858d5215ba17585ebf79bc1c33f2bd5e Mon Sep 17 00:00:00 2001
From: Marcus Stollsteimer <[e-mail]>
Date: Sat, 15 Apr 2017 19:35:22 +0200
Subject: * test/ruby/test_integer.rb: simplify test for Integer.sqrt

---
 test/ruby/test_integer.rb |   13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

diff --git a/test/ruby/test_integer.rb b/test/ruby/test_integer.rb
index 963c6b7..db47827 100644
--- a/test/ruby/test_integer.rb
+++ b/test/ruby/test_integer.rb
@@ -490,15 +490,12 @@ def test_square_root
     end
 
     bug13440 = '[ruby-core:80696] [Bug #13440]'
-    too_big = []
-    too_small = []
-    0.step(to: 50, by: 0.001) do |i|
+    failures = []
+    0.step(to: 50, by: 0.05) do |i|
       n = (10**i).to_i
-      int_root = Integer.sqrt(n)
-      too_big   << n  if int_root*int_root > n
-      too_small << n  if (int_root+1)*(int_root+1) <= n
+      root = Integer.sqrt(n)
+      failures << n  unless root*root <= n && (root+1)*(root+1) > n
     end
-    assert_empty(too_big, bug13440)
-    assert_empty(too_small, bug13440)
+    assert_empty(failures, bug13440)
   end
 end
-- 
1.7.9.5

```


----------------------------------------
Bug #13440: Integer.sqrt produces wrong results
https://bugs.ruby-lang.org/issues/13440#change-64248

* Author: stomar (Marcus Stollsteimer)
* Status: Closed
* Priority: Normal
* Assignee: 
* Target version: 2.5
* ruby -v: ruby 2.5.0dev (2017-04-14 trunk 58353) [i686-linux]
* Backport: 2.2: DONTNEED, 2.3: DONTNEED, 2.4: DONTNEED
----------------------------------------
The new `Integer.sqrt` method produces wrong results, e.g. for

    38815036599065022652481536
    38904514499428047971680256

and (many) other numbers.

Note that these numbers were picked selectively (these are not the 2 smallest examples), and also that they are well in the range where Math.sqrt(n).to_i still gives correct results (Float precision still sufficient). However, the latter point is only incidental, I also found much bigger examples, in the range where Math.sqrt is useless.

``` ruby
numbers = [
  38815036599065022652481534,
  38815036599065022652481535,
  38815036599065022652481536,  # fails
  38815036599065022652481537,  # fails
  38904514499428047971680254,
  38904514499428047971680255,
  38904514499428047971680256,  # fails
  38904514499428047971680257,  # fails
  40271703432545948091285502,
  40271703432545948091285503,
  40271703432545948091285504,  # fails
  40271703432545948091285505,  # fails
  1442115351524865087017488818362939538217338142719,
  1442115351524865087017488818362939538217338142720,  # fails
]

def validate(number, root)
  root**2 <= number && (root+1)**2 > number
end

numbers.map {|n| [Integer.sqrt(n), validate(n, Integer.sqrt(n))] }
  # => [[6230171474290, true],
  #     [6230171474290, true],
  #     [6230171582464, false],
  #     [6230171582464, false],
  #     [6237348354824, true],
  #     [6237348354824, true],
  #     [6237348429824, false],
  #     [6237348429824, false],
  #     [6345999009812, true],
  #     [6345999009812, true],
  #     [6345999122432, false],
  #     [6345999122432, false],
  #     [1200881073014669961418100, true],
  #     [1200881075629054276665344, false]]
numbers.map {|n| [Math.sqrt(n).to_i, validate(n, Math.sqrt(n).to_i)] }
  # => [[6230171474290, true],
  #     [6230171474290, true],
  #     [6230171474290, true],
  #     [6230171474290, true],
  #     [6237348354824, true],
  #     [6237348354824, true],
  #     [6237348354824, true],
  #     [6237348354824, true],
  #     [6345999009812, true],
  #     [6345999009812, true],
  #     [6345999009812, true],
  #     [6345999009812, true],
  #     [1200881073014669968408576, false],
  #     [1200881073014669968408576, false]]

1.size  # => 4 (32-bit system)
```

Interestingly, I found only examples (yet) where `Integer.sqrt` produces results that are (much) too big.

It was rather too easy to find those; here's what I did:

``` ruby
too_big, too_small = [], []
total = 0

0.step(to: 50, by: 0.001) do |i|
  n = (10**i).to_i
  raise  unless n.class == Integer  # just to make sure...

  int_root = Integer.sqrt(n)

  total += 1
  too_big   << n  if int_root*int_root > n
  too_small << n  if (int_root+1)*(int_root+1) <= n
end

puts "total: #{total}"
puts
puts "too small (#{too_small.size}):", too_small
puts
puts "too big (#{too_big.size}):"

puts too_big[0..9]
puts "..."
puts too_big[-10..-1]

# >> total: 50001
# >> 
# >> too small (0):
# >> 
# >> too big (3579):
# >> 38815036599065022652481536
# >> 38904514499428047971680256
# >> 38994198667654436652843008
# >> 39810717055349854497144832
# >> 40271703432545948091285504
# >> 40364539296760648765014016
# >> 40457589169744204087164928
# >> 40644332916521443952427008
# >> 40926065973001261821198336
# >> 42169650342858222399913984
# >> ...
# >> 1324341535194664238462783233069825155347351863296
# >> 1367728825595857894544027656111101204949201059840
# >> 1370881766164855075247880701478883966489888555008
# >> 1409288798421877644341184857286932334307738386432
# >> 1412537544622749693814622477014802231398687047680
# >> 1415793779957092451680042925874609046246970621952
# >> 1422328787122815537257372883177955123216529752064
# >> 1432187899273539462185319204962288499459270639616
# >> 1438798578255849634982033297755877609401625870336
# >> 1442115351524865087017488818362939538217338142720
```




-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>