From: nobu@... Date: 2017-04-16T06:27:43+00:00 Subject: [ruby-core:80707] [Ruby trunk Bug#13440] Integer.sqrt produces wrong results Issue #13440 has been updated by 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. ---------------------------------------- Bug #13440: Integer.sqrt produces wrong results https://bugs.ruby-lang.org/issues/13440#change-64253 * 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: