Bug #13440: Integer.sqrt produces wrong results

• Status: Closed
• 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

[stomar (Marcus Stollsteimer)]

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.

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:

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

[nobu (Nobuyoshi Nakada)]

• Status changed from Open to Closed

Applied in changeset trunk|r58366.

---

bignum.c: fix inexact estimation

• bignum.c (estimate_initial_sqrt): estimated square root is
  inexact if it is not equal to its ceil, needs Newton's method.
  [ruby-core:80696] [Bug #13440]

[nobu (Nobuyoshi Nakada)]

• Backport changed from 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN to 2.2: DONTNEED, 2.3: DONTNEED, 2.4: DONTNEED

[stomar (Marcus Stollsteimer)]

@nobu (Nobuyoshi Nakada)

Do you mind when I simplify the test and also reduce the number of tested values (50.000 seems more than necessary, and increases the runtime for the integer tests by a considerable percentage; even for only 1000 cases, i.e. step 0.05, there would be more than 70 failures without the fix).

I'd change it like this:

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

[nobu (Nobuyoshi Nakada)]

stomar (Marcus Stollsteimer) wrote:

Do you mind when I simplify the test and also reduce the number of tested values (50.000 seems more than necessary, and increases the runtime for the integer tests by a considerable percentage; even for only 1000 cases, i.e. step 0.05, there would be more than 70 failures without the fix).

No problems at all.