无忧视频

CS Professor鈥檚 Work Anything But Predictable

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 无忧视频 Professor of Computer Science Melissa O鈥橬eill.

鈥淢ost people are surprised to learn that the RNGs in languages like Python, Java and C++ are both easily predicted and have serious statistical flaws,鈥� says O鈥橬eill. 鈥淚t鈥檚 surprising because RNGs have been around for about 50 years, so you might think that the problem would have been well solved already.鈥� But there was no good all-round solution, until now.

O鈥橬eill has developed a family of RNGs, under the acronym , that set a new performance standard. 鈥淧rior to the PCG family, there was always a trade-off,鈥� she says. 鈥淵ou could pick a fast RNG, or a hard-to-predict one, or one with good statistical performance, but you couldn鈥檛 find one that would give you all the desirable features together.鈥� O鈥橬eill鈥檚 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.

O鈥橬eill became interested in random number generation last year by chance. 鈥淚 saw a talk where the speaker was critical of a particular kind of low-quality RNG and said it should never be used,鈥� she says. 鈥淚 always encourage students to think critically about the things they鈥檙e told, and in this case I applied that same skepticism. Should it really never be used?鈥�

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 鈥渁 new randomized algorithm for randomness,鈥� allowing an RNG to apply its own randomness to itself.

O鈥橬eill 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. 鈥淎s they embarked on their own projects, I wanted them to understand how valuable curiosity and play are,鈥� says O鈥橬eill. Colleagues who saw her presentation encouraged her to publish it. As a result, she formalized and generalized her work, culminating in a (currently under review). Analysis indicates that the performance of the PCG family in statistical tests isn鈥檛 merely good, but optimal.

PCG family versus other RNGs

O鈥橬eill notes that the success of an RNG doesn鈥檛 just depend on its technical qualities; the truly successful ones are those that everyone uses. To that end, she has built 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鈥橬eill was contacted by Mudd alumnus Zvi Effron 鈥�10, who informed her that leading game industry graphics programmers were raving about the paper on Twitter. 鈥淚t鈥檚 a new world,鈥� says O鈥橬eill, 鈥渨here part of being successful isn鈥檛 just how well the work does in academic peer review, but also how much traction it gets on social media!鈥�

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 鈥�.鈥� It includes an RNG that will produce 3,000 billion billion completely random numbers, then output Hamlet, and then return to completely random numbers again.

O’Neill’s research on random number generation isn鈥檛 the first case of her work being popular with bloggers as well as academics. Her 2009 paper, was also immensely popular online.

O鈥橬eill sees her research as imbued with the spirit of Harvey Mudd鈥攍earning for learning鈥檚 sake, healthy skepticism and, most importantly, play.聽 She hopes it will be an empowering example to encourage her students to think outside the box and consider novel approaches to problem solving. 鈥淪ome people think that undergraduates should aim low in research because of their relative lack of experience,鈥� she says. 鈥淏ut I encourage them to aim high, because sometimes a fresh perspective is a wonderful thing.鈥�

Hired by the college in 2001, O鈥橬eill 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.

O’Neill at the Stanford computer science colloquium. The PCG website is .