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
[EMAIL PROTECTED]
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
_______________________________________________
Bug-sh-utils mailing list
[EMAIL PROTECTED]
http://mail.gnu.org/mailman/listinfo/bug-sh-utils
