Cet algorithme ([30], [39]) est une extension de l'algorithme précédent, à mémoire limiée. Concrètement, on se donne un entier , de l'ordre de , et on ne stocke que les dernières paires calculées. La mise à jour des matrices se fait alors de la manière suivante :