bug-sh-utils
[Top][All Lists]

## Suggestion for improving GNU factor

 From: Fernando Scandolo Subject: Suggestion for improving GNU factor Date: Fri, 20 Jul 2001 16:18:41 -0300

```    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

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!?