Calculating and Optimizing M(n) Algorithms

David Purdum Butler University
Faculty Sponsor(s): Jonathan Webster Butler University
We present a new algorithm to compute M(n), the function that counts the number of distinct integers in the n x n multiplication table. Our new algorithm runs faster than a straightforward algorithm by using less memory, prime sieve segmentation, parallelization, and clever optimizations. Specifically, the straightforward algorithm is O(n^2) in both time and space complexity. Our algorithm runs in o(n^2 ln n) in time and O(n) in space. The algorithm has been developed in C++ and has gone through many optimizations to reduce runtime. We will discuss these optimizations of the C++ implementation.
Mathematics & Computer Science
Oral Presentation

When & Where

11:00 AM
Jordan Hall 238