########################################################################
##
## Copyright (C) 2000-2021 The Octave Project Developers
##
## See the file COPYRIGHT.md in the top-level directory of this
## distribution or .
##
## This file is part of Octave.
##
## Octave is free software: you can redistribute it and/or modify it
## under the terms of the GNU General Public License as published by
## the Free Software Foundation, either version 3 of the License, or
## (at your option) any later version.
##
## Octave is distributed in the hope that it will be useful, but
## WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with Octave; see the file COPYING. If not, see
## .
##
########################################################################
## -*- texinfo -*-
## @deftypefn {} {@var{pf} =} factor (@var{q})
## @deftypefnx {} {[@var{pf}, @var{n}] =} factor (@var{q})
## Return the prime factorization of @var{q}.
##
## The prime factorization is defined as @code{prod (@var{pf}) == @var{q}}
## where every element of @var{pf} is a prime number. If @code{@var{q} == 1},
## return 1. The output @var{pf} is of the same numeric class as the input.
##
## With two output arguments, return the unique prime factors @var{pf} and
## their multiplicities. That is,
## @code{prod (@var{pf} .^ @var{n}) == @var{q}}.
##
## Implementation Note: The input @var{q} must be less than @code{flintmax}
## when the input is a floating point class (double or single).
## @seealso{gcd, lcm, isprime, primes}
## @end deftypefn
function [pf, n] = factor (q)
if (nargin < 1)
print_usage ();
endif
if (! isscalar (q) || ! isreal (q) || q < 0 || q != fix (q))
error ("factor: Q must be a real non-negative integer");
endif
## Special case of no primes less than sqrt (q).
if (q < 4)
pf = q;
n = 1;
return;
endif
cls = class (q); # store class
if (isfloat (q) && q > flintmax (q))
error ("factor: Q too large to factor (> flintmax)");
endif
# The basic idea is to divide by the prime numbers from 1 to sqrt(q).
# But primes(sqrt(q)) can be very time-consuming to compute for q > 1e16,
# so we divide by smaller primes first.
# This won't make a difference for prime q, but it makes a big (100x) difference for large composite q.
# Since there are many more composites than primes, this leads overall to a speedup.
## There is at most one prime greater than sqrt(q), and if it exists,
## it has multiplicity 1, so no need to consider any factors greater
## than sqrt(q) directly. [If there were two factors p1, p2 > sqrt(q),
## then q >= p1*p2 > sqrt(q)*sqrt(q) == q. Contradiction.]
# The following calculation of transition and number of divisors to use was detemined empirically.
# As of 2021 it gives the best overall performance over the range of 1 <= q <= intmax ("uint64").
# For future programmers, check periodically for performance improvements and tune this transition as required.
if (q < 10e9) # sufficiently small q
smallprimes = feval (cls, [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]);
# going up to primes(100) is 3% faster than going up to primes(30) even for the very small q < 1e6.
# increases to 7% faster for 1e9 < q < 10e9.
# smallprimes(smallprimes > q) = []; # only relevant for really small q, unnecessary and slows down for large q.
else # sufficiently large q
smallprimes = primes (feval (cls, q^0.2)); # go up to the 5th root of q for now.
end
# Trials that didn't yield success in 2021:
# persistent smallprimes = primes (FOO) for various fixed FOO in the range 10 <= FOO <= 10e6. (FOO is independent of q)
# The thought had been that making it persistent would cache it so it didn't need to be recomputed for subsequent calls,
# but it slowed it down overall. It seems calling primes twice with smaller q is still faster than one persistent call for a large q.
#
# Also tried variants with:
# smallprimes = primes (q ^ FOO) for various values of FOO.
# For FOO >= 0.25 or FOO <= 0.16, the performance is very poor.
# FOO needs to be in the 0.17 to 0.24 range, somewhat.
# Benchmark experiments indicate it should increase gently from 0.18 to 0.21 as q goes from 10^11 to 10^18.
# But putting in such an expression would require calculating the log of q, which defeats any performance improvement.
# Or a stepwise approximation like:
# foo = 0.18 + 0.01 * (q > 1e12) + 0.01 * (q > 1e14) + 0.01 * (q > 1e16);
# smallprimes = primes (feval (cls, q^foo));
# where the RHS of foo would go from 0.18 to 0.21 over several orders of magnitude without calling the log.
# Obviously that is overly empirical, so putting in q^0.2 seems to be the most robust overall for 64-bit q.
pf = feval (cls, []); # pf will be the list of prime factors returned. We cast it to be the same class as the input.
[pf, q] = reducefactors (q, pf, smallprimes);
# pf will now contain all prime factors of q within smallprimes, including repetitions, in ascending order.
# q itself will be divided by those prime factors to become smaller, unless q was prime to begin with.
# Now we go all the way to sqrt(q), where q is smaller than the original q in most cases.
largeprimes = primes(sqrt(q)); # do not try to weed out the smallprimes inside largeprimes, whether using length(smallprimes) or max(smallprimes) -- it slows it down!
[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 have been pulled out of q in ascending order,
# so no need to sort(pf).
## Determine multiplicity.
if (nargout > 1)
idx = find ([0, pf] != [pf, 0]);
pf = pf(idx(1:length (idx)-1));
n = diff (idx);
endif
endfunction
function [pf, q] = reducefactors (qin, pfin, divisors)
pf = pfin;
q = qin;
divisors = divisors (mod (q, divisors) == 0); # a few milliseconds faster than "divisors(mod(q,divisors) ~= 0) = []"
for pp = divisors # for each factor in turn,
while (mod (q, pp) == 0) # keep extracting all occurrences of that factor
pf(end+1) = pp; # before going to larger factors
q /= pp; # mod() was marginally faster than rem() when assessed over 10e6 trials of the whole factor() function.
endwhile
endfor
endfunction
## Test special case input
%!assert (factor (1), 1)
%!assert (factor (2), 2)
%!assert (factor (3), 3)
%!test
%! for i = 2:20
%! pf = factor (i);
%! assert (prod (pf), i);
%! assert (all (isprime (pf)));
%! [pf, n] = factor (i);
%! assert (prod (pf.^n), i);
%! assert (all ([0,pf] != [pf,0]));
%! endfor
%!assert (factor (uint8 (8)), uint8 ([2 2 2]))
%!assert (factor (single (8)), single ([2 2 2]))
%!test
%! [pf, n] = factor (int16 (8));
%! assert (pf, int16 (2));
%! assert (n, double (3));
## Test input validation
%!error factor ()
%!error factor ([1,2])
%!error factor (6i)
%!error factor (-20)
%!error factor (1.5)
%!error factor (flintmax ("single") + 2)
%!error factor (flintmax ("double") + 2)