Mercurial > jwe > octave
changeset 31113:6ee5bd9ad7cc
maint: merge stable to default
author | Arun Giridhar <arungiridhar@gmail.com> |
---|---|
date | Sat, 25 Jun 2022 16:40:58 -0400 |
parents | d98abdd15d40 (current diff) bbb59cc6698c (diff) |
children | e8238ae72381 |
files | |
diffstat | 1 files changed, 24 insertions(+), 16 deletions(-) [+] |
line wrap: on
line diff
--- a/scripts/specfun/factor.m Thu Jun 23 15:23:57 2022 -0400 +++ b/scripts/specfun/factor.m Sat Jun 25 16:40:58 2022 -0400 @@ -150,23 +150,31 @@ ## q itself will be divided by those prime factors to become smaller, ## unless q was prime to begin with. - ## Now go all the way to sqrt(q), where q is smaller than the original q in - ## most cases. - ## - ## Note: Do not try to weed out the smallprimes inside largeprimes, whether - ## using length(smallprimes) or max(smallprimes) -- it slows it down! - largeprimes = primes (sqrt (q)); - [pf, q] = reducefactors (q, pf, largeprimes); + if (isprime (q)) + ## This is an optimization for numbers like 18446744073709551566 + ## == 2 * 9223372036854775783, where the small factors can be pulled + ## out easily and the remaining is prime. This optimization reduces + ## 14.3 s to 1.8 ms (8000X faster) for such cases. + pf(end+1) = q; + else + ## Now go all the way to sqrt(q), where q is smaller than the original q in + ## most cases. + ## + ## Note: Do not try to weed out the smallprimes inside largeprimes, whether + ## using length(smallprimes) or max(smallprimes) -- it slows it down! + largeprimes = primes (sqrt (q)); + [pf, q] = reducefactors (q, pf, largeprimes); - ## At this point, all prime factors <= the sqrt of the original q have been - ## pulled out in ascending order. - ## - ## If q = 1, then no further primes are left. - ## If q > 1, then q itself must be prime, and it must be the single prime - ## factor that was larger than the sqrt of the original q. - if (q > 1) - pf(end+1) = q; - endif + ## At this point, all prime factors <= the sqrt of the original q have been + ## pulled out in ascending order. + ## + ## If q = 1, then no further primes are left. + ## If q > 1, then q itself must be prime, and it must be the single prime + ## factor that was larger than the sqrt of the original q. + if (q > 1) + pf(end+1) = q; + endif + end ## At this point, all prime factors have been pulled out of q in ascending ## order. There is no need to sort(pf).