What's the correct and fast way to determine if a (gig) number is a perfect square?

Discussion in 'Ruby' started by Sam Kong, Feb 11, 2007.

  1. Sam Kong

    Sam Kong Guest


    I'm solving a math problem in Ruby.
    I need to determine if a number is a perfect square.
    If the number is small, you may do like the following.

    def perfect_square? n
    sqrt = n ** 0.5
    sqrt - sqrt.to_i == 0

    But Float number has limitation on precision.
    Thus the function won't work correctly for big numbers like

    How would you solve such a case?
    It should be fast as well as correct because I will use it repeatedly.

    Thanks in advance.

    Sam Kong, Feb 11, 2007
    1. Advertisements

  2. Easy: compare integers rather than floats.

    x = 123456789123456789

    sqrt = Math::sqrt(x)
    p(x == sqrt.floor**2)
    Joel VanderWerf, Feb 11, 2007
    1. Advertisements

  3. Sam Kong

    Xavier Noria Guest

    There are faster algorithms based on the fact that most non-squares
    aren't quadratic residues modulo some integers. I remember some is
    explained in Henri Cohen's "A Course in Computational Algebraic
    Number Theory", but do not have the book at hand.

    Perhaps you can take a look at the function that implements this test
    in GNU MP, explained here,


    or the one in Pari:


    -- fxn
    Xavier Noria, Feb 11, 2007
  4. Sam Kong

    Xavier Noria Guest

    I've been able to consult the book today. There is a specialised
    algorithm to compute integer roots using integer arithmetic, and the
    integer square test itself. Thus, they guarantee a correct result. I
    attach them below translated to Ruby.

    Some operations would be written using bitwise stuff, but anyway the
    code performs very poorly (compared to Math::sqrt) according to the
    benchmarks. If performance is important a solution in C would be
    worth exploring.

    -- fxn

    # From Henri Cohen's "A Course in Computational Algebraic Number
    # Theory".

    # Algorithm 1.7.1 (Integer Square Root) Given a positive integer n,
    # this algorithm computes the integer part of the square root of n,
    # i.e. the number m such that m^2 <= n < (m + 1)^2.
    def isqrt(n)
    x = n
    loop do
    y = ((x + n/x)/2)
    if y < x
    x = y
    return x

    # Cache the squares modulus 11, 63, 64, and 65. This is used to check
    # for non-squares, since a square is a square mod k for all k. The
    # choice of these numbers is based on the probability that a non-square
    # is a square mod any of them, which is 6/715, less than a 1%.
    $squares = {}
    [11, 63, 64, 65].each do |m|
    $squares[m] = [false] * m
    (0...(m/2)).each {|i| $squares[m][i**2 % m] = true}

    # Algorithm 1.7.3 (Square Test). Given a positive integer n,
    # this algorithm determines whether n is a square or not,
    # and if it is, outputs the square root of n. We assume the
    # precomputations made above.
    def issquare(n)
    return false unless $squares[64][n % 64]

    r = n % 45045 # 45045 = 63*65*11
    return false unless $squares[63][r % 63]
    return false unless $squares[65][r % 65]
    return false unless $squares[11][r % 11]

    q = isqrt(n)
    return q**2 == n ? q : false

    require 'benchmark'

    $r = 1000

    # square of 32248581868698698768678697647823648238462348
    $s =

    # non-square, the previous number minus 1
    $ns =

    # Just for the sake of curiosity, since the code based on Math::sqrt
    is not correct.
    Benchmark.benchmark do |x|
    x.report("builtin is square (true)") do
    1.upto($r) do
    sqrt = Math::sqrt($s)
    $s == sqrt.floor**2
    x.report("modular is square (true)") do
    1.upto($r) do
    x.report("builtin is square (false)") do
    1.upto($r) do
    sqrt = Math::sqrt($ns)
    $ns == sqrt.floor**2
    x.report("modular is square (false)") do
    1.upto($r) do
    Xavier Noria, Feb 12, 2007
  5. Sam Kong

    Sam Kong Guest

    Hi Joel,

    Yes. Your approach is better than mine.
    But it gives a wrong answer for big numbers like 55833579873437812.

    Thanks anyway.

    Sam Kong, Feb 12, 2007
  6. Sam Kong

    Sam Kong Guest

    Hi Xavier,

    I really appreciate your kind help.
    I put my comment inline.

    Actually you posted this message, I implemented an algorithm myself.
    It's just the way we calculate sqrt with pen and paper.
    It might be slow but correct even for big numbers.

    def max_digit n, m
    result = 0
    (0..9).each do |i|
    break if ((n * 10) + i) * i > m
    result = i

    def perfect_square? n
    arr = []
    a = n
    while true
    a, b = a / 100, a % 100
    arr.unshift b
    break if a == 0
    remain = 0
    carried = 0
    arr.each do |i|
    num = remain * 100 + i
    digit = max_digit(carried, num)
    remain = num - (carried * 10 + digit) * digit
    carried = (carried * 10 + digit) + digit
    remain == 0

    I felt ashamed to see the code you posted.OTL
    Thank you for your support.

    Sam Kong, Feb 12, 2007
  7. Wrong how?

    irb(main):001:0> x = 55833579873437812
    => 55833579873437812
    irb(main):002:0> sqrt = Math::sqrt(x)
    => 236291303.0
    irb(main):003:0> sqrt.floor**2 - x
    => -3

    Ok, I can see that one problem with my approach is that I should have
    used #round instead of #floor.
    Joel VanderWerf, Feb 12, 2007
  8. Sam Kong

    Sam Kong Guest

    I think even if you use #round, the problem won't go away.
    Float type cannot generate correct result due to its limited

    Sam Kong, Feb 12, 2007
  9. Sam Kong

    Phrogz Guest

    For example:
    => 981723462487562983749812734972342334123435635465656432452

    irb(main):005:0> y=x**2

    irb(main):006:0> z=Math.sqrt(y)
    => 9.81723462487563e+056

    irb(main):007:0> z==x
    => true

    irb(main):010:0> z==(x+1000)
    => true

    irb(main):011:0> z==(x+10000)
    => true
    Phrogz, Feb 12, 2007
  10. I agree, but I don't think the problem shows up until you have much
    larger numbers. Is that the case for your program?

    In this case, 55833579873437812 cannot be exactly represented by a
    float, but it doesn't matter for purposes of this calculation.
    Joel VanderWerf, Feb 12, 2007
  11. Sam Kong

    Ondrej Bilka Guest

    Best is use GMP. Other methods are binary search. Or bigdecimal with
    required accuracy
    Ondrej Bilka, Feb 13, 2007
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.