PIMS-Shell Lunchbox Lecture
- Date: 09/25/2008
Dr. Vassil Dimitrov, Schulich School of Engineering, University of Calgary
Calgary Place Tower (Shell)
The multiplication of two integers is a fundamental computational problem, which, due to its obvious importance, has been a subject of a large amount of research concerning efficient impementations. The asymptotically fastest known algorithm is due to Schonhage and Strassen. While time forms a major part of the cost of computing, the resource of storage space should also be considered in an analysis of the computational complexity of a problem such as integer multiplication. Interestingly enough, there are many unknown things that have to be unveiled, despite the simplicity of this problem. For example, if one implements the multiplications as a succession of additions and binary shift operations, how many additions, on average, are required? What about the worst cases? If one can use not only additions, but additions and subtractions, would that make a considerable difference?Addressing all these issues is of obvious importance for people working in the area of signal and image processing, where designing special purpose hardware for computationally intensive problems requires extremely fast multipliers. Another possible application is in the field of compiler optimization. At the end of the talk some easy-to-pose but different-to-answer open problems will be considered.