Project

General

Profile

Actions

Bug #13440

closed

Integer.sqrt produces wrong results

Added by stomar (Marcus Stollsteimer) almost 7 years ago. Updated almost 7 years ago.

Status:
Closed
Assignee:
-
Target version:
ruby -v:
ruby 2.5.0dev (2017-04-14 trunk 58353) [i686-linux]
[ruby-core:80696]

Description

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
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0