Show simple item record

dc.contributor.authorStaple, Douglas
dc.date.accessioned2015-08-19T12:43:20Z
dc.date.available2015-08-19T12:43:20Z
dc.identifier.urihttp://hdl.handle.net/10222/60524
dc.description.abstractThis thesis describes recent advances in the combinatorial method for computing pi(x), the number of primes less-than or equal-to x. In particular, the memory usage has been reduced by a factor of log x, and modifications for shared- and distributed-memory parallelism have been incorporated. The resulting method computes pi(x) with complexity O(x^(2/3) (log x)^(-2)) in time and O(x^(1/3) (log x)^2) in space. The algorithm has been implemented and used to compute pi(10^n) for 1 <= n <= 26 and pi(2^m) for 1 <= m <= 86. The mathematics presented here is consistent with and builds on that of previous authors.en_US
dc.language.isoenen_US
dc.subjectprime counting functionen_US
dc.subjectpi(x)en_US
dc.titleThe combinatorial algorithm for computing pi(x)en_US
dc.typeThesisen_US
dc.date.defence2015-08-17
dc.contributor.departmentDepartment of Mathematics & Statistics - Math Divisionen_US
dc.contributor.degreeMaster of Scienceen_US
dc.contributor.external-examinern/aen_US
dc.contributor.graduate-coordinatorDavid Ironen_US
dc.contributor.thesis-readerMeng Heen_US
dc.contributor.thesis-readerKeith Johnsonen_US
dc.contributor.thesis-supervisorKarl Dilcheren_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.copyright-releaseNot Applicableen_US
 Find Full text

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record