Re: isqrt tweak and factor(1) questions

On Thu, Feb 5, 2026 at 1:42 AM David Sparks <[email protected]> wrote:
> > Adding more code to trial division loop will cause additional
> > register pressure (=> slower code).
>
> I should have a look.  Are you worried about speed or size more
> here?

Obviously, trial division loop should be optimized for speed.

> If you want an unpacked wheel, I can generate it on the fly with
> smaller code than the current packed table, and barely more time.

Sure, show me a patch. Can you generate a larger wheel?
How much speedup this larger wheel gives us
"we skip N% more integers for 'factor 18446744073709551557' run"?

I imagine keeping the wheel smaller than L1D might be better,
or else cache misses may become dominant.

> (Q: On which platform do you generally run bloat-o-meter?)

x86.

> > Tell me what I'm missing.
>
> I screwed up my example.  If N = p^3, *then* it'll divide by p,
> notice that p^2 is square, and start trial dividing again.

So.. 1229*7207*7207 = 63835303421

factorize(63835303421) will eventually find the 1229 divisor,
divide by it, discover that N/1229 is a square, and
then will call factorize(7207). Which will try divisors below 1229
again.

Yes, this can be improved.
_______________________________________________
busybox mailing list
[email protected]
https://lists.busybox.net/mailman/listinfo/busybox