How to calculate the number of squares needed to exceed 1 million before doing any squaring

Question

This code prompts the user to enter a valid integer and repeatedly square the integer until it exceeds 1 million. It is also type-safe. Is there a way I can calculate the number of squares of it will take for an integer to exceed 1 million before my program does any squaring?

import java.util.Scanner;

public class Squaring{

public static void main (String [] args) {

Scanner scan = new Scanner(System.in);
long number;
long number2;
int count = 0;
number = getInt("Enter an integer greater than 1:",scan);

while ( number <= 1) {
  scan.nextLine();
  System.out.println(number +" is not greater than 1.");
  number = getInt("Enter an integer greater than 1:",scan);

}
number2 = number;
while ( number < 1000000) {
  number = number * number;
  System.out.println(number);
  count++;
}      

System.out.println(number2 + " exceeded 1,000,000 after "+ count + " squarings.");  }  

public static int getInt(String prompt, Scanner scan) {

int input;    
System.out.println( prompt );
while ( !scan.hasNextInt() ) { 
  String garbage = scan.nextLine(); 
  System.out.println( garbage + " is not valid input.\n" + prompt);
}

input = scan.nextInt();

return input;
} 
}

Answer 1

To my best knowledge, it appears that instead of having to slowly loop through the square roots, the # of squaring's required are essentially governed by this formula (those are division signs) :

ceiling( log(         log(target) 
          .                ÷ 
          .        log(base-to-square)
          .
          .  ) ÷ log(2) )

And the 3rd column indeed matches what @hunteke described :

.  1000000  1        inf  1             0
.  1000000  2        5    4294967296    1
.  1000000  3        4    43046721      1
.  1000000  4        4    4294967296    1
.  1000000  5        4    152587890625  1

.  1000000  6        3    1679616       1
.  1000000  7        3    5764801       1
.  1000000  8        3    16777216      1
.  1000000  9        3    43046721      1
.  1000000  10       3    100000000     1

.  1000000  11       3    214358881     1
.  1000000  12       3    429981696     1
.  1000000  13       3    815730721     1
.  1000000  14       3    1475789056    1
.  1000000  971      2    888949151281  1

.  1000000  66508    1    4423314064    1
.  1000000  132045   1    17435882025   1
.  1000000  197582   1    39038646724   1
.  1000000  263119   1    69231608161   1
.  1000000  328656   1    108014766336  1

.  1000000  394193   1    155388121249  1
.  1000000  459730   1    211351672900  1
.  1000000  525267   1    275905421289  1
.  1000000  590804   1    349049366416  1
.  1000000  656341   1    430783508281  1

.  1000000  721878   1    521107846884  1
.  1000000  787415   1    620022382225  1
.  1000000  852952   1    727527114304  1
.  1000000  918489   1    843622043121  1
.  1000000  984026   1    968307168676  1

.  1000000  1000000  0    1000000       1 ***

.  1000000  1049563  0    1049563       1
.  1000000  1115100  0    1115100       1
.  1000000  1180637  0    1180637       1
.  1000000  1246174  0    1246174       1

.  1000000  1311711  0    1311711       1
.  1000000  1377248  0    1377248       1
.  1000000  1442785  0    1442785       1
.  1000000  1508322  0    1508322       1

numbers at or above the target would get zero (0) returned, since you've already above the target to begin with.

granted, pure squaring isn't remotely close to optimal, since it way overshoots for most scenarios.

Answer 2

Yes. Shy of using a more elegant Algebraic method, use an if-check based on precalculation and working backwards:

1e6
^ 0.5  = 1000      (1)
^ 0.5 ~=   31.6    (2)
^ 0.5 ~=    5.6    (3)
^ 0.5 ~=    2.4    (4)
^ 0.5 ~=    1.5    (5)

Since you've specified integer input (and assuming positive), you can get some bounds right quick. To exceed a million:

• a value of 1 or less will never get there,
• a value of 2 will take 5 squaring operations,
• values 3 to 5 will take 4 squaring operations,
• values 6 to 31 will take 3 squaring operations,
• values 32 to 999 will take 2 squaring operations,
• and values 1000 to 999,999 will take only 1 squaring operation.

Now your algorithm is reduced to a simple if-check.