chebyshev polynomial in nemo

gistfile1.jl

function chebyshev_t_pair{S <: Ring}(n::Int, x::S)
   if n == 0
      return one(S), x
   elseif n == 1
      return x, one(S)
   elseif n < 0
      a, b = chebyshev_t_pair(1-n, x)
      return b, a
   elseif iseven(n)
      a, b = chebyshev_t_pair(n>>1, x)
      return 2*(a*a) - 1, 2*(a*b) - x
   else
      a, b = chebyshev_t_pair((n>>1)+1, x)
      return 2*(a*b) - x, 2*(b*b) - 1
   end
end

function chebyshev_t{S <: Ring}(n::Int, x::S)
   if n == 0
      return one(S)
   elseif n == 1
      return x
   elseif n < 0
      return chebyshev_t(-n, x)
   elseif iseven(n)
      a = chebyshev_t(n>>1, x)
      return 2*(a*a) - 1
   else
      a, b = chebyshev_t_pair((n>>1)+1, x)
      return 2*(a*b) - x
   end
end