Abstract In this paper we show how Schönhage’s strategy for computing continued fractions (Schönhage 1971) can be combined with the theory of sub-resultants (Habicht, 1948; Collins, 1967; Brown, 1971; Brown and Traub, 1971; Loos, 1982; Gonzalez et al., 1990, 1994; Ducos, 1996; Ho and Yap, 1996; Lazard, 1998; Quitté, 1998) in order to compute the Cauchy index of a rational function or the signature of a non-singular Hankel matrix in a fast and also storage efficient way. Over the integers our algorithms have bit complexity O ( M( d, σ) ·log( d)) with σ = O( dτ) where M( d, σ ) = O( dσ·log( dσ) ·loglog( dσ)) is Schönhage’s bound for multiplication of integer polynomials of degrees bounded by d and bit size bounded by σ in the multi-tape Turing machine model (Schönhage, 1982). Thus our bound is O( d 2 τ· log( dτ) · loglog( dτ) · log( d)).As a byproduct of the necessary analysis we obtain a refinement of the Sub-resultant Theorem. We present a new exact divisibility for sub-resultants in the defective case which extends the formulæ for the non-defective situation in a natural way. We also prove that the size of coefficients in the ordinary remainder sequence is quadratic in d.