I'm looking for the most efficient way to test whether a number is a square

I'm looking for the most efficient way to test whether a number is a square

8 => false
9 => true
10 => false
11 => false
etc.

This is about the algorithm.
For given code, Python would help.
Haskell is okay too.
C++ if necessary.

Other urls found in this thread:

en.wikipedia.org/wiki/Methods_of_computing_square_roots
stackoverflow.com/questions/12862637/perfect-square-or-not
twitter.com/SFWRedditVideos

Do your own homework Rasheed Majin paffuril loo

I think this gif would be better if it clearly showed the winners, I don't want to watch it multiple times to compare one by one.

I was doing the exact same thing!

you can find it in log(n) by testing the sequence square(1), square(2), square(4), square(8)... until its greater than or equal to n

def check_square(num):
root = int(math.sqrt(num))
if root * root != num:
return False
return True

Gonna help you with your homework kid.
var % 2 == 0

There you go.

Why do you choose arguments 2^n?

this is similar to what I found on a Mathematica forum, where they effectively do

root = math.sqrt(num)
return int(root) == root:

not sure if that's translatable to Python

otherwise it would be O(n)

All odd numbers are a square confirmed

yeah, so it seems like Python accepts this.

not sure if this is most effective, tho

var is a reserved keyword desu

Google what a modulus operator is and what you can use it for, not going to give you the super hard 3 lines of code of your homework you have to at least type the conditionals :^)

>var is a reserved keyword desu
Oh shit no OP is doomed it won't compile.

Every number is a square has exactly one bit in it's binary representation.

2 = 0b10
4 = 0b100
8 = 0b1000
16 = 0b10000
etc.

So,
bool checksquare(int num){
return (__builtin_popcount(num) == 1);
}

is the best you can get.

friendly reminder pie are squared.

You should feel embarrassed.

Please be bait.

>8

wtf

I really hope this is bait.

> let f = all (even . length) . group . primeFactors
> map f [8,9,10,11]
[False,True,False,False]

>primeFactors
yes, indeed, how efficient.

OP here, thanks for your input

I've run into nasty long type incapabilities of Python and I don't feel like perusing this path further right now..

true if round(sqrt(input)) == sqrt(input)
false otherwise

linear time, 4 operations
write it yourself you lazy bastard

>linear
constant, I'm retarded

Here is the correct answer in python, it will work with integers of any length
def intSqrt(N):
if N == 0: return 0
a = 1 > 1); b = a+1
while b > a:
b, a = a, a + N//a >> 1
return b

def isSquare(x):
return intSqrt(x)**2 == x

import sys, math

def square_check(number):
i = float(1)
while i:
if math.pow(i, 2) == number:
return True
elif i == sys.float_info.max:
return False

number = input()
print(square_check(number))

Fuck I forgot to increment i

1001

just check if the sqrt(n) is a whole number.

fucking finally someone who isn't a brainlet

>just check the square root bro, floating points won't let you down

op didn't state floating point math was used anywhere in his post

math.sqrt is floating point math

none of the posts linked specified a language, so you can assume they're pseudocode
i.e. your statement about math.sqrt() goes out the window

...

Why are they all typeconverting the root to int unless math.sqrt returns a float?

because you can reasonably assume that a pseudocode sqrt() returns a decimal (whether float or not is irrelevant)

Decimals have bounded precision just like floats, so you would still be a brainlet if you thought they wouldn't let you down

What do you mean by "number"? If it is a usual int32 then you can utilize a lookup table with all the square numbers in range.

1) Take square root of n. Call it sn.
2) Take the floor of sn. Also take the floor of sn and then add one.
3) Separately square them. Does either one equal n?
4) If yes, then n is a square. If no, then it isn't.

Two checks is less efficient but accounts for potential rounding errors in compilers.

>Decimals have bounded precision just like floats
Oh really? Why don't you write down the decimal representation of 1/3?

This is the absolute state of C cucks.

1/3 is not the square root of an integer kiddo
Furthermore a standard decimal data type would round 1/3 to a specified number of digits
How about you write down the decimal representation of sqrt(3) ?

I honestly can't tell if you're baiting or retarded

I was under the impression that modern processors have an instruction that checks if a number is square root. Calling that is going to be faster than anything you can write.

In base 12, it is 0.4

OP asked for an algorithm.

You sound like a nice, quiet and smart person user, the kind of guy who only speaks to crack up a great joke. Have a nice day :-)

if sqrt(n)%2 == 0 or (sqrt(n)-1)%2 == 0
n is a square

the instruction underneath has an algorithm that drives it

>>> math.sqrt(10**50+1)%2 == 0
True

Is 10**50 + 1 a square?

there are instructions that calculate the square root, but i don't think there are instructions that check if a number is a square number
and anyway, even if it turns out i'm wrong, you can't just say "the assembly instruction is faster than rewriting its algorithm in a high level language" as an answer to "what's the fastest algorithm"

Compute the square root; round to the nearest integer; test if that integer squared is the original number.
(define (sqrt x)
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.1))
(define (improve guess)
(average guess (/ x guess)))
(sqrt-iter 1.0))

In C it would be
double sqrt(double x)
{
double guess = 1.0;
while (abs(guess * guess - x) < 0.1)
guess = (guess + (x / guess)) / 2;
return guess;
}
[\code]

why can't I say that

Because it's the same algorithm with a constant language-implementation overhead
It would have the same algorithmic complexity in assembly and in finger-counting

en.wikipedia.org/wiki/Methods_of_computing_square_roots

haskell:
> let sqrt x = head . dropWhile ((>=0.1) . abs . (x-) . (^2)) $ iterate (\g -> (g + x/g)/2) 1
> sqrt 25
5.000023178253949

Most computationally "efficient" in the average case is dynamic programming and a lookup table

Problem has insufficient bounds.

Hope this helps OP =).

def check_square(n):
for m in range(1, n / 2 + 1, 2):
n -= m
if n == 0:
return True
return False


There are many optimizations possible.

didn't bother to check, but should work


int
is_square(int n)
{
for(int k = 0; n >= 0; k++) {
n -= (2 * k) + 1
}

return n == 0;
}

whops, I checked and it was wrong, should works with n strictly greater than 0 in the for loops rather than greater equal than zero
int
is_square(int n)
{
for(int k = 0; n > 0; k++)
n -= (2 * k) + 1

return n == 0;
}

You were too late m8

Consider the following:
def is_square(x):
feh = x.bit_length()

n = 1 1)

if feh & 1:
n >>= 1

while n

but is wrong.

check_square(9) -> False
check_square(1) -> False

Hence I'm not l8, m8

And here's the fastest algorithm I could muster:
def is_square(x):
o = 0
p = 1 > 1)
while p:
t = o + p
s = t * t
if s < x:
o = t
elif s == x:
return True
p >>= 1
return False

O(log(x)), or, less formally, O(ceil(log(x)/2)).

...

This algorithm will do the same thing but with square root as many loop runs (because Newton's method converges quadratically)
So I'm pretty sure it's faster but I don't know how expensive long division is

int is_square(float s){

if (s > 100000){
printf("Illegal argument exception!");
}


for (int i = 0; i < 100; i++){
if (i*i == s){
printf("It's square! You go girl!");
return 1;
}
}

return 0

}

harder problem please

i=1
j=1
k=1

n=input("Introduce un numero ")

while(i

stackoverflow.com/questions/12862637/perfect-square-or-not

An algorithm wouldn't necessarily have the same complexity in assembly and finger counting. The model of computation you use can impact the complexity of your algorithms. Famously, this is why Quantum computers can be "faster", but it also shows up in many other scenarios.

For instance, if you are searching a long row of books sorted algorithmically, a binary search won't be the most evenings efficient algorithm (since the cost of moving from the nth to mth book is O(|n-m|) in reality, rather than O(1) like on a standard computer).

def squared(i):
j=1
k=1

while (j

1 + 3 + ... + (n*2+1) = (n+1)^2
(n+1)^2 + ((n+1)*2 +1) = n^2 + 2n + 1 + 2n + 2 + 1
= n^2 + 4n + 4

(n+2)^2 = n^2 + 4n + 4

It checks out.

I love this gif

fuckin nerds lmao

>math.sqrt(10**50+1)

that evaluates the same as 10**50, test it, it's a problem with python not my solution
and I said sqrt(n)-1 not sqrt(n-1)

you say it like it's a bad thing.

bool hasRoot(unsigned long long num)
{
return floor(sqrt(num)) == sqrt(num);
}

Interesting, but not exactly a fast method.

10**50+1 IS the n that you're testing, and your stupid code failed
>it's a problem with python not my solution
You can't just leave "arbitrary precision sqrt" as a black box, it has no standard implementation. So your """solution""" fails in all non-trivial cases.