A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two

	This Article
	Subscribers, please Login Purchase article: $19 PDF RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Serdar S. Erdem Articles by Çetin K. Koç

16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03)

Santiago de Compostela, Spain

June 15-June 18

ISBN: 0-7695-1894-X

	ASCII Text	x
	Serdar S. Erdem, Çetin K. Koç, "A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two," Computer Arithmetic, IEEE Symposium on, pp. 28, 16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03), 2003.

	BibTex	x
	@article{ 10.1109/ARITH.2003.1207657, author = {Serdar S. Erdem and Çetin K. Koç}, title = {A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two}, journal ={Computer Arithmetic, IEEE Symposium on}, volume = {0}, year = {2003}, issn = {1063-6889}, pages = {28}, doi = {http://doi.ieeecomputersociety.org/10.1109/ARITH.2003.1207657}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computer Arithmetic, IEEE Symposium on TI - A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two SN - 1063-6889 SP EP A1 - Serdar S. Erdem, A1 - Çetin K. Koç, PY - 2003 KW - null VL - 0 JA - Computer Arithmetic, IEEE Symposium on ER -

Serdar S. Erdem, Gebze Yüksek Teknoloji Enstitüsü

Çetin K. Koç, Oregon State University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2003.1207657

We propose a new algorithm for fast multiplication of large integers having a precision of 2k computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls.

Citation:

Serdar S. Erdem, Çetin K. Koç, "A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two," arith, pp.28, 16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.