Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Karatsuba multiplication with temporary space of size ≤ n

Abstract : We describe in this short note how it is possible to perform a Karatsuba multiplication of two polynomials of degree n − 1 using a buffer holding at most n − 1 coefficients if n is even, and n coefficients if n is odd. This method is valid for any n (in other words, when n ≥ 2). Similar results can be obtained for the Karatsuba squaring.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02396734
Contributor : Emmanuel Thomé <>
Submitted on : Friday, December 6, 2019 - 10:52:21 AM
Last modification on : Wednesday, October 14, 2020 - 3:54:02 PM
Long-term archiving on: : Saturday, March 7, 2020 - 2:00:54 PM

File

kara.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02396734, version 1

Collections

Citation

Emmanuel Thomé. Karatsuba multiplication with temporary space of size ≤ n. 2002. ⟨hal-02396734⟩

Share

Metrics

Record views

79

Files downloads

90