Project

General

Profile

Feature #13219

Updated by nobu (Nobuyoshi Nakada) about 7 years ago

In doing a math application using **Math.sqrt(n).to_i** to compute integer squareroots  
 of integers I started noticing errors for numbers > 10**28. 


 I coded an algorithm that accurately computes the integer squareroot for arbirary sized numbers 
 but its significantly slower than the math library written in C. 

 Thus, I request a new method **Math.intsqrt(n)** be created, that is coded in C and part of the 
 core library, that will compute the integer squareroots of integers accurately and fast. 

 Here is working highlevel code to accurately compute the integer squareroot. 

 ```ruby ``` 
 def intsqrt(n) 
   bits_shift = (n.to_s(2).size)/2 + 1 
   bitn_mask = root = 1 << bits_shift 
   while true 
     root ^= bitn_mask if (root * root) > n 
     bitn_mask >>= 1 
     return root if bitn_mask == 0 
     root |= bitn_mask 
   end 
 end 

 def intsqrt1(n) 
   return n if n | 1 == 1     # if n is 0 or 1 
   bits_shift = (Math.log2(n).ceil)/2 + 1 
   bitn_mask = root = 1 << bits_shift 
   while true 
     root ^= bitn_mask if (root * root) > n 
     bitn_mask >>= 1 
     return root if bitn_mask == 0 
     root |= bitn_mask 
   end 
 end 

 require "benchmark/ips" 

 Benchmark.ips do |x| 
   n = 10**40 
   puts "integer squareroot tests for n = #{n}" 
   x.report("intsqrt(n)"         ) { intsqrt(n)    } 
   x.report("intsqrt1(n)"        ) { intsqrt1(n) } 
   x.report("Math.sqrt(n).to_i") { Math.sqrt(n).to_i } 
   x.compare! 
 end 
 ``` 
 Here's why it needs to be done in C. 

 ``` 
 2.4.0 :178 > load 'intsqrttest.rb' 
 integer squareroot tests for n = 10000000000000000000000000000000000000000 
 Warming up -------------------------------------- 
           intsqrt(n)       5.318k i/100ms 
          intsqrt1(n)       5.445k i/100ms 
    Math.sqrt(n).to_i     268.281k i/100ms 
 Calculating ------------------------------------- 
           intsqrt(n)       54.219k (± 5.5%) i/s -      271.218k in     5.017552s 
          intsqrt1(n)       55.872k (± 5.4%) i/s -      283.140k in     5.082953s 
    Math.sqrt(n).to_i        5.278M (± 6.1%) i/s -       26.560M in     5.050707s 

 Comparison: 
    Math.sqrt(n).to_i:    5278477.8 i/s 
          intsqrt1(n):      55871.7 i/s - 94.47x    slower 
           intsqrt(n):      54219.4 i/s - 97.35x    slower 

  => true  
 2.4.0 :179 >  

 ``` 
 Here are examples of math errors using **Math.sqrt(n).to_i** run on Ruby-2.4.0. 

 ``` 
 2.4.0 :101 > n = 10**27; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c    
 1000000000000000000000000000 
 31622776601683 
 999999999999949826038432489 
 31622776601683 
 999999999999949826038432489 
 31622776601683 
 999999999999949826038432489 
  => nil  
 2.4.0 :102 > n = 10**28; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c  
 10000000000000000000000000000 
 100000000000000 
 10000000000000000000000000000 
 100000000000000 
 10000000000000000000000000000 
 100000000000000 
 10000000000000000000000000000 
  => nil  
 2.4.0 :103 > n = 10**29; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c  
 100000000000000000000000000000 
 316227766016837 
 99999999999999409792567484569 
 316227766016837 
 99999999999999409792567484569 
 316227766016837 
 99999999999999409792567484569 
  => nil  
 2.4.0 :104 > n = 10**30; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c   
 1000000000000000000000000000000 
 1000000000000000 
 1000000000000000000000000000000 
 1000000000000000 
 1000000000000000000000000000000 
 1000000000000000 
 1000000000000000000000000000000 
  => nil  
 2.4.0 :105 > n = 10**31; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c  
 10000000000000000000000000000000 
 3162277660168379 
 9999999999999997900254631487641 
 3162277660168379 
 9999999999999997900254631487641 
 3162277660168379 
 9999999999999997900254631487641 
  => nil  
 2.4.0 :106 > n = 10**32; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c  
 100000000000000000000000000000000 
 10000000000000000 
 100000000000000000000000000000000 
 10000000000000000 
 100000000000000000000000000000000 
 10000000000000000 
 100000000000000000000000000000000 
  => nil  
 2.4.0 :107 > n = 10**33; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 
 1000000000000000000000000000000000 
 31622776601683793 
 999999999999999979762122758866849 
 31622776601683793 
 999999999999999979762122758866849 
 31622776601683792 
 999999999999999916516569555499264 
  => nil  
 2.4.0 :108 > n = 10**34; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 
 10000000000000000000000000000000000 
 100000000000000000 
 10000000000000000000000000000000000 
 100000000000000000 
 10000000000000000000000000000000000 
 100000000000000000 
 10000000000000000000000000000000000 
  => nil  
 2.4.0 :109 > n = 10**35; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 
 100000000000000000000000000000000000 
 316227766016837933 
 99999999999999999873578871987712489 
 316227766016837933 
 99999999999999999873578871987712489 
 316227766016837952 
 100000000000000011890233980627554304 
  => nil  
 2.4.0 :110 > n = 10**36; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 
 1000000000000000000000000000000000000 
 1000000000000000000 
 1000000000000000000000000000000000000 
 1000000000000000000 
 1000000000000000000000000000000000000 
 1000000000000000000 
 1000000000000000000000000000000000000 
  => nil  
 2.4.0 :111 > n = 10**37; puts n, (a = intsqrt(n)), a*a, (b = intsqrt1(n)), b*b, (c = Math.sqrt(n).to_i), c*c 
 10000000000000000000000000000000000000 
 3162277660168379331 
 9999999999999999993682442519108007561 
 3162277660168379331 
 9999999999999999993682442519108007561 
 3162277660168379392 
 10000000000000000379480317059650289664 
  => nil  
 2.4.0 :112 >  
 ```

Back