{"id":3503,"date":"2014-12-12T08:40:06","date_gmt":"2014-12-12T16:40:06","guid":{"rendered":"https:\/\/www.hmc.edu\/about-hmc\/?p=3503"},"modified":"2015-03-18T09:30:19","modified_gmt":"2015-03-18T16:30:19","slug":"cs-professors-work-anything-predictable","status":"publish","type":"post","link":"https:\/\/www.hmc.edu\/about\/2014\/12\/12\/cs-professors-work-anything-predictable\/","title":{"rendered":"CS Professor\u2019s Work Anything But Predictable"},"content":{"rendered":"

Algorithmic random number generators (RNGs) lie at the heart of many important algorithms in computer science. They are hard at work assisting in a variety of tasks, including computer simulation, computational creativity, global optimization, robotics, games and more. Yet despite our widespread reliability on them, many of the most widely used RNGs are actually flawed, says Harvey Mudd College Professor of Computer Science Melissa O\u2019Neill.<\/p>\n

\u201cMost people are surprised to learn that the RNGs in languages like Python, Java and C++ are both easily predicted and have serious statistical flaws,\u201d says O\u2019Neill. \u201cIt\u2019s surprising because RNGs have been around for about 50 years, so you might think that the problem would have been well solved already.\u201d But there was no good all-round solution, until now.<\/p>\n

O\u2019Neill has developed a family of RNGs, under the acronym \u201cPCG\u201d (permuted congruential generator)<\/a>, that set a new performance standard. \u201cPrior to the PCG family, there was always a trade-off,\u201d she says. \u201cYou could pick a fast RNG, or a hard-to-predict one, or one with good statistical performance, but you couldn\u2019t find one that would give you all the desirable features together.\u201d O\u2019Neill\u2019s PCG scheme changes that, providing a broader array of features than found on any prior RNG, combining speed, ease of use and low predictability, all contained within a small amount of code and minimal memory usage.<\/p>\n

O\u2019Neill became interested in random number generation last year by chance. \u201cI saw a talk where the speaker was critical of a particular kind of low-quality RNG and said it should never be used,\u201d she says. \u201cI always encourage students to think critically about the things they\u2019re told, and in this case I applied that same skepticism. Should it really never be used?\u201d<\/p>\n

She became curious about whether she could turn a very low-quality RNG into a very good one. With the development of PCG, she succeeded. The end result was what she calls \u201ca new randomized algorithm for randomness,\u201d allowing an RNG to apply its own randomness to itself.<\/p>\n

O\u2019Neill first presented the work to Harvey Mudd summer research students, in part to show them how a fresh perspective on an old problem can yield new results. \u201cAs they embarked on their own projects, I wanted them to understand how valuable curiosity and play are,\u201d says O\u2019Neill. Colleagues who saw her presentation encouraged her to publish it. As a result, she formalized and generalized her work, culminating in a detailed academic paper<\/a> (currently under review). Analysis indicates that the performance of the PCG family in statistical tests isn\u2019t merely good, but optimal.<\/p>\n

\"RNG<\/a>

PCG family versus other RNGs<\/p><\/div>\n

O\u2019Neill notes that the success of an RNG doesn\u2019t just depend on its technical qualities; the truly successful ones are those that everyone uses. To that end, she has built a website<\/a> that provides an accessible description of the advantages of the PCG scheme and offers downloadable code. Not long after the website went live, O\u2019Neill was contacted by Mudd alumnus Zvi Effron \u201910, who informed her that leading game industry graphics programmers were raving about the paper on Twitter. \u201cIt\u2019s a new world,\u201d says O\u2019Neill, \u201cwhere part of being successful isn\u2019t just how well the work does in academic peer review, but also how much traction it gets on social media!\u201d<\/p>\n

One of the most popular aspects of her work is a more whimsical part of the PCG website that shows how PCG-based RNGs can perform \u201cparty tricks<\/a>.\u201d It includes an RNG that will produce 3,000 billion billion completely random numbers, then output Hamlet<\/em>, and then return to completely random numbers again.<\/p>\n

O’Neill’s research on random number generation isn\u2019t the first case of her work being popular with bloggers as well as academics. Her 2009 paper, \u201cThe Genuine Sieve of Eratosthenes,\u201d<\/a> was also immensely popular online.<\/p>\n

O\u2019Neill sees her research as imbued with the spirit of Harvey Mudd\u2014learning for learning\u2019s sake, healthy skepticism and, most importantly, play.\u00a0 She hopes it will be an empowering example to encourage her students to think outside the box and consider novel approaches to problem solving. \u201cSome people think that undergraduates should aim low in research because of their relative lack of experience,\u201d she says. \u201cBut I encourage them to aim high, because sometimes a fresh perspective is a wonderful thing.\u201d<\/p>\n

Hired by the college in 2001, O\u2019Neill has taught Data Structures and Program Development, Programming Languages, and Operating Systems. Her other areas of active research include memory management and making parallel and concurrent programming easier.<\/p>\n

O’Neill recently spoke about the PCG family<\/a> at the Stanford computer science colloquium. The PCG website is www.pcg-random.org<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Algorithmic random number generators (RNGs) lie at the heart of many important algorithms in computer science. They are hard at […]<\/p>\n","protected":false},"author":1,"featured_media":3504,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[11,14,26],"class_list":["post-3503","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science","category-faculty","category-research"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts\/3503","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/comments?post=3503"}],"version-history":[{"count":0,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts\/3503\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/media\/3504"}],"wp:attachment":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/media?parent=3503"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/categories?post=3503"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}