squarerootconstraints.halleck.c:

/* Factoring by square root constraint. */
#include <stdio.h>

long N, S, R, P, Q, A, D, T;

/* Integer square root by Halleck's method, with Legalize's speedup */
/* Modified to leave remainder */
long remainder;
long isqrt (x) long x;{
  long   squaredbit, root;
   if (x<1) return 0;
   squaredbit  = (long) ((((unsigned long) ~0L) >> 1) & 
                        ~(((unsigned long) ~0L) >> 2));
   /* Form bits of the answer. */
   remainder = x;  root = 0;
   while (squaredbit > 0) {
     if (remainder >= (squaredbit | root)) {
         remainder -= (squaredbit | root);
         root >>= 1; root |= squaredbit;
     } else { root >>= 1; }
     squaredbit >>= 2; 
   }
   return root;
}

main () {
   printf ("Number to factor?\n");
   scanf  ("%ld", &N); printf ("N = %ld\n", N);
   if (N < 0) {
      printf ("Number must be positive\n");
      return -1;
   } else if (N == 0) {
      printf ("0 is a factor\n");
      return 0;
   }
   S = isqrt(N);
   if (remainder == 0) {
      printf ("%ld is a factor\n",S);
      return S; 
   }
   R = N - S*S;
   for (D=1; 1; D++) {
       T = isqrt (D*D + 2*S*D - R);
       if (remainder == 0) {
          A = T - D;
          P = S - A;
          printf ("%ld is a factor\n",P);
          return P;
       }
   }
}

Go to ...

• Factoring Page
• John Halleck's Home Page

This page is http://www.cc.utah.edu/~nahaj/factoring/squarerootconstraints.halleck.c.html
© Copyright 2000 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 18th, 2001
And the underlying file was last modified on January 16th, 1998