Suggestion for improving GNU factor

[Fernando Scandolo]

    Hello and cheers to the GNU team ! I know you must deal with a truckload
of mail every day, so I'll let you opt-out this one. It's a suggestion about
optimizing the factor program, which I guess it's not your biggest concern.
You don't need to read further if you're not interested.
    Keep up the good work ! I'm another GNU/Linux user/advocate, trying hard
to get rid of proprietary software at my workplace...

    Fernando Scandolo
    address@hidden

    The suggestion:

    This morning I got curious about what algorithm was used in factor, so I
downloaded the sh-utils 2.0 source and looked at the source. The main algo
goes like this:

    while (n % 2 == 0)
   {
      assert (n_factors < max_n_factors);
      factors[n_factors++] = 2;
      n /= 2;
    }

[...]

  d = 3;
  do
    {
      q = n / d;
      while (n == q * d)
 {
   assert (n_factors < max_n_factors);
   factors[n_factors++] = d;
   n = q;
   q = n / d;
 }
      d += 2;
    }
  while (d <= q);


    I noticed it tests every odd number, and because of that 1/3 of the
tests are superfluous (multiples of 6). With a little bit of restructuring
and an unroll, it could work faster:

    while (n % 2 == 0)
   {
      assert (n_factors < max_n_factors);
      factors[n_factors++] = 2;
      n /= 2;
    }

    while (n % 3 == 0)
   {
      assert (n_factors < max_n_factors);
      factors[n_factors++] = 3;
      n /= 3;
    }

  d = 5;
  do
    {
      q = n / d;
      while (n == q * d)
     {
       assert (n_factors < max_n_factors);
       factors[n_factors++] = d;
       n = q;
       q = n / d;
     }
     d += 2;

    if (d <= q) break;

      q = n / d;
      while (n == q * d)
     {
       assert (n_factors < max_n_factors);
       factors[n_factors++] = d;
       n = q;
       q = n / d;
     }
     d += 4;
    }
  while (d <= q);


    I hope this is of use. It's quite trivial, it must have been overlooked
because of it's low importance. But I couldn't just keep my big mouth shut
=)



_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com