The Mixed Binary Euclid Algorithm期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

The Mixed Binary Euclid Algorithm

Affiliation:	1. Faculty of Robot Science and Engineering, Northeastern University, 110004, Shenyang, Liaoning Province, China;2. School of Computing, Engineering and Intelligent Systems, Ulster University, Londonderry, BT48 7JL, Northern Ireland, United Kingdom;1. Department of ECE, Mar Ephraem College of Engineering and Technology, Elavuvilai, India;2. Department of EEE, Noorul Islam University, Thuckalay, India

Abstract:	We present a new GCD algorithm for two integers that combines both the Euclidean and the binary gcd approaches. We give its worst case time analysis and we prove that its bit-time complexity is still $O (n^{2})$ for two n-bit integers in the worst case. Our preliminar experiments show a potential speedup for small integers. A parallel version matches the best presently known time complexity, namely $O (n / \log n)$ time with $O (n^{1 + ϵ})$ processors, for any constant $ϵ > 0$ .

Keywords:
本文献已被 ScienceDirect 等数据库收录！