• Post Reply Bookmark Topic Watch Topic
  • New Topic

How to find if a BigInteger is square  RSS feed

 
Tiberius Marius
Ranch Hand
Posts: 115
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser Java Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That isn't a Project Euler question, is it?
 
Tiberius Marius
Ranch Hand
Posts: 115
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
C++ Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!