Algorithm to Compute Cubes of 1st "N" Natural Numbers using Single Multiplication per Iteration
|
10.5120/17761-8872 |
Rajat Tandon and Rajika Tandon. Article: Algorithm to Compute Cubes of 1st “N” Natural Numbers using Single Multiplication per Iteration. International Journal of Computer Applications 101(15):6-9, September 2014. Full text available. BibTeX
@article{key:article,
author = {Rajat Tandon and Rajika Tandon},
title = {Article: 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},
month = {September},
note = {Full text available}
}
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.