programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# How to find if a BigInteger is square

Tiberius Marius
Ranch Hand
Posts: 115
3
I have a program i m not sure how to implement :

(Square numbers) Find the first ten square numbers that are greater than Long.MAX_VALUE . A square number is a number in the form of n 2 . For example, 4, 9, and 16 are square numbers. Find an efficient approach to run your
program fast.

I found two ways of solving this but i think both are way inefficient :

-A square number can be divided in lesser square numbers :
what's the square of 36 ? 36 is 2 * 3 * 2 * 3 => 4 * 9 => square is 2 * 3

-second option is to estimate a number and increase it or decrease it based on how close that number * number is to the BigInteger starting number , as as it gets closer the delta gets smaller until it gets to 1

K. Tsang
Bartender
Posts: 3648
16
Interesting problem. Let me have a crack at it.

First I need to know what Long.MAX_VALUE is. Then find the closest square number to this value (may be smaller or larger than MAX_VALUE). Once I have that, called this "x", depending on x is smaller or larger than MAX_VALUE:

if x is smaller => (x+1)^2 would be > than MAX_VALUE
(x+1)^2 to (x+10)^2

if x is larger => x^2 already fulfill your criteria; maybe want to get (x-1)^2 too
x^2, (x+1)^2, ... to (x+9)^2

I just thought of this out of my head which may also be inefficient.

Paweł Baczyński
Bartender
Posts: 2086
44
• 2
I would find floor of square root of Long.MAX_VALUE. Let's call it x.
Then I would calculate (x+1)^2, (x+2)^2 etc...

3037000499 * 3037000499 = 9223372030926249001
Long.MAX_VALUE = 9223372036854775807
1: 3037000500 * 3037000500 = 9223372037000250000
2: 3037000501 * 3037000501 = 9223372043074251001
3: 3037000502 * 3037000502 = 9223372049148252004
4: 3037000503 * 3037000503 = 9223372055222253009
5: 3037000504 * 3037000504 = 9223372061296254016
6: 3037000505 * 3037000505 = 9223372067370255025
7: 3037000506 * 3037000506 = 9223372073444256036
8: 3037000507 * 3037000507 = 9223372079518257049
9: 3037000508 * 3037000508 = 9223372085592258064
10: 3037000509 * 3037000509 = 9223372091666259081

Tiberius Marius
Ranch Hand
Posts: 115
3
Paweł Baczyński wrote:I would find floor of square root of Long.MAX_VALUE. Let's call it x.
Then I would calculate (x+1)^2, (x+2)^2 etc...

3037000499 * 3037000499 = 9223372030926249001
Long.MAX_VALUE = 9223372036854775807
1: 3037000500 * 3037000500 = 9223372037000250000
2: 3037000501 * 3037000501 = 9223372043074251001
3: 3037000502 * 3037000502 = 9223372049148252004
4: 3037000503 * 3037000503 = 9223372055222253009
5: 3037000504 * 3037000504 = 9223372061296254016
6: 3037000505 * 3037000505 = 9223372067370255025
7: 3037000506 * 3037000506 = 9223372073444256036
8: 3037000507 * 3037000507 = 9223372079518257049
9: 3037000508 * 3037000508 = 9223372085592258064
10: 3037000509 * 3037000509 = 9223372091666259081

Yes , thanks . So easy when you put it that way :P

Winston Gutkowski
Bartender
Posts: 10575
66
Tiberius Marius wrote:I have a program i m not sure how to implement :

Well, one thing to think about it is that √x can also be written as x^(1/2), so the square root of Long.MAX_VALUE, which is 2⁶³-1, must be very close to 2^(31.5), which must lie between 2³¹ and 2³².

Assuming you are not allowed to use a sqrt() function, you can nevertheless use a binary chop to find, as Pawel says, the floor of √Long.MAX_VALUE (ie, the maximum integer value n, where n² < Long.MAX_VALUE) - which should take no more than 30 guesses - and after that, do exactly as he suggests.

Winston

Campbell Ritchie
Marshal
Posts: 56570
172
That isn't a Project Euler question, is it?

Tiberius Marius
Ranch Hand
Posts: 115
3
No , it 's from the book Intro in Java Programming 10th edition by Daniel Liang , chapter 10 exercise 17

Stevens Miller
Bartender
Posts: 1445
30
Tiberius Marius wrote:-A square number can be divided in lesser square numbers :
what's the square of 36 ? 36 is 2 * 3 * 2 * 3 => 4 * 9 => square is 2 * 3

That won't always be the case. Any number whose square root is prime can't be further divided.

 Consider Paul's rocket mass heater.