#include <math.h>
#include <iostream>
#include <strstream>
#include <string>

// Written by Owen O'Malley (owenomalley@alumni.uci.edu)
// compile with: g++ -O sqrt.cc -lcln -lm

#define WANT_OBFUSCATING_OPERATORS
#include <cl_integer.h>
#include <cl_integer_io.h>

/* #define PRINT_TIMES */

#ifdef PRINT_TIMES
#include <time.h>
#endif

int main(int argc, char *argv[]) {
  int max_digits;
  int digits;
  int next_digit;
  int orig_number;

  cout << "Square root for integers:\n\n";
  cout << "Enter the number to square root: ";
  cin >> orig_number;
  cout << "\nEnter the number of digits desired: ";
  cin >> max_digits;

#ifdef PRINT_TIMES
  long Clock_Time[max_digits+1];  // Declare a structure for keeping times
#endif

  cout << "\nWorking... (" << orig_number << ":" << max_digits << ")\n\n";

  // Find how many digits are in the integer portion of the answer
  int final_length = int(floor(log10(1.0 * orig_number)))/2 + 1;
  cl_I remainder = orig_number;
  cl_I result = 0;
  cl_I decr_size;

     // Find each digit starting with most significant
  for (digits=0; digits<max_digits; digits++) {

#ifdef PRINT_TIMES
     Clock_Time[digits] = clock() * (1000 / CLOCKS_PER_SEC);
#endif

     decr_size = result * 20 + 1;

        // Guess digits from 0 to 9
        // We are trying to solve (result * 20 + next_digit) * next_digit
        //    for the smallest positive remainder.
     for (next_digit=0; 
          remainder >= decr_size; 
          next_digit++) {
        remainder -= decr_size;
        decr_size += 2;
     }
        // Bring two more places into the remainder
     remainder *= 100;
        // Save digit in result
     result = result * 10 + next_digit;
  }

#ifdef PRINT_TIMES
  Clock_Time[digits] = clock();
#endif

  cout << "The answer is:" << endl;

  // Save the number into a string stream
  ostrstream ostr;
  ostr << result;
  char *str_result = ostr.str();

  // Write out the integer portion of the answer
  cout.write(str_result, final_length);
  cout << ".";

  // Write out the decimal portion of the answer, with at most 72 characters
  // per a line.
  const int max_length = 72;
  int line_start = final_length;
  // Take into account that we already printed some on this line
  int line_length = max_length - final_length - 1;
  int remaining_chars = ostr.pcount() - final_length;

  // Loop through until there are no more characters
  while (remaining_chars > 0) {
    int line_chars = (line_length < remaining_chars ? 
                      line_length : 
                      remaining_chars);
    cout.write(str_result + line_start, line_chars);
    cout << "\n";
    line_start += line_chars;
    remaining_chars -= line_chars;
    line_length = max_length;
  }

#ifdef PRINT_TIMES
  {
   int i;
   for (i=1;i<=max_digits;i++) {
      clog << i << " " << Clock_Time[i] << "\n";
   }
  }
#endif
  return 0;
}