Computes the square roots of integers to arbitrary precision.

sqrt.cc

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

// Written by Owen O'Malley ([email protected])
// compile with: g++ -O sqrt.cc -lcln -lm

#define WANT_OBFUSCATING_OPERATORS
#include <cln/integer.h>
#include <cln/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;

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

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

  std::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;
  cln::cl_I remainder = orig_number;
  cln::cl_I result = 0;
  cln::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() * 1000L) / 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() * 1000L) / CLOCKS_PER_SEC;
#endif

  std::cout << "The answer is:\n";

  // Save the number into a string stream
  std::stringstream ostr;
  ostr << result;
  std::string str_result = ostr.str();

  // Write out the integer portion of the answer
  std::cout << str_result.substr(0, final_length) << ".";

  // 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 = str_result.length() - 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);
    std::cout << str_result.substr(line_start, line_chars) << "\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++) {
     std::cout << i << " " << Clock_Time[i] << "\n";
   }
  }
#endif
  return 0;
}