I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
Friend key: 28904932216450_59cd9d55374be03d8167d37c8ff4196b
This morning my wife (whom I love and adore) woke me up at 3:00 AM with an urgent question.
"Hey!" she said, shaking me awake.
"Is 19 prime?"
Like a fool, I answered her. "Yes. Yes it is." Off she went.
This is a true response, but not a correct response. I realized shortly afterwards that a correct response would look more like:
I'm glad you asked me that. dear. Eratosthenes, the Greek mathematician, discovered a very efficient way to list primes in about 200 BC that is still in use today. You start by writing out all the numbers from 1 to 19: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19. 1 is a very special number (it's the multiplicative identity, or what algebraists would call a unit) so we put a square around it. The first number we didn't consider was 2, so we circle it - that means it's prime - and then cross out every multiple of 2 after that. Going back, the first number we didn't consider was 3... and so on until we get 1 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19. A common optimization is to realize that after circling a prime p, the first number you cross out (that wasn't crossed out before) is always p2, which means that after circling a number you can immediately jump to its square, and also means you can stop crossing out altogether once you hit p2 > N...
This would allow her to fish rather than waking me up when she wanted a fish.
An even better response would have been:
It's funny you've asked me that. Number theorists and cryptanalysts have considered this question for thousands of years. Eratosthenes' method (see above) is a very simple way to find all the primes below a given number, but an efficient way to determine whether a given number is prime was found only very recently.
In practice, the test that is usually used is the randomized version of the Miller-Rabin test. Although this is nondeterministic, it is very fast indeed, and will tell you to a very high degree of certainty whether the given number is prime. This usually suffices.
There is a deterministic version of the Miller-Rabin test too, which is guaranteed to tell you with perfect certainty whether the given number is prime. But it only works if you believe in the generalized Riemann hypothesis. Most mathematicians nowadays believe the hypothesis, but no-one has (yet) been able to prove it.
Amazingly, in 2002 three mathematicians named Manindra Agrawal, Neeraj Kayal, and Nitin Saxena came up with a deterministic, proven, polynomial-time (specifically, polynomial in the number of digits in the input) method for telling whether a given number is prime. This is known as the AKS primality test. The most striking thing about this test is its simplicity - if something this straightforward can be found after thousands of years of looking, what else out there remains to be found?
Such a response would probably prevent her from waking me again for any mathematical problem at all. Boo-ya.
Here's Agrawal, Kayal, and Saxena's "PRIMES is in P" paper.
Here's Yves Gallot's C++ implementation of AKS.
My own Perl implementation follows:
Here's the output when I run it on 19:
And here's the output with a bigger input:
As a Windows tester, I install Windows on my own machines a lot (this is known internally as "selfhosting", or "dogfooding", or "ice cream-ing".)
One of my little idiosyncracies is I like to run as a non-administrative user. That is, I don't add my domain account to the local Administrators group.
Instead, I create a local "Admin" account with a known (to me) password; every time I need to elevate, I get a prompt that asks for credentials rather than just "Yes/No". To this prompt I pass the credentials of the local "Admin" account.
Although I usually install fresh builds regularly (on my multiple machines), sometimes one machine gets a little stale. In fact, it happened once that my local .\Admin account got so stale that I had to change the password! This was annoying enough that I devoted some energy into figuring out how to check the "Password never expires" box on the local account properties programmatically.
The result was the following script: call as cscript.exe never-expire-admin-password.wsf This version hardcodes the username "Admin"; a production version would probably allow passing a username in via the command line.
If the Admin password already has the box checked, this script does nothing.
' LDAP doesn't work for controlling local users' (unless you're a domain controller, of course)'' have to use WinNT provider instead
Const ADS_UF_DONT_EXPIRE_PASSWD = &H10000
' hardcoding "Admin" usernameDim admin: Set admin = GetObject("WinNT://localhost/Admin,user")
WScript.Echo "Admin's userFlags are 0x" & Hex(admin.userFlags)
If Not admin.userFlags And ADS_UF_DONT_EXPIRE_PASSWD Then WScript.Echo "Setting local admin account to never expire password" admin.userFlags = (admin.userFlags Or ADS_UF_DONT_EXPIRE_PASSWD)
' Save admin.SetInfoEnd If