Tiberius Marius

Ranch Hand

Posts: 115

3

posted 3 years ago

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

(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

posted 3 years ago

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.

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.

K. Tsang OCPJP7 OCMJEA6

posted 3 years ago

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

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 = 9223372091666259081Long.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

posted 3 years ago

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

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

posted 3 years ago

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

Assuming you are

Winston

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Campbell Ritchie

Marshal

Posts: 56570

172

Tiberius Marius

Ranch Hand

Posts: 115

3

posted 3 years ago

No , it 's from the book Intro in Java Programming 10th edition by Daniel Liang , chapter 10 exercise 17

posted 3 years ago

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

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.

"Il y a peu de choses qui me soient impossibles..."

Consider Paul's rocket mass heater. |