function [t,i] = stepsize(x, dx)

% calling sequence: [t,i] = stepsize(x, dx)
% ratio test for LP
% given vectors x and dx, with x >= 0 (all components),
% compute max { t:  x - t dx >= 0}   (all components)
% here t is a real nonnegative scalar, possibly infinity,
% and i is returned as an index achieving the max
%  Written by M. Overton for class Feb 2, 1998.
%  Warning: may not be fully debugged.


% check x and dx have same length

n = length(x);
if n ~= length(dx),
   error('x and dx must have same length')
end

% check that x >= 0
if min(x) < 0,
   error('x has a negative component')
end


% if dx(i) <= 0 we don't care about it 
%   (because then (x - t dx)_i >= 0 for all t >=0)
% so consider only the dx(i) which are > 0

for i = 1:n,
   if dx(i) > 0,
      ratio(i) = x(i)/dx(i);
   else
      ratio(i) = inf;   % infinity
   end;
end;
[t,i] = min(ratio);     % t could be infinity, then LP is unbounded
