Mercurial > hg > octave-lyh
diff scripts/general/rat.m @ 6788:c81a0f3f5a82
[project @ 2007-07-23 22:05:29 by dbateman]
author | dbateman |
---|---|
date | Mon, 23 Jul 2007 22:05:30 +0000 |
parents | |
children | 65a28e9de0a5 |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/scripts/general/rat.m @@ -0,0 +1,135 @@ +## Copyright (C) 2001 Paul Kienzle +## +## 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 2, 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, write to the Free +## Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +## 02110-1301, USA. + +## -*- texinfo -*- +## @deftypefn {Function File} {@var{s} =} rat (@var{x}, @var{tol}) +## @deftypefnx {Function File} {[@var{n}, @var{d}] =} rat (@var{x}, @var{tol}) +## +## Find a rational approximation to @var{x} within tolerance defined +## by @var{tol} using a continued fraction expansion. E.g, +## +## @example +## rat(pi) = 3 + 1/(7 + 1/16) = 355/113 +## rat(e) = 3 + 1/(-4 + 1/(2 + 1/(5 + 1/(-2 + 1/(-7))))) = 1457/536 +## @end example +## +## Called with two arguments returns the numerator and deniminator seperately +## as two matrices. +## @end deftypefn +## @seealso{rats} + +function [n,d] = rat(x,tol) + + if (nargin != [1,2] || nargout > 2) + print_usage (); + endif + + y = x(:); + + ## replace inf with 0 while calculating ratios + y(isinf(y)) = 0; + + ## default norm + if (nargin < 2) + tol = 1e-6 * norm(y,1); + endif + + ## First step in the approximation is the integer portion + n = round(y); # first element in the continued fraction + d = ones(size(y)); + frac = y-n; + lastn = ones(size(y)); + lastd = zeros(size(y)); + + nd = ndims(y); + nsz = prod (size (y)); + steps = zeros([nsz, 0]); + + ## grab new factors until all continued fractions converge + while (1) + ## determine which fractions have not yet converged + idx = find (abs(y-n./d) >= tol); + if (isempty(idx)) break; endif + + ## grab the next step in the continued fraction + flip = 1./frac(idx); + step = round(flip); # next element in the continued fraction + + if (nargout < 2) + tsteps = NaN .* ones (nsz, 1); + tsteps (idx) = step; + steps = [steps, tsteps]; + endif + + frac(idx) = flip-step; + + ## update the numerator/denominator + nextn = n; + nextd = d; + n(idx) = n(idx).*step + lastn(idx); + d(idx) = d(idx).*step + lastd(idx); + lastn = nextn; + lastd = nextd; + endwhile + + if (nargout == 2) + ## move the minus sign to the top + n = n.*sign(d); + d = abs(d); + + ## return the same shape as you receive + n = reshape(n, size(x)); + d = reshape(d, size(x)); + + ## use 1/0 for Inf + n(isinf(x)) = sign(x(isinf(x))); + d(isinf(x)) = 0; + + ## reshape the output + n = reshape (n, size (x)); + d = reshape (d, size (x)); + else + n = ""; + nsteps = size(steps, 2); + for i = 1: nsz + s = [int2str(y(i))," "]; + j = 1; + + while (true) + step = steps(i, j++); + if (isnan (step)) + break; + endif + if (j > nsteps || isnan (steps(i, j))) + if (step < 0) + s = [s(1:end-1), " + 1/(", int2str(step), ")"]; + else + s = [s(1:end-1), " + 1/", int2str(step)]; + endif + break; + else + s = [s(1:end-1), " + 1/(", int2str(step), ")"]; + endif + endwhile + s = [s, repmat(")", 1, j-2)]; + n = cat (1, n, s); + endfor + endif + +endfunction