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