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

    Hello,

    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
    end

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

    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
     
    Sam Kong, Feb 11, 2007
    #1
    1. Advertising

  2. Re: What's the correct and fast way to determine if a (gig) numberis a perfect square?

    Sam Kong wrote:
    > Hello,
    >
    > 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
    > end
    >
    > But Float number has limitation on precision.
    > Thus the function won't work correctly for big numbers like
    > (123456789123456789).
    >
    > How would you solve such a case?
    > It should be fast as well as correct because I will use it repeatedly.


    Easy: compare integers rather than floats.

    x = 123456789123456789

    sqrt = Math::sqrt(x)
    p(x == sqrt.floor**2)

    --
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Joel VanderWerf, Feb 11, 2007
    #2
    1. Advertising

  3. Sam Kong

    Xavier Noria Guest

    On Feb 11, 2007, at 8:30 PM, Sam Kong wrote:

    > Hello,
    >
    > 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
    > end
    >
    > But Float number has limitation on precision.
    > Thus the function won't work correctly for big numbers like
    > (123456789123456789).
    >
    > How would you solve such a case?
    > It should be fast as well as correct because I will use it repeatedly.


    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,

    http://www.swox.com/gmp/manual/Perfect-Square-Algorithm.html

    or the one in Pari:

    http://www.ufr-mi.u-bordeaux.fr/~belabas/pari/

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

    Xavier Noria Guest

    On Feb 11, 2007, at 10:48 PM, Xavier Noria wrote:

    > 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.


    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
    else
    return x
    end
    end
    end

    # 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}
    end


    # 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
    end

    require 'benchmark'

    $r = 1000

    # square of 32248581868698698768678697647823648238462348
    $s =
    103997103254216245831009973053627303273419242413513150637645310539211244
    0875299413673104

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

    # 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
    end
    end
    x.report("modular is square (true)") do
    1.upto($r) do
    issquare($s)
    end
    end
    x.report("builtin is square (false)") do
    1.upto($r) do
    sqrt = Math::sqrt($ns)
    $ns == sqrt.floor**2
    end
    end
    x.report("modular is square (false)") do
    1.upto($r) do
    issquare($ns)
    end
    end
    end
     
    Xavier Noria, Feb 12, 2007
    #4
  5. Sam Kong

    Sam Kong Guest

    Hi Joel,

    On Feb 11, 11:37 am, Joel VanderWerf <> wrote:
    > Sam Kong wrote:
    > > Hello,

    >
    > > 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
    > > end

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

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

    >
    > Easy: compare integers rather than floats.
    >
    > x = 123456789123456789
    >
    > sqrt = Math::sqrt(x)
    > p(x == sqrt.floor**2)


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


    >
    > --
    > vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407


    Thanks anyway.

    Sam
     
    Sam Kong, Feb 12, 2007
    #5
  6. Sam Kong

    Sam Kong Guest

    Hi Xavier,

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

    On Feb 12, 10:32 am, Xavier Noria <> wrote:
    > On Feb 11, 2007, at 10:48 PM, Xavier Noria wrote:
    >
    > > 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.

    >
    > 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
    > else
    > return x
    > end
    > end
    > end


    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
    end
    result
    end

    def perfect_square? n
    arr = []
    a = n
    while true
    a, b = a / 100, a % 100
    arr.unshift b
    break if a == 0
    end
    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
    end
    remain == 0
    end

    I felt ashamed to see the code you posted.OTL

    >
    > # 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}
    > end
    >
    > # 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
    > end
    >
    > require 'benchmark'
    >
    > $r = 1000
    >
    > # square of 32248581868698698768678697647823648238462348
    > $s =
    > 103997103254216245831009973053627303273419242413513150637645310539211244
    > 0875299413673104
    >
    > # non-square, the previous number minus 1
    > $ns =
    > 103997103254216245831009973053627303273419242413513150637645310539211244
    > 0875299413673103
    >
    > # 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
    > end
    > end
    > x.report("modular is square (true)") do
    > 1.upto($r) do
    > issquare($s)
    > end
    > end
    > x.report("builtin is square (false)") do
    > 1.upto($r) do
    > sqrt = Math::sqrt($ns)
    > $ns == sqrt.floor**2
    > end
    > end
    > x.report("modular is square (false)") do
    > 1.upto($r) do
    > issquare($ns)
    > end
    > end
    > end


    Thank you for your support.

    Sam
     
    Sam Kong, Feb 12, 2007
    #6
  7. Re: What's the correct and fast way to determine if a (gig) numberis a perfect square?

    Sam Kong wrote:
    > Hi Joel,
    >
    > On Feb 11, 11:37 am, Joel VanderWerf <> wrote:
    >> Sam Kong wrote:
    >>> Hello,
    >>> 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
    >>> end
    >>> But Float number has limitation on precision.
    >>> Thus the function won't work correctly for big numbers like
    >>> (123456789123456789).
    >>> How would you solve such a case?
    >>> It should be fast as well as correct because I will use it repeatedly.

    >> Easy: compare integers rather than floats.
    >>
    >> x = 123456789123456789
    >>
    >> sqrt = Math::sqrt(x)
    >> p(x == sqrt.floor**2)

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


    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.

    --
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Joel VanderWerf, Feb 12, 2007
    #7
  8. Sam Kong

    Sam Kong Guest

    On Feb 12, 12:12 pm, Joel VanderWerf <> wrote:
    > Sam Kong wrote:
    > > Hi Joel,

    >
    > > On Feb 11, 11:37 am, Joel VanderWerf <> wrote:
    > >> Sam Kong wrote:
    > >>> Hello,
    > >>> 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
    > >>> end
    > >>> But Float number has limitation on precision.
    > >>> Thus the function won't work correctly for big numbers like
    > >>> (123456789123456789).
    > >>> How would you solve such a case?
    > >>> It should be fast as well as correct because I will use it repeatedly.
    > >> Easy: compare integers rather than floats.

    >
    > >> x = 123456789123456789

    >
    > >> sqrt = Math::sqrt(x)
    > >> p(x == sqrt.floor**2)

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

    >
    > 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.


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

    Sam

    >
    > --
    > vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Sam Kong, Feb 12, 2007
    #8
  9. Sam Kong

    Phrogz Guest

    On Feb 12, 2:07 pm, "Sam Kong" <> wrote:
    > On Feb 12, 12:12 pm, Joel VanderWerf <> wrote:
    > > 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

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


    For example:
    irb(main):004:0>
    x=981723462487562983749812734972342334123435635465656432452
    => 981723462487562983749812734972342334123435635465656432452

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

    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
    #9
  10. Re: What's the correct and fast way to determine if a (gig) numberis a perfect square?

    Sam Kong wrote:
    >
    > On Feb 12, 12:12 pm, Joel VanderWerf <> wrote:
    >> Sam Kong wrote:
    >>> Hi Joel,
    >>> On Feb 11, 11:37 am, Joel VanderWerf <> wrote:
    >>>> Sam Kong wrote:
    >>>>> Hello,
    >>>>> 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
    >>>>> end
    >>>>> But Float number has limitation on precision.
    >>>>> Thus the function won't work correctly for big numbers like
    >>>>> (123456789123456789).
    >>>>> How would you solve such a case?
    >>>>> It should be fast as well as correct because I will use it repeatedly.
    >>>> Easy: compare integers rather than floats.
    >>>> x = 123456789123456789
    >>>> sqrt = Math::sqrt(x)
    >>>> p(x == sqrt.floor**2)
    >>> Yes. Your approach is better than mine.
    >>> But it gives a wrong answer for big numbers like 55833579873437812.

    >> 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.

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


    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.

    --
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Joel VanderWerf, Feb 12, 2007
    #10
  11. Sam Kong

    Ondrej Bilka Guest

    On Feb 12, 10:33 pm, Joel VanderWerf <> wrote:
    > Sam Kong wrote:
    >
    > > On Feb 12, 12:12 pm, Joel VanderWerf <> wrote:
    > >> Sam Kong wrote:
    > >>> Hi Joel,
    > >>> On Feb 11, 11:37 am, Joel VanderWerf <> wrote:
    > >>>> Sam Kong wrote:
    > >>>>> Hello,
    > >>>>> 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
    > >>>>> end
    > >>>>> But Float number has limitation on precision.
    > >>>>> Thus the function won't work correctly for big numbers like
    > >>>>> (123456789123456789).
    > >>>>> How would you solve such a case?
    > >>>>> It should be fast as well as correct because I will use it repeatedly.
    > >>>> Easy: compare integers rather than floats.
    > >>>> x = 123456789123456789
    > >>>> sqrt = Math::sqrt(x)
    > >>>> p(x == sqrt.floor**2)
    > >>> Yes. Your approach is better than mine.
    > >>> But it gives a wrong answer for big numbers like 55833579873437812.
    > >> 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.

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

    >
    > 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.
    >
    > --
    > vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

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

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,255
  2. Tod Birdsall

    w3wp.exe Allocating Over a Gig of RAM

    Tod Birdsall, Dec 15, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    9,103
    akantos
    Apr 12, 2008
  3. JimmyJohn
    Replies:
    0
    Views:
    352
    JimmyJohn
    Sep 5, 2005
  4. Replies:
    4
    Views:
    529
    Attila Feher
    Dec 31, 2004
  5. Replies:
    26
    Views:
    935
    Chetan
    Oct 28, 2006
Loading...

Share This Page