fib(n)={
  if(n<=0,
    if(n,(-1)^(n+1)*fib(n),0)
  ,
    my(v=lucas(n-1));
    (2*v[1]+v[2])/5
  )
};
lucas(n)={
  if (!n, return([2,1]));
  my(v=lucas(n >> 1), z=v[1], t=v[2], pr=v[1]*v[2]);
  n=n%4;
  if(n%2,
    if(n==3,[v[1]*v[2]+1,v[2]^2-2],[v[1]*v[2]-1,v[2]^2+2])
  ,
    if(n,[v[1]^2+2,v[1]*v[2]+1],[v[1]^2-2,v[1]*v[2]-1])
  )
};