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.
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
stackoverflow.com
twitter.com
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
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
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.