octave: scripts/specfun/factor.m annotate

annotate scripts/specfun/factor.m @ 31548:c8ad083a5802 stable

maint: Clean up m-files before Octave 8.1 release. * external.txi, oop.txi, Table.h, documentation.cc, gui-preferences-ed.h, lo-specfun.cc, range.tst : Eliminate triple newlines. * Map.m, MemoizedFunction.m, delaunayn.m, inputParser.m, __publish_latex_output__.m, publish.m, unpack.m, fminbnd.m, __add_default_menu__.m, gammainc.m, gallery.m, hadamard.m, weboptions.m: Add newline after keyword "function" or before keyword "endfunction" for readability. * getaudiodata.m, pkg.m : Add semicolon to end of line for error() statement. * movegui.m: Combine mutliple calls to set() into one for performance. * __unimplemented__.m (missing_functions): Remove missing functions that have been implemented. * __vectorize__.m, check_default_input.m, betaincinv.m, gammaincinv.m: Remove semicolon at end of line with "function" declaration. * weboptions.m: Remove semicolon at end of line with "if" keyword. * integrate_adaptive.m, factor.m: Use keyword "endif" rather than bare "end".

author	Rik <rik@octave.org>
date	Fri, 25 Nov 2022 21:23:54 -0800
parents	658cce403bc7
children	597f3ee61a48

rev	line source
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	1 ########################################################################
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	2 ##
30564 796f54d4ddbf update Octave Project Developers copyright for the new year John W. Eaton <jwe@octave.org> parents: 30379 diff changeset	3 ## Copyright (C) 2000-2022 The Octave Project Developers
27918 b442ec6dda5c use centralized file for copyright info for individual contributors John W. Eaton <jwe@octave.org> parents: 26376 diff changeset	4 ##
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	5 ## See the file COPYRIGHT.md in the top-level directory of this
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	6 ## distribution or <https://octave.org/copyright/>.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	7 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	8 ## This file is part of Octave.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	9 ##
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	10 ## 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	11 ## 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	12 ## 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	13 ## (at your option) any later version.
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 ## 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	16 ## WITHOUT ANY WARRANTY; without even the implied warranty of
22755 3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	17 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	18 ## GNU General Public License for more details.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	19 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	20 ## 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	21 ## 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	22 ## <https://www.gnu.org/licenses/>.
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	23 ##
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	24 ########################################################################
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	25
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	26 ## -- texinfo --
20852 516bb87ea72e 2015 Code Sprint: remove class of function from docstring for all m-files. Rik <rik@octave.org> parents: 20486 diff changeset	27 ## @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	28 ## @deftypefnx {} {[@var{pf}, @var{n}] =} factor (@var{q})
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	29 ## Return the prime factorization of @var{q}.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	30 ##
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	31 ## 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	32 ## 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	33 ## 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	34 ##
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	35 ## 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	36 ## their multiplicities. That is,
f7f97d7e9294 doc: Wrap m-file docstrings to 79 characters + newline (80 total). Rik <rik@octave.org> parents: 20852 diff changeset	37 ## @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	38 ##
31405 cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	39 ## Implementation Note: If the input @var{q} is @code{single} or @code{double},
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	40 ## then it must not exceed the corresponding @code{flintmax}. For larger
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	41 ## inputs, cast them to @code{uint64} if they're less than 2^64:
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	42 ##
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	43 ## @example
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	44 ## @group
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	45 ## factor (uint64 (18446744073709011493))
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	46 ## @result{} 571111 761213 42431951
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	47 ## @end group
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	48 ## @end example
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	49 ##
31406 658cce403bc7 doc: Capitalize Symbolic in factor.m. Arun Giridhar <arungiridhar@gmail.com> parents: 31405 diff changeset	50 ## For even larger inputs, use @code{sym} if you have the Symbolic package
31405 cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	51 ## installed and loaded:
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	52 ##
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	53 ## @example
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	54 ## @group
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	55 ## factor (sym ('9444733049654361449941'))
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	56 ## @result{} (sym)
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	57 ## 1 1
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	58 ## 1099511627689 ⋅8589934669
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	59 ## @end group
cd33d20283f4 doc: Add text to factor.m about how to factorize input > flintmax. Arun Giridhar <arungiridhar@gmail.com> parents: 31402 diff changeset	60 ## @end example
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	61 ## @seealso{gcd, lcm, isprime, primes}
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	62 ## @end deftypefn
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	63
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	64 function [pf, n] = factor (q)
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	65
28891 de5f2f9a64ff maint: Use same coding style when checking for a minimum of 1 input. Rik <rik@octave.org> parents: 27978 diff changeset	66 if (nargin < 1)
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	67 print_usage ();
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	68 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	69
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	70 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	71 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	72 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	73
30330 01de0045b2e3 maint: Shorten some long lines to <= 80 characters (bug #57599) Rik <rik@octave.org> parents: 30261 diff changeset	74 ## Special case if q is prime, because isprime() is now much faster than
01de0045b2e3 maint: Shorten some long lines to <= 80 characters (bug #57599) Rik <rik@octave.org> parents: 30261 diff changeset	75 ## factor(). This also absorbs the case of q < 4, where there are no primes
01de0045b2e3 maint: Shorten some long lines to <= 80 characters (bug #57599) Rik <rik@octave.org> parents: 30261 diff changeset	76 ## less than sqrt(q).
30261 a49c635b179d isprime.m: Speed up for large integers using Miller-Rabin test (bug #61312). Arun Giridhar <arungiridhar@gmail.com> parents: 30228 diff changeset	77 if (q < 4 \|\| isprime (q))
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	78 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	79 n = 1;
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	80 return;
11587 c792872f8942 all script files: untabify and strip trailing whitespace John W. Eaton <jwe@octave.org> parents: 11523 diff changeset	81 endif
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	82
30261 a49c635b179d isprime.m: Speed up for large integers using Miller-Rabin test (bug #61312). Arun Giridhar <arungiridhar@gmail.com> parents: 30228 diff changeset	83 ## If we are here, then q is composite.
a49c635b179d isprime.m: Speed up for large integers using Miller-Rabin test (bug #61312). Arun Giridhar <arungiridhar@gmail.com> parents: 30228 diff changeset	84
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	85 cls = class (q); # store class
ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	86 if (isfloat (q) && q > flintmax (q))
29984 c633d34960b4 factor.m: Fix typo in error() message. Rik <rik@octave.org> parents: 29983 diff changeset	87 error ("factor: Q too large to factor (> flintmax)");
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	88 endif
ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	89
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	90 ## The overall flow is this:
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	91 ## 1. Divide by small primes smaller than q^0.2, if any.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	92 ## 2. Use Pollard Rho to reduce the value below 1e10 if possible.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	93 ## 3. Divide by primes smaller than sqrt (q), if any.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	94 ## 4. At all stages, stop if the remaining value is prime.
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	95
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	96 ## First divide by primes (q ^ 0.2).
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	97 ## For q < 1e10, we can hard-code the primes.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	98 if (q < 1e10)
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	99 smallprimes = feval (cls, ...
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	100 [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]);
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	101 else
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	102 smallprimes = primes (feval (cls, q ^ 0.2));
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	103 endif
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	104
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	105 ## pf is the list of prime factors returned with type of input class.
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	106 pf = feval (cls, []);
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	107 [pf, q] = reducefactors (q, pf, smallprimes);
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	108
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	109 ## pf now contains all prime factors of q within smallprimes, including
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	110 ## repetitions, in ascending order.
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	111 ##
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	112 ## q itself has been divided by those prime factors to become smaller,
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	113 ## unless q was prime to begin with.
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	114
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	115 sortflag = false;
31107 bbb59cc6698c factor.m: Performance tweak to avoid division in certain cases Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	116 if (isprime (q))
bbb59cc6698c factor.m: Performance tweak to avoid division in certain cases Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	117 pf(end+1) = q;
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	118 elseif (q > 1)
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	119 ## Use Pollard Rho technique to pull factors one at a time.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	120 while (q > 1e10 && ! isprime (q))
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	121 pr = feval (cls, __pollardrho__ (q)); # pr is a factor of q.
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	122
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	123 ## There is a small chance (13 in 1e5) that pr is not actually prime.
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	124 ## To guard against that, factorize pr, which will force smaller factors
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	125 ## to be found. The use of isprime above guards against infinite
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	126 ## recursion.
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	127 if (! isprime (pr))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	128 pr = factor (pr);
31548 c8ad083a5802 maint: Clean up m-files before Octave 8.1 release. Rik <rik@octave.org> parents: 31406 diff changeset	129 endif
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	130
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	131 [pf, q] = reducefactors (q, pf, pr);
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	132 ## q is now divided by all occurrences of factor(s) pr.
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	133 sortflag = true;
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	134 endwhile
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	135
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	136 if (isprime (q))
31107 bbb59cc6698c factor.m: Performance tweak to avoid division in certain cases Arun Giridhar <arungiridhar@gmail.com> parents: 30564 diff changeset	137 pf(end+1) = q;
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	138 elseif (q > 1)
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	139 ## If we are here, then q is composite but less than 1e10,
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	140 ## and that is fast enough to test by division.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	141 largeprimes = primes (feval (cls, sqrt (q)));
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	142 [pf, q] = reducefactors (q, pf, largeprimes);
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	143
31395 068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	144 ## If q is still not 1, then it must be a prime of power 1.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	145 if (q > 1)
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	146 pf(end+1) = q;
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	147 endif
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	148 endif
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	149 endif
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	150
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	151 ## The Pollard Rho technique can give factors in arbitrary order,
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	152 ## so we need to sort pf if that was used.
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	153 if (sortflag)
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	154 pf = sort (pf);
068342cc93b8 factor.m: Speed up for large inputs. Arun Giridhar <arungiridhar@gmail.com> parents: 31107 diff changeset	155 endif
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	156
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	157 ## Determine multiplicity.
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	158 if (nargout > 1)
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	159 idx = find ([0, pf] != [pf, 0]);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	160 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	161 n = diff (idx);
5827 1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	162 endif
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	163
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	164 endfunction
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe] jwe parents: diff changeset	165
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	166 function [pf, q] = reducefactors (qin, pfin, divisors)
30379 363fb10055df maint: Style check m-files ahead of 7.1 release. Rik <rik@octave.org> parents: 30330 diff changeset	167
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	168 pf = pfin;
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	169 q = qin;
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	170 divisors = divisors (mod (q, divisors) == 0);
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	171
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	172 for pp = divisors # for each factor in turn
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	173 ## Keep extracting all occurrences of that factor before going to larger
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	174 ## factors.
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	175 while (mod (q, pp) == 0)
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	176 pf(end+1) = pp;
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	177 q /= pp;
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	178 endwhile
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	179 endfor
30379 363fb10055df maint: Style check m-files ahead of 7.1 release. Rik <rik@octave.org> parents: 30330 diff changeset	180
30228 39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	181 endfunction
39a4ab124fd0 factor.m: significant speedup for large input quantities (> 1e14) (bug #61129). Arun Giridhar <arungiridhar@gmail.com> parents: 29984 diff changeset	182
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	183
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	184 ## Test special case input
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	185 %!assert (factor (1), 1)
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	186 %!assert (factor (2), 2)
ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	187 %!assert (factor (3), 3)
ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	188
11469 c776f063fefe Overhaul m-script files to use common variable name between code and documentation. Rik <octave@nomad.inbox5.com> parents: 10476 diff changeset	189 %!test
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	190 %! for i = 2:20
19097 e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	191 %! pf = factor (i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	192 %! assert (prod (pf), i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	193 %! assert (all (isprime (pf)));
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	194 %! [pf, n] = factor (i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	195 %! assert (prod (pf.^n), i);
e7bffcea619f factor.m: Overhaul function. Rik <rik@octave.org> parents: 17744 diff changeset	196 %! 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	197 %! 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	198
31402 0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	199 ## Make sure that all factors returned are indeed prime, even when
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	200 ## __pollardrho__ returns a composite factor.
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	201 %!assert (all (isprime (factor (uint64 (18446744073707633197)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	202 %!assert (all (isprime (factor (uint64 (18446744073707551733)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	203 %!assert (all (isprime (factor (uint64 (18446744073709427857)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	204 %!assert (all (isprime (factor (uint64 (18446744073709396891)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	205 %!assert (all (isprime (factor (uint64 (18446744073708666563)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	206 %!assert (all (isprime (factor (uint64 (18446744073708532009)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	207 %!assert (all (isprime (factor (uint64 (18446744073708054211)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	208 %!assert (all (isprime (factor (uint64 (18446744073707834741)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	209 %!assert (all (isprime (factor (uint64 (18446744073707298053)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	210 %!assert (all (isprime (factor (uint64 (18446744073709407383)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	211 %!assert (all (isprime (factor (uint64 (18446744073708730121)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	212 %!assert (all (isprime (factor (uint64 (18446744073708104447)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	213 %!assert (all (isprime (factor (uint64 (18446744073709011493)))))
0783418ac443 factor.m: Guard against non-prime factors returned from C++. Arun Giridhar <arungiridhar@gmail.com> parents: 31395 diff changeset	214
25270 617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	215 %!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	216 %!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	217 %!test
617fe022e965 factor.m: Return output factors of same class as input for Matlab compatibility. Rik <rik@octave.org> parents: 25269 diff changeset	218 %! [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	219 %! 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	220 %! 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	221
19833 9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions. Rik <rik@octave.org> parents: 19697 diff changeset	222 ## Test input validation
28896 90fea9cc9caa test: Add expected error message <Invalid call> to BIST tests for nargin. Rik <rik@octave.org> parents: 28891 diff changeset	223 %!error <Invalid call> factor ()
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	224 %!error <Q must be a real non-negative integer> 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	225 %!error <Q must be a real non-negative integer> factor (6i)
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	226 %!error <Q must be a real non-negative integer> factor (-20)
25269 cac96fd5310d factor.m: Emit an error if input is negative (bug #53425). Dildar Sk <dildarsk101010@gmail.com> parents: 25054 diff changeset	227 %!error <Q must be a real non-negative integer> factor (1.5)
29983 ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	228 %!error <Q too large to factor> factor (flintmax ("single") + 2)
ecbcc4647dbe factor.m: Overhaul function to support inputs > flintmax. Rik <rik@octave.org> parents: 29359 diff changeset	229 %!error <Q too large to factor> factor (flintmax ("double") + 2)

Mercurial > octave

annotate scripts/specfun/factor.m @ 31548:c8ad083a5802 stable