From: sto.mar@...
Date: 2017-04-15T13:19:55+00:00
Subject: [ruby-core:80696] [Ruby trunk Bug#13440] Integer.sqrt produces	wrong results

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

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

* Author: stomar (Marcus Stollsteimer)
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 2.5
* ruby -v: ruby 2.5.0dev (2017-04-14 trunk 58353) [i686-linux]
* Backport: 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
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:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>