Research Article
Algorithm to Compute Cubes of 1st “N” Natural Numbers using Single Multiplication per Iteration
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 101 - Issue 15 |
| Published: September 2014 |
| Authors: Rajat Tandon, Rajika Tandon |
10.5120/17761-8872
|
Rajat Tandon, Rajika Tandon . Algorithm to Compute Cubes of 1st “N” Natural Numbers using Single Multiplication per Iteration. International Journal of Computer Applications. 101, 15 (September 2014), 6-9. DOI=10.5120/17761-8872
@article{ 10.5120/17761-8872,
author = { Rajat Tandon,Rajika Tandon },
title = { Algorithm to Compute Cubes of 1st “N” Natural Numbers using Single Multiplication per Iteration },
journal = { International Journal of Computer Applications },
year = { 2014 },
volume = { 101 },
number = { 15 },
pages = { 6-9 },
doi = { 10.5120/17761-8872 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Rajat Tandon
%A Rajika Tandon
%T Algorithm to Compute Cubes of 1st “N” Natural Numbers using Single Multiplication per Iteration%T
%J International Journal of Computer Applications
%V 101
%N 15
%P 6-9
%R 10.5120/17761-8872
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Different processors work with disparate speeds. For any given processor, elementary operations differ in terms of their speeds and computational complexities. The paper presents an algorithm to compute cubes of 1st "N" Natural Numbers using one multiplication by constant, two additions on variables and one addition by constant, per iteration. Theoretically, computational complexity of multiplication is O(n2) while that of addition is ?(n), where n is the number of bits used to represent that number. So, keeping the number of iterations same in both, in the traditional approach, the overall computational complexity per iteration is expressed in the order of O(n2) while in the current approach the overall computational complexity per iteration is of the order of O(n). For small values of "N", the difference in complexities may not be huge. But, given any large value of "N", difference will be noticeable.
References
- Levitin, A. 2002. Introduction to the Design and Analysis of Algorithms, 2nd ed. , Addison Wesley.
- Harel, D. and Feldman Y. 2004. Algorithmics: The Spirit of Computing, 3rd ed. , Addison-Wesley Publishers Limited.
- Tandon, R. 2012. "Algorithm to Compute Squares of 1st "N" Natural Numbers Without Using Multiplication", arXiv:1212. 5645v1 [cs. DS].
- Knuth, D. E. 1997. The Art of Computer Programming, vol. 1, 3rd ed. , Addison-Wesley.
- Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , and Stein, C. 2009. Introduction to Algorithms, 3rd ed. , The MIT Press and McGraw-Hill.
- Malhotra, O. P. , Gupta S. K. , and Gangal A. , 2007. I. S. C. Mathematics Book I for Class XI (page 6-39), S. Chand & Company Ltd.
Index Terms
Keywords