% function [degrees,lambda,stats]=CompLeftPoly(R,n);
%
% Computes degree distributions from the right-regular
% family
%
%  f(x;n) = rho(x;n) = x^n.
%
% Uses explicit formulas for the Taylor
% coefficients of g(x)=1-(1-x)^{1/n}
% Average and maximal right degrees coincide: a_r=n+1=N
%
% Input: Rate 0<R<1 and parameter n>0
% 
% Output:
%  degrees=[a_r a_l N M] average and maximal degrees 
%          of right and left degree distributions
%  lambda  1xM array of left degrees
%  stats   [delta,epsilon,mu,Delta,Lambda2]  
%          distances to capacity 1-R, comparison to
%          lower bounds, and fraction of degree 2 variable
%          nodes  Lambda2=lambda2*a_l/2
%
% Author: P. Oswald
% Last changed: 10/4/2002

function [degrees,lambda,stats]=CompLeftPoly(R,n);
%
% Setting a maximum for anticipated M (to avoid serious
% rounding problems and endless computation)
Mmax=20000;
%
% Computation of a_r, N
N=n+1;ar=N;
%
% Computation of a_l, M, lambda, and delta 
% by implementing Step (2) and (3) of Algorithm 1.
% This is based on hand-derived recursions for the Taylor coefficients
% g_k of g, which lead to recursions for s_k and sigma_k and finally
% to finding t such that hat(I)(t)=1/a_l where a_l=a_r*(1-R)
% is the average degree of the left (variable) nodes.
al=ar*(1-R);a=1/n;
c=a;sk=c;c1=c/2;sigmak=c1;lambda=[];
if al<2
  disp('Average degree of left nodes too small (decrease R or increase a)');
  M=0;lambda=[];stats=[];
 else
  if al==2
    lambda=1;M=2;delta=c;
   else
    m=2;q=sigmak/sk;
    while q*al>1&m<Mmax
      lambda=[lambda c];c=c1*(m-1-a);sk=sk+c;
      m=m+1;c1=c/m;sigmak=sigmak+c1;q0=q;q=sigmak/sk;
     end
    if m==Mmax&q*al>1
      disp('M larger than allowed (reduce n or increase Mmax)');
      M=m;lambda=[];stats=[];
     else
      M=m;t1=(al*sigmak-sk)/(al*c1-c);
      delta=(sk-t1*c);lambda=[lambda (1-t1)*c]/delta;
     end
   end
  %
  % Computation of output
  epsilon=1-delta/(1-R);
  b=ar*log(R);mu=b/log(epsilon);Delta=epsilon/exp(b);
  Lambda2=lambda(1)*al/2;stats=[delta epsilon mu Delta Lambda2];
 end
degrees=[ar al N M];
% End CompLeftPoly.m