Anàlisi d'un algorisme de multiplicació d'enters

Abstract

We present a fast algorithms for integer product, based on the

Es proposa un algorisme de multiplicació d'enters basat en l'esquema "divideix i venç", però diferent del de Karatsuba i Ofman. Es fa l'anàlisi de la seva complexitat. Es troba que, encara que sembli millor que els ja coneguts si el cost de la suma es considera constant, fent la hipótesi, més realista, que la suma requereix temps lineal, el cost total puja fins a quadràtic.

Preprint