octave: scripts/specfun/factor.m annotate

annotate scripts/specfun/factor.m @ 26376:00f796120a6d stable

maint: Update copyright dates in all source files.

author	John W. Eaton <jwe@octave.org>
date	Wed, 02 Jan 2019 16:32:43 -0500
parents	996d78102a71
children	b442ec6dda5c

rev	line source
26376 00f796120a6d maint: Update copyright dates in all source files. John W. Eaton <jwe@octave.org> parents: 25436 diff changeset	1 ## Copyright (C) 2000-2019 Paul Kienzle
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	2 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	3 ## This file is part of Octave.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	4 ##
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	5 ## Octave is free software: you can redistribute it and/or modify it
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	6 ## under the terms of the GNU General Public License as published by
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	7 ## the Free Software Foundation, either version 3 of the License, or
22755 3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	8 ## (at your option) any later version.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	9 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	10 ## Octave is distributed in the hope that it will be useful, but
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
22755 3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	13 ## GNU General Public License for more details.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	14 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	15 ## You should have received a copy of the GNU General Public License
7016 93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe] jwe parents: 7001 diff changeset	16 ## along with Octave; see the file COPYING. If not, see
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	17 ## <https://www.gnu.org/licenses/>.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	18
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	19 ## -- texinfo --
20852 516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files. Rik <rik@octave.org> parents: 20486 diff changeset	20 ## @deftypefn {} {@var{pf} =} factor (@var{q})
516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files. Rik <rik@octave.org> parents: 20486 diff changeset	21 ## @deftypefnx {} {[@var{pf}, @var{n}] =} factor (@var{q})
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	22 ## Return the prime factorization of @var{q}.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	23 ##
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	24 ## The prime factorization is defined as @code{prod (@var{pf}) == @var{q}}
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	25 ## where every element of @var{pf} is a prime number. If @code{@var{q} == 1},
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	26 ## return 1. The output @var{pf} is of the same numeric class as the input.
19593 446c46af4b42 strip trailing whitespace from most source files John W. Eaton <jwe@octave.org> parents: 17744 diff changeset	27 ##
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	28 ## With two output arguments, return the unique prime factors @var{pf} and
21546 f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total). Rik <rik@octave.org> parents: 20852 diff changeset	29 ## their multiplicities. That is,
f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total). Rik <rik@octave.org> parents: 20852 diff changeset	30 ## @code{prod (@var{pf} .^ @var{n}) == @var{q}}.
19596 0e1f5a750d00 maint: Periodic merge of gui-release to default. John W. Eaton <jwe@octave.org> parents: 19152 19593 diff changeset	31 ##
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	32 ## Implementation Note: The input @var{q} must be less than @code{flintmax}
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	33 ## (9.0072e+15) in order to factor correctly.
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	34 ## @seealso{gcd, lcm, isprime, primes}
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	35 ## @end deftypefn
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	36
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	37 ## Author: Paul Kienzle
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	38
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	39 function [pf, n] = factor (q)
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	40
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	41 if (nargin != 1)
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	42 print_usage ();
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	43 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	44
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	45 if (! isscalar (q) \|\| ! isreal (q) \|\| q < 0 \|\| q != fix (q))
cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	46 error ("factor: Q must be a real non-negative integer");
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	47 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	48
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	49 ## Special case of no primes less than sqrt(q).
c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	50 if (q < 4)
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	51 pf = q;
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	52 n = 1;
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	53 return;
11587 c792872f8942 all script files: untabify and strip trailing whitespace John W. Eaton <jwe@octave.org> parents: 11523 diff changeset	54 endif
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	55
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	56 cls = class (q); # store class
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	57 q = double (q); # internal algorithm relies on numbers being doubles.
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	58 qorig = q;
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	59 pf = [];
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	60 ## There is at most one prime greater than sqrt(q), and if it exists,
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	61 ## it has multiplicity 1, so no need to consider any factors greater
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	62 ## than sqrt(q) directly. [If there were two factors p1, p2 > sqrt(q),
21751 b571fc85953f maint: Use two spaces after period to indicate sentence break. Rik <rik@octave.org> parents: 21546 diff changeset	63 ## then q >= p1p2 > sqrt(q)sqrt(q) == q. Contradiction.]
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	64 p = primes (sqrt (q));
c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	65 while (q > 1)
c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	66 ## Find prime factors in remaining q.
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	67 p = p(rem (q, p) == 0);
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	68 if (isempty (p))
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	69 ## Can't be reduced further, so q must itself be a prime.
c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	70 p = q;
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	71 endif
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	72 pf = [pf, p];
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	73 ## Reduce q.
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	74 q /= prod (p);
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	75 endwhile
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	76 pf = sort (pf);
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	77
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	78 ## Verify algorithm was successful
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	79 q = prod (pf);
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	80 if (q != qorig)
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	81 error ("factor: Q too large to factor");
20486 4bb41929286b Deprecate bitmax. Kai T. Ohlhus <k.ohlhus@gmail.com> parents: 19833 diff changeset	82 elseif (q >= flintmax ())
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	83 warning ("factor: Q too large. Answer is unreliable");
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	84 endif
e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	85
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	86 ## Determine multiplicity.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	87 if (nargout > 1)
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	88 idx = find ([0, pf] != [pf, 0]);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	89 pf = pf(idx(1:length (idx)-1));
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	90 n = diff (idx);
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	91 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	92
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	93 ## Restore class of input
25436 996d78102a71 maint: Strip trailing whitespace from source files. John W. Eaton <jwe@octave.org> parents: 25270 diff changeset	94 pf = feval (cls, pf);
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	95
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	96 endfunction
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	97
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	98
f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	99 %!assert (factor (1), 1)
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	100 %!test
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	101 %! for i = 2:20
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	102 %! pf = factor (i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	103 %! assert (prod (pf), i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	104 %! assert (all (isprime (pf)));
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	105 %! [pf, n] = factor (i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	106 %! assert (prod (pf.^n), i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	107 %! assert (all ([0,pf] != [pf,0]));
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	108 %! endfor
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	109
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	110 %!assert (factor (uint8 (8)), uint8 ([2 2 2]))
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	111 %!assert (factor (single (8)), single ([2 2 2]))
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	112 %!test
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	113 %! [pf, n] = factor (int16 (8));
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	114 %! assert (pf, int16 (2));
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	115 %! assert (n, double (3));
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	116
19833 9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions. Rik <rik@octave.org> parents: 19697 diff changeset	117 ## Test input validation
17716 e48f5a52e838 factor.m: Warn when the input is too large to calculate reliable answer. Doug Stewart <doug.dastew@gmail.com> parents: 14868 diff changeset	118 %!error factor ()
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	119 %!error factor (1,2)
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	120 %!error <Q must be a real non-negative integer> factor (6i)
cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	121 %!error <Q must be a real non-negative integer> factor ([1,2])
cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	122 %!error <Q must be a real non-negative integer> factor (1.5)
cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	123 %!error <Q must be a real non-negative integer> factor (-20)

Mercurial > octave

annotate scripts/specfun/factor.m @ 26376:00f796120a6d stable