Bug #13440
closed
Integer.sqrt produces wrong results
Description
The new Integer.sqrt method produces wrong results, e.g. for
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
Updated by nobu (Nobuyoshi Nakada) about 9 years ago
- 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]
Updated by nobu (Nobuyoshi Nakada) about 9 years ago
- Backport changed from 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN to 2.2: DONTNEED, 2.3: DONTNEED, 2.4: DONTNEED
Updated by stomar (Marcus Stollsteimer) about 9 years ago
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 <sto.mar@web.de>
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
Updated by nobu (Nobuyoshi Nakada) about 9 years ago
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.