# Matthew van Eerde's web log

• #### Generating sample first names

I had a need to write a script that would give me a random first name.  I grabbed the top 200 first names for baby boys in the US from 2000-2009, and the same list for baby girls:

 Boys Girls Jacob Emily Michael Madison ... ...

My initial implementation just printed out the name, but I quickly realized I needed to print out the gender if I wanted to talk about what the (fictitious) person did.  So I updated it to print out the gender as well.

In the course of this I realized that some names appeared on both lists.  In particular they are:

• Alexis
• Angel
• Jordan
• Peyton
• Riley

The script is called like this:

>perl -w name.pl
Wesley (male)

And here's the source:

use strict;

# prints a randomly chosen name

print $words[ rand(@words) ]; sub read_words() { my @words = <DATA>; chomp @words; return @words; } __DATA__ Aaliyah (female) Aaron (male) Abby (female) Abigail (female) Abraham (male) Adam (male) Addison (female) Adrian (male) Adriana (female) Adrianna (female) Aidan (male) Aiden (male) Alan (male) Alana (female) Alejandro (male) Alex (male) Alexa (female) Alexander (male) Alexandra (female) Alexandria (female) Alexia (female) Alexis (female) Alexis (male) Alicia (female) Allison (female) Alondra (female) Alyssa (female) Amanda (female) Amber (female) Amelia (female) Amy (female) Ana (female) Andrea (female) Andres (male) Andrew (male) Angel (female) Angel (male) Angela (female) Angelica (female) Angelina (female) Anna (female) Anthony (male) Antonio (male) Ariana (female) Arianna (female) Ashley (female) Ashlyn (female) Ashton (male) Aubrey (female) Audrey (female) Austin (male) Autumn (female) Ava (female) Avery (female) Ayden (male) Bailey (female) Benjamin (male) Bianca (female) Blake (male) Braden (male) Bradley (male) Brady (male) Brandon (male) Brayden (male) Breanna (female) Brendan (male) Brian (male) Briana (female) Brianna (female) Brittany (female) Brody (male) Brooke (female) Brooklyn (female) Bryan (male) Bryce (male) Bryson (male) Caden (male) Caitlin (female) Caitlyn (female) Caleb (male) Cameron (male) Camila (female) Carlos (male) Caroline (female) Carson (male) Carter (male) Cassandra (female) Cassidy (female) Catherine (female) Cesar (male) Charles (male) Charlotte (female) Chase (male) Chelsea (female) Cheyenne (female) Chloe (female) Christian (male) Christina (female) Christopher (male) Claire (female) Cody (male) Colby (male) Cole (male) Colin (male) Collin (male) Colton (male) Conner (male) Connor (male) Cooper (male) Courtney (female) Cristian (male) Crystal (female) Daisy (female) Dakota (male) Dalton (male) Damian (male) Daniel (male) Daniela (female) Danielle (female) David (male) Delaney (female) Derek (male) Destiny (female) Devin (male) Devon (male) Diana (female) Diego (male) Dominic (male) Donovan (male) Dylan (male) Edgar (male) Eduardo (male) Edward (male) Edwin (male) Eli (male) Elias (male) Elijah (male) Elizabeth (female) Ella (female) Ellie (female) Emily (female) Emma (female) Emmanuel (male) Eric (male) Erica (female) Erick (male) Erik (male) Erin (female) Ethan (male) Eva (female) Evan (male) Evelyn (female) Faith (female) Fernando (male) Francisco (male) Gabriel (male) Gabriela (female) Gabriella (female) Gabrielle (female) Gage (male) Garrett (male) Gavin (male) Genesis (female) George (male) Gianna (female) Giovanni (male) Giselle (female) Grace (female) Gracie (female) Grant (male) Gregory (male) Hailey (female) Haley (female) Hannah (female) Hayden (male) Hector (male) Henry (male) Hope (female) Hunter (male) Ian (male) Isaac (male) Isabel (female) Isabella (female) Isabelle (female) Isaiah (male) Ivan (male) Jack (male) Jackson (male) Jacob (male) Jacqueline (female) Jada (female) Jade (female) Jaden (male) Jake (male) Jalen (male) James (male) Jared (male) Jasmin (female) Jasmine (female) Jason (male) Javier (male) Jayden (male) Jayla (female) Jazmin (female) Jeffrey (male) Jenna (female) Jennifer (female) Jeremiah (male) Jeremy (male) Jesse (male) Jessica (female) Jesus (male) Jillian (female) Jocelyn (female) Joel (male) John (male) Johnathan (male) Jonah (male) Jonathan (male) Jordan (female) Jordan (male) Jordyn (female) Jorge (male) Jose (male) Joseph (male) Joshua (male) Josiah (male) Juan (male) Julia (female) Julian (male) Juliana (female) Justin (male) Kaden (male) Kaitlyn (female) Kaleb (male) Karen (female) Karina (female) Kate (female) Katelyn (female) Katherine (female) Kathryn (female) Katie (female) Kayla (female) Kaylee (female) Kelly (female) Kelsey (female) Kendall (female) Kennedy (female) Kenneth (male) Kevin (male) Kiara (female) Kimberly (female) Kyle (male) Kylee (female) Kylie (female) Landon (male) Laura (female) Lauren (female) Layla (female) Leah (female) Leonardo (male) Leslie (female) Levi (male) Liam (male) Liliana (female) Lillian (female) Lilly (female) Lily (female) Lindsey (female) Logan (male) Lucas (male) Lucy (female) Luis (male) Luke (male) Lydia (female) Mackenzie (female) Madeline (female) Madelyn (female) Madison (female) Makayla (female) Makenzie (female) Malachi (male) Manuel (male) Marco (male) Marcus (male) Margaret (female) Maria (female) Mariah (female) Mario (male) Marissa (female) Mark (male) Martin (male) Mary (female) Mason (male) Matthew (male) Max (male) Maxwell (male) Maya (female) Mckenzie (female) Megan (female) Melanie (female) Melissa (female) Mia (female) Micah (male) Michael (male) Michelle (female) Miguel (male) Mikayla (female) Miranda (female) Molly (female) Morgan (female) Mya (female) Naomi (female) Natalia (female) Natalie (female) Nathan (male) Nathaniel (male) Nevaeh (female) Nicholas (male) Nicolas (male) Nicole (female) Noah (male) Nolan (male) Oliver (male) Olivia (female) Omar (male) Oscar (male) Owen (male) Paige (female) Parker (male) Patrick (male) Paul (male) Payton (female) Peter (male) Peyton (female) Peyton (male) Preston (male) Rachel (female) Raymond (male) Reagan (female) Rebecca (female) Ricardo (male) Richard (male) Riley (female) Riley (male) Robert (male) Ruby (female) Ryan (male) Rylee (female) Sabrina (female) Sadie (female) Samantha (female) Samuel (male) Sara (female) Sarah (female) Savannah (female) Sean (male) Sebastian (male) Serenity (female) Sergio (male) Seth (male) Shane (male) Shawn (male) Shelby (female) Sierra (female) Skylar (female) Sofia (female) Sophia (female) Sophie (female) Spencer (male) Stephanie (female) Stephen (male) Steven (male) Summer (female) Sydney (female) Tanner (male) Taylor (female) Thomas (male) Tiffany (female) Timothy (male) Travis (male) Trenton (male) Trevor (male) Trinity (female) Tristan (male) Tyler (male) Valeria (female) Valerie (female) Vanessa (female) Veronica (female) Victor (male) Victoria (female) Vincent (male) Wesley (male) William (male) Wyatt (male) Xavier (male) Zachary (male) Zoe (female) Zoey (female) • #### How to dump Speech API object properties • 0 Comments Stamatis Pap asked in a forum thread how to use a Speech API ISpVoice with a non-default audio deviceThis MSDN article shows how to use SpEnumTokens to list all the currently active audio outputs, but the number and order of audio outputs is subject to change as things come and go, or as the default audio device changes. I spent some time poking around the Speech API documentation and discovered that each audio output object has a DeviceId string value which is the WASAPI endpoint ID; this is the way to recognize a given audio output rather than relying on enumeration order. As part of figuring this out, as a side effect I created a command-line tool to dump all the speech objects and all of their properties. Source and binaries attached. Pseudocode: for each object category in (audio outputs; audio inputs; voices; recognizers; etc.) SpEnumTokens(category) ISpEnumTokens::GetCount(); for each token ISpEnumTokens::Next(1); SpGetDescription(ISpObjectToken); Log the description the ISpObjectToken is also an ISpDataKey the ISpDataKey may also contain subkeys log all subkeys and their values recursively using ISpDataKey::EnumKeys and ISpDataKey::OpenKey for each subkey including this one log all values in the ISpDataKey using ISpDataKey::EnumValues and ISpDataKey::GetStringValue Here's the output on my system. Note the audio output has a DeviceId string value which matches the WASAPI endpoint ID. >speech-attributes.exe -- SPCAT_AUDIOOUT -- #1: [[Speakers] ([High Definition Audio Device])] Attributes Vendor = Microsoft Technology = MMSys (default) = [[Speakers] ([High Definition Audio Device])] CLSID = {A8C680EB-3D32-11D2-9EE7-00C04F797396} DeviceName = [[Speakers] ([High Definition Audio Device])] DeviceId = {0.0.0.00000000}.{c2cbdacb-a70d-4629-8368-542a00f5a4b0} -- SPCAT_AUDIOIN -- -- SPCAT_VOICES -- #1: Microsoft Zira Desktop - English (United States) Attributes Version = 10.4 Language = 409 Gender = Female Age = Adult SharedPronunciation = Name = Microsoft Zira Desktop Vendor = Microsoft (default) = Microsoft Zira Desktop - English (United States) LangDataPath = C:\Windows\Speech\Engines\TTS\en-US\MSTTSLocEnUS.dat VoicePath = C:\Windows\Speech\Engines\TTS\en-US\M1033ZIR 409 = Microsoft Zira Desktop - English (United States) CLSID = {C64501F6-E6E6-451f-A150-25D0839BC510} -- SPCAT_RECOGNIZERS -- -- SPCAT_APPLEXICONS -- -- SPCAT_PHONECONVERTERS -- #1: Simplified Chinese Phone Converter Attributes Language = 804 (default) = Simplified Chinese Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #2: English Phone Converter Attributes Language = 409 (default) = English Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #3: French Phone Converter Attributes Language = 40C (default) = French Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #4: German Phone Converter Attributes Language = 407 (default) = German Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #5: Japanese Phone Converter Attributes Language = 411 NumericPhones = NoDelimiter = (default) = Japanese Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #6: Spanish Phone Converter Attributes Language = 40A;C0A (default) = Spanish Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #7: Traditional Chinese Phone Converter Attributes Language = 404 NumericPhones = NoDelimiter = (default) = Traditional Chinese Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} #8: Universal Phone Converter Attributes Language = (lengthy value redacted) (default) = Universal Phone Converter PhoneMap = (lengthy value redacted) CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8} -- SPCAT_RECOPROFILES -- None found. • #### Linearity of Windows volume APIs - render session and stream volumes • 0 Comments We have talked about some of the volume APIs Windows exposes. We have also talked about what it means for a volume control to be linear in magnitude, linear in power, or linear in dB. We have also talked about how to read IAudioMeterInformation and how the limiter can attenuate full-scale signals. The last post had a volume-linearity.exe which, when called with --signal, showed that IAudioMeterInformation is linear in amplitude. Today we'll look at the --stream, --channel, and --session arguments, which explore the linearity of IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume respectively. Each of these modes plays a half-scale square wave, then set the volume API to various levels, and reads the resulting IAudioMeterInformation. We use a half-scale square wave to avoid running afoul of the limiter; we expect a meter reading of 0.5 when the volume is set to 1. The graphs below have their meter readings doubled to account for the fact that we're using a half-scale square wave rather than a full-scale. Here's what we get for IAudioStreamVolume, graph-inated for your convenience: And IChannelAudioVolume: And ISimpleAudioVolume: We already know that IAudioMeterInformation is linear in amplitude. We now know that IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume have a linear effect (with slope 1 and intercept 0) on IAudioMeterInformation. We infer that IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume are linear in amplitude. • #### Nitpicking Sam Loyd - a wheel within a wheel • 0 Comments In August 1878 Sam Loyd published this mate in two and dedicated it to a friend of his named Wheeler: Mate in two; Black to move and mate in two; Selfmate in two; Black to move and selfmate in two While the mates appear to stand up, the problem position is not legal. White has three a-pawns; this implies at least three Black pieces were captured by a White pawn. But Black has fifteen pieces on the board; only one is missing! Looking at Black pawn captures - the b2-, c-, and d- pawns together account for three pawn captures. This seems OK at first glance since White has three pieces missing. But all the missing White pieces are pawns, and they are from the right half of the board... so they must have promoted. This implies more pawn captures to either get the Black pawns out of the way or to get the White pawns around them. (The promoted pieces could have been captured by the Black pawns, or the original pieces could have been captured in which case the promoted pieces are on the board now.) Finally, the h-pawns on h5 and h6 could not have got into their present position without at least one pawn capture by White, or at least two pawn captures by Black. • #### Mark your variadic logging function with __format_string to have PREfast catch format specifier errors • 0 Comments There are a handful of Problems (with a capital P) which occur over and over again in programming. One of them is Logging. It is incredibly convenient to use the variadic printf function to log strings with values of common types embedded in them: // spot the bug LOG(L"Measurement shows %lg% deviation", 100.0 * abs(expected - actual) / expected); However, printf is very error prone. It is very easy to use the wrong format specifier like %d instead of %Id, or to forget to escape a special character like % or \. In particular, the above line contains a bug. Static code analysis tools like PREfast are quite good at catching these kinds of errors. If my LOG macro was something like this, PREfast would catch the bug: #define LOG(fmt, ...) wprintf(fmt L"\n", __VA_ARGS__) This works because PREfast knows that the first argument to wprintf is a format string, and can match up the format specifiers with the trailing arguments and verify that they match. If you implement your own variadic logger function, though, PREfast doesn't necessarily know that the last explicit argument is a format specifier - you have to tell it. For example, PREfast will NOT catch format specifier issues if the LOG macro is defined like this: // PREfast doesn't know Format is a format string interface IMyLogger { virtual void Log(LPCWSTR Format, ...) = 0; }; extern IMyLogger *g_Logger; #define LOG(fmt, ...) g_Logger->Log(fmt, __VA_ARGS__) How do you tell it? Well, let's look at the declaration of wprintf. It's in (SDK)\inc\crt\stdio.h: _CRTIMP __checkReturn_opt int __cdecl wprintf(__in_z __format_string const wchar_t * _Format, ...); The relevant part here is __format_string. So the fixed IMyLogger declaration looks like this: // Now PREfast can catch format specifier issues interface IMyLogger { virtual void Log(__format_string LPCWSTR Format, ...) = 0; }; extern IMyLogger *g_Logger; #define LOG(fmt, ...) g_Logger->Log(fmt, __VA_ARGS__) • #### Beep sample • 0 Comments A question came in today about the Beep(...) API1 not being able to set the frequency of the beep that was generated. In order to confirm that it worked I whipped up a quick sample which would take the frequency (and duration) on the command line. Source and binaries attached. For fun I added the ability to pass in the frequency using Scientific pitch notation. Note that A4 is about 431 Hz using this scale, rather than the more standard 440 Hz2. for (int i = 1; i + 1 < argc; i += 2) { ULONG frequency; HRESULT hr = HertzFromScientificPitchNotation(argv[i], &frequency); if (FAILED(hr)) { return -__LINE__; } ULONG duration; hr = UlongFromString(argv[i + 1], &duration); if (FAILED(hr)) { return -__LINE__; } if (!Beep(frequency, duration)) { LOG(L"Beep(%u, %u) failed: GetLastError() = %u", frequency, duration, GetLastError()); return -__LINE__; } } So, for example, you can play a certain well-known tune via Beep() using this command: >beep.exe C3 2000 G3 2000 C4 4000 E4 500 Eb4 3500 C3 500 G2 500 C3 500 G2 500 C3 500 G2 500 C3 2000 1 More on the Beep(...) API: The official Beep(...) documentation A couple of blog posts from Larry Osterman: Beep Beep What’s up with the Beep driver in Windows 7? 2 If you want the more standard pitch, change this line: double freq = 256.0; To this: double freq = 440.0 * pow(semitoneRatio, -9.0); // C4 is 9 semitones below A4 • #### Command-line app to set the desktop wallpaper • 0 Comments Working on Windows, I find myself installing Windows a lot. I find that I like to change a lot of the settings that Windows offers to non-default values. (That is, I'm picky.) I have a script which automates some of these things, which I add to now and again. Some of the bits of the script are straightforward, but once in a while the tweak itself is of interest. One of the things I love about my work setup is the many large monitors. So, one of the things I like to change is the desktop wallpaper image. Changing the desktop wallpaper required some code, which makes it "of interest." Here's the code. // main.cpp #include <windows.h> #include <winuser.h> #include <stdio.h> int _cdecl wmain(int argc, LPCWSTR argv[]) { if (1 != argc - 1) { wprintf(L"expected a single argument, not %d\n", argc); return -__LINE__; } if (!SystemParametersInfo( SPI_SETDESKWALLPAPER, 0, const_cast<LPWSTR>(argv[1]), SPIF_SENDCHANGE )) { DWORD dwErr = GetLastError(); wprintf(L"SystemParametersInfo(...) failed with error %d\n", dwErr); return -__LINE__; } wprintf(L"Setting the desktop wallpaper to %s succeeded.\n", argv[1]); return 0; } Binaries attached. Warning: if you pass a relative path to this tool, it won't qualify it for you, and the SystemParametersInfo call won't either - so the wallpaper you want won't be set, though all the calls will succeed. Make sure to specify a fully-qualified path. • #### How to create a shortcut from the command line • 0 Comments Working on Windows, I install Windows a lot. This means a lot of my customizations have to be re-applied every time I install. To save myself some time I created a script which applies some of them. Last time I showed how to set the desktop wallpaper from a command-line app. This time, a script to create a shortcut. The example usage creates a shortcut to Notepad and puts that in the "SendTo" folder. I find this very useful because I often need to edit text files that have non-".txt" assocations. (There are also other shortcuts I create with it.) Here's the script: >create-shortcut.vbs If WScript.Arguments.Count < 2 Or WScript.Arguments.Count > 3 Then WScript.Echo "Expected two or three arguments; got " & WScript.Arguments.Count WScript.Echo "First argument is the file to create" WScript.Echo "Second is the command to link to" WScript.Echo "Third, if present, is the arguments to pass" WScript.Quit End If Set shell = WScript.CreateObject("WScript.Shell") Set link = shell.CreateShortcut(WScript.Arguments(0)) link.TargetPath = WScript.Arguments(1) If WScript.Arguments.Count = 3 Then link.Arguments = WScript.Arguments(2) End If link.Save >cscript create-shortcut.vbs "%appdata%\Microsoft\Windows\SendTo\Notepad.lnk" notepad.exe • #### Generating primes using the Sieve of Eratosthenes plus a few optimizations • 0 Comments When solving Project Euler problems I frequently need to iterate over prime numbers less than a given n. A Sieve of Eratosthenes method quickly and easily finds the small prime numbers; there are more complicated methods that find larger prime numbers, but with a couple of tweaks the Sieve of Eratosthenes can get quite high. A naive implementation for finding the set of primes below n will: 1. Allocate an array of n booleans, initialized to false. 2. Allocate an empty list 3. For each i in the range 2 to n: 1. If the boolean value at this index in the array is true, i is composite. Skip to the next value and check that. 2. If the boolean value at this index in the array is false, i is prime! 3. Add i to the list of primes 4. For each multiple of i in the range 2i to n, set the boolean value at that index in the array to true There are a handful of simple optimizations that can be made to this naive implementation: 1. Step 3d) will have no effect until the multiple of i reaches i2, so the range can be changed to "i2 to n" 2. As a direct consequence of this, step 3d) can be skipped entirely once i2 passes n. 3. Instead of allocating an array of n booleans, an array of nbits will suffice. 4. All the even-indexed bits are set to true on the first pass. Manually recognize that 2 is prime, and only allocate bits for odd-numbered values. Change the outer loop in 3) to "in the range 3 to n", incrementing by two each time. Change the loop 3d) to increment by 2i each time. 5. Storing the list of primes takes a lot of memory - more than the sieve. Don't bother creating a list of primes, just write an enumerator that travels the sieve directly. With these optimizations I can enumerate primes from 2 up to 5 billion (5 * 109) in about seven minutes. Source and binaries attached. >primes 5000000000 Will enumerate primes <= 5000000000 = 5e+009 Memory for sieve: 298.023 MB Initialization complete: 983 milliseconds since start Sieving to 70711 Sieving complete: 4.70292 minutes since start Picking up the rest to 5000000000 Pickup complete: 6.12252 minutes since start Primes: 234954223 1: 2 23495423: 442876981 46990845: 920233121 70486267: 1410555607 93981689: 1909272503 117477111: 2414236949 140972533: 2924158169 164467955: 3438252577 187963377: 3955819157 211458799: 4476550979 234954221: 4999999883 Enumerating complete: 7.43683 minutes since start Freeing CPrimes object There are more complicated sieves like the Sieve of Atkin which perform better but at the cost of being much more complex. So far I haven't had to resort to any of those. • #### Programmatically grabbing a screenshot of the primary display • 0 Comments It's sometimes difficult to explain to people what my job actually is. "I test Windows sound." "Cool. How does that work?" A product like Windows has a lot of components that interact with each other. If everything works, the user doesn't know that most of these components even exist; everything is invisible and seamless. Most testing involves the connection ("interface") between two components. "I test APIs." To the uninitiated, this is just a word. It sounds like "I test wakalixes." "You test what, now?" There are two interfaces which are easier to explain. There's the software-to-hardware interface, where the driver talks to the hardware. "I test the HD Audio, USB Audio, and Bluetooth audio class drivers." "Huh?" "They make the speakers and the microphone work." "Oh, cool. So you sit around and use Skype all day?" But the easiest of all to explain is the user interface. "I make sure that the Sound Recorder app, the volume slider, and the Sound control panel work." "Oh, that! I had this annoying problem once where..." What does the test result for an invisible interface look like? A lot of logging. "I expected this call to succeed; it returned this HRESULT." "I poked the hardware like this and got a bluescreen." "There seems to be an infinite loop here." Lots of text. Boring. UI testing has logging too. But with UI testing you can also... TAKE PICTURES! A UI bug is a lot easier to understand (triage, and fix) if there's a screenshot attached (preferably with a big red rectangle highlighting the problem.) It is therefore valuable to have an automatable utility that can take a screenshot and dump it to a file. Here's one I cribbed together from the "Capturing an Image" sample code on http://msdn.microsoft.com/en-us/library/dd183402(v=VS.85).aspx. Source and binaries attached. This version only captures the main display, and not secondary monitors (if any.) Pseudocode: screen_dc = GetDC(nullptr); memory_dc = CreateCompatibleDC(screen); rect = GetClientRect(GetDesktopWindow()); hbmp = CreateCompatibleBitmap(screen_dc, rect); SelectObject(memory_dc, hbmp); BitBlt(memory_dc, rect, screen_dc); bmp = GetObject(hbmp); bytes = allocate enough memory bytes = GetDIBits(screen_dc, bmp, hbmp) file = CreateFile(); WriteFile(bitmap header); WriteFile(bytes); • #### Excruciating rhymes • 0 Comments I was watching How the Grinch Stole Christmas and I was struck by this rhyme (from the song "You're a Mean One, Mr. Grinch:") You're a nauseous super naus! You're a dirty crooked jockey, and you drive a crooked hoss -- Dr. Seuss, How the Grinch Stole Christmas I tried to see what other particularly excruciating rhymes I could remember. I came up with two: You know, that little guy, he's got me feeling all contempt-ey: He takes his boat out loaded up and brings it back in empty. -- Phil Vischer, Lyle the Kindly Viking And then of course: In short, when I've a smattering of elemental strategy, You'll say a better Major-General had never sat a-gee! -- W. S. Gilbert, The Pirates of Penzance • #### Teaching someone to fish and the AKS primality test • 0 Comments 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 p> 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. My own Perl implementation follows: use strict; # use bignum; print <<USAGE and exit 0 unless @ARGV;$0 [-v] n
Use the AKS primality test to check whether n is prime
USAGE

sub is_power($$); sub ceil_log2(); sub first_r($$);
sub check_gcds($$); sub check_polynomials($$$); sub gcd($$); sub totient(); sub polypow($$\@); sub polymult($$\@\@); sub polyeq(\@\@); my verbose = ARGV[0] eq "-v"; shift @ARGV if verbose; die "Expected only one argument" unless 1 == @ARGV; my n = shift; # step 0: restrict to integers >= 2 print "n is not an integer and so is NEITHER PRIME NOR COMPOSITE\n" and exit 0 unless int(n) == n; print "n < 2 and so is NEITHER PRIME OR COMPOSITE\n" and exit 0 unless n >= 2; # step 1: check if the number is a power of some lower number. # this can be done quickly by iterating over the exponent (2, 3, ...) # and doing a binary search on the base. # we start at the top and work down for performance reasons; # several subroutines need to know ceil(log2(n)) so we calculate it once and pass it around. my log2_n = ceil_log2(n); is_power(n, log2_n) and exit 0; print "Not a power.\n"; # step 2: find the smallest r such that o_r(n) > (log2 n)^2 # where o_r(n) is the multiplicative order of n mod r # that is, the smallest k such that n^k == 1 mod r my r = first_r(n, log2_n); print "r = r\n"; # step 3: for all a between 2 and r inclusive, check whether gcd(a, n) > 1 check_gcds(n, r) or exit 0; # step 4: if r >= n, we're done if (r >= n) { print "r >= n so n is PRIME\n"; exit 0; } # step 5: for all a between 1 and floor( sqrt(phi(r)) log2(n) ) # check whether (x + a)^n = x^n + a mod x^r - 1, n check_polynomials(n, r, log2_n) or exit 0; # step 6: if we got this far, n is prime print "n is PRIME\n"; sub is_power($$) { my$n = shift;
my $log2_n = shift; # actually ceil(log2(n)) print "Checking for power-ness...\n"; # we consider numbers of the form b^i # we iterate over the exponent i # starting at i = ceil(log2(n)) and working down to i = 2 # # for each exponent we do a binary search on the base # the lowest the base can be is 2 # and the highest the base can be (initially) is 2 # # we set up bounds on the base that are guaranteed to # surround the actual base my$b_low = 1; # 1 ^ ceil(log2(n)) = 1 < n
my $b_high = 3; # 3 ^ ceil(log2(n)) > 2 ^ log2(n) = n for (my$i = $log2_n;$i >= 2; $i--) { print "\tb^$i\n" if $verbose; # let's check that the bounds are really correct die "$b_low ^ $i is not <$n" unless $b_low **$i < $n; die "$b_high ^ $i is not >$n" unless $b_high **$i > $n; # do a binary search to find b such that b ^ i = n while ($b_high - $b_low > 1) { print "\t\tb^$i: b is between $b_low and$b_high\n" if $verbose; my$b = int(($b_low +$b_high)/2);

my $t =$b ** $i; if ($t == $n) { print "$n = $b^$i; $n is COMPOSITE\n"; return 1; } ($t > $n ?$b_high : $b_low) =$b;
}

# as we pass from the exponent (say, 5)
# to the exponent below (say, 4)
# we need to reconsider our bounds
#
# b_low can remain the same because b ^ (i - 1) is even less than b ^ i
# OPEN ISSUE: can we even raise b_low?
#
# but we need to raise b_high since b ^ i > n does NOT imply b ^ (i - 1) > n
#
# we'll square b_high; b ^ i > n => (b ^ 2) ^ (i - 1) = b ^ (2 i - 2) > n
# since i >= 2
#
# OPEN ISSUE: is there a better way to raise this higher bound? Does this help much?
$b_high *=$b_high;
}

# nope, not a power
return 0;
}

sub ceil_log2($) { my$n = shift;

my $i = 0; my$t = 1;

until ($t >=$n) {
$i++;$t *= 2;
}

return $i; } sub first_r($$) { my n = shift; my log2_n = shift; # actually ceil(log2(n)) my s = log2_n ** 2; print "Looking for the first r where o_r(n) > s...\n"; # for each r we want to find the smallest k such that # n^k == 1 mod r my r; for (r = 2; ; r++) { # print "\tTrying r...\n"; # find the multiplicative order of n mod r my k = 1; my t = n % r; until (1 == t or k > s) { t = (t * n) % r; k++; } if (k > s) { # print "\to_r(n) is at least k\n"; last; } else { # print "\to_r(n) = k\n"; } } return r; } sub check_gcds($$) { my ($n, $r) = @_; print "Checking GCD($n, a) for a = 2 to $r...\n"; for (my$a = 2; $a <=$r; $a++) { my$g = gcd($n,$a);

next if ($g ==$n); # this is OK

if (1 != $g) { print "gcd($n, $a) =$g; $n is COMPOSITE\n"; return 0; } } print "All GCDs are 1 or$n\n";

return 1;
}

sub gcd($$) { my (x, y) = @_; (x, y) = (y, x) unless x > y; while (y) { (x, y) = (y, x % y); } return x; } sub check_polynomials($$$) { my$n = shift;
my $r = shift; my$log2_n = shift; # actually ceil(log2(n))

# iterate over a from 1 to floor( sqrt(phi(r)) log2(n) )
# for each a, check whether the polynomial equality holds:
# (x + a)^n = x^n + a mod (x^r - 1, n)
# if it fails to hold, the number is composite
#
# first we need to evaluate phi(r) so we can determine the upper bound
# OPEN ISSUE: this seems to be a potential weakness in the algorithm
# because the usual way to evaluate phi(r) is to find the prime factorization of r
# and then form the product r*PI(1 - 1/p) where the product ranges over all primes
# which divide r

my $phi = totient($r);

# a < sqrt(phi(r)) * log2(n) => a^2 < phi(r) * (log2(n))^2
my $a2_max =$phi * $log2_n *$log2_n;
print "Checking polynomials up to roughly ", int sqrt($a2_max), "...\n"; for (my$a = 1; $a *$a <= $a2_max;$a++) {
print "\ta = $a...\n" if$verbose;

# polynomials are of the form (c0, c1, c2, ..., ci, ...)
# which corresponds to c0 + c1 x + c2 x^2 + ... + ci x^i + ...)
my @x = (0, 1);
my @x_plus_a = ($a %$n, 1);

my @lhs = polypow($n,$r, @x_plus_a);

# POTENTIAL OPTIMIZATION:
# x^n + a mod (x^r - 1) is just x^(n % r) + a
# and we know n % r != 0
my @rhs = polypow($n,$r, @x); # x^n
$rhs[0] = ($rhs[0] + $a) %$n; # + a

next if polyeq(@lhs, @rhs);

print "(x + $a)^$n is not equal to x^$n +$a mod(x^$r - 1,$n)\n";
print "So $n is COMPOSITE\n"; return 0; } return 1; } sub totient($) {
my $r = shift; print "Finding the Euler totient of$r\n";

# we'll do a trial division to find the totient
# there are faster ways that use a sieve
# but we don't know how big r is
my $t =$r;

# by construction p will always be prime when it is used
# OPEN ISSUE: this might be slow
for (my $p = 2;$r > 1; $p++) { next if$r % $p; print "\t$p is a factor\n" if $verbose; # decrease the totient$t /= $p;$t *= $p - 1; # decrease r$r /= $p; # we know there's at least one factor of p$r /= $p until$r % $p; # there might be more } print "Totient is$t\n";

return $t; } sub polypow($$\@) { my n = shift; # this is both the mod and the exponent my r = shift; my @base = @{ +shift }; my exp = n; my @result = (1); # 1 # print "\t(", join(" ", @base), ")^exp mod (x^r - 1, n)\n" if verbose; # basic modpow routine, but with polynomials while (exp) { if (exp % 2) { @result = polymult(n, r, @result, @base); } exp = int (exp / 2); @base = polymult(n, r, @base, @base); } # print "\t= (", join(" ", @result), ")\n" if verbose; return @result; } sub polymult($$\@\@) { my$n = shift;
my $r = shift; my @first = @{ +shift }; my @second = @{ +shift }; # print "\t\t(", join(" ", @first), ") * (", join(" ", @second), ") mod (x^$r - 1, $n)\n" if$verbose;

my @result = ();

# first do a straight multiplication first * second
my $s = @second - 1; for (my$i = @first - 1; $i >= 0;$i--) {
for (my $j =$s; $j >= 0;$j--) {
my $k =$i + $j;$result[$k] +=$first[$i] *$second[$j];$result[$k] %=$n;
}
}

# then do a straight mod x^r - 1
# consider a polynomial
# c0 + ... + ck x^k
# with k >= r
# we can subtract ck (x^r - 1)
# without changing the mod value
# the net effect is to eliminate the x^k term
# and add ck to the x^(k - r) term

for (my $i = @result - 1;$i >= $r;$i--) {
my $j =$i - $r;$result[$j] +=$result[$i];$result[$j] %=$n;

pop @result;
}

# eliminate any leading zero terms
for (my $i = @result - 1; 0 ==$result[$i];$i--) {
pop @result;
}

# print "\t\t= (", join(" ", @result), ")\n" if $verbose; return @result; } sub polyeq(\@\@) { my @lhs = @{ +shift }; my @rhs = @{ +shift }; # print "(", join(" ", @lhs), ") = (", join(" ", @rhs), ")?\n" if$verbose;

return 0 unless @lhs == @rhs;

for (my $i = @lhs - 1;$i >= 0; $i--) { return 0 unless$lhs[$i] ==$rhs[$i]; } return 1; } Here's the output when I run it on 19: >perl -w aks.pl 19 Checking for power-ness... Not a power. Looking for the first r where o_r(19) > 25... r = 19 Checking GCD(19, a) for a = 2 to 19... All GCDs are 1 or 19 19 >= 19 so 19 is PRIME And here's the output with a bigger input: >perl -w aks.pl 99 Checking for power-ness... Not a power. Looking for the first r where o_r(997) > 100... r = 103 Checking GCD(997, a) for a = 2 to 103... All GCDs are 1 or 997 Finding the Euler totient of 103 Totient is 102 Checking polynomials up to roughly 100... 997 is PRIME • #### Enumerating MIDI devices • 0 Comments In addition to audio playback and recording, Windows Multimedia (WinMM) provides a Musical Instrument Digital Interface (MIDI) API. Here's how to make a list of all the MIDI devices on the system, their capabilities, and the hardware device interface associated with each of them. Source and binaries attached. Pseudocode: midiInGetNumDevs or midiOutGetNumDevs for each device midiInGetDevCaps or midiOutGetDevCaps log device capabilities midiInMessage or midiOutMessage with DRV_QUERYDEVICEINTERFACESIZE and DRV_QUERYDEVICEINTERFACE log the device interface Output: >midienum.exe midiIn devices: 1 -- 0: USB2.0 MIDI Device -- Device ID: 0 Manufacturer identifier: 65535 Product identifier: 65535 Driver version: 1.6 Product name: USB2.0 MIDI Device Support: 0x0 Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..." midiOut devices: 2 -- 0: Microsoft GS Wavetable Synth -- Device ID: 0 Manufacturer identifier: 1 Product identifier: 27 Driver version: 1.0 Product name: Microsoft GS Wavetable Synth Technology: 7 (MOD_SWSYNTH) Voices: 32 Notes: 32 Channel mask: 0xffff Support: 0x1 MIDICAPS_VOLUME Device interface: "" -- 1: USB2.0 MIDI Device -- Device ID: 1 Manufacturer identifier: 65535 Product identifier: 65535 Driver version: 1.6 Product name: USB2.0 MIDI Device Technology: 1 (MOD_MIDIPORT) Voices: 0 Notes: 0 Channel mask: 0xffff Support: 0x0 Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..." (Actual device interface string suppressed.) Note the Microsoft GS Wavetable Synth device, which is always present. Why would you want to know the device interface? In our case, because we want to test all the audio-related interfaces of a particular device on the system. • #### Enumerating mixer devices, mixer lines, and mixer controls • 0 Comments The WinMM multimedia APIs include an API for enumerating and controlling all the paths through the audio device; things like bass boost, treble control, pass-through audio from your CD player to your headphones, etc. This is called the "mixer" API and is the forerunner of the IDeviceTopology API. I wrote a quick app to enumerate all the mixer devices on the system; for each mixer device, enumerate each mixer line (that is, each source and destination); for each mixer line, enumerate all the controls (volume, mute, equalization, etc.); and for each control, query the associated text (if any) and the current value. Source and binaries attached. Pseudocode: mixerGetNumDevs() for each mixer device mixerGetDevCaps(dev) for each destination (line) on the device mixerGetLineInfo(dest) mixerGetLineControls(dest) for each control on the line if the control supports per-item description mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_LISTTEXT) log the per-item description mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_VALUE) log the value(s) Usage: >mixerenum.exe Mixer devices: 5 -- 0: Contoso headset -- Device ID: 0 Manufacturer identifier: 1 Product identifier: 104 Driver version: 6.2 Product name: Contoso headset Support: 0x0 Destinations: 1 -- Destination 0: Master Volume -- Destination: 0 Source: -1 Line ID: 0xffff0000 Status: MIXERLINE_LINEF_ACTIVE (1) User: 0x00000000 Component Type: MIXERLINE_COMPONENTTYPE_DST_HEADPHONES (5) Channels: 1 Connections: 2 Controls: 2 Short name: Volume Long name: Master Volume -- Target: -- Type: MIXERLINE_TARGETTYPE_UNDEFINED (0) Device ID: 0 Manufacturer identifier: 65535 Product identifier: 65535 Driver version: 0.0 Product name: -- Control 1: Mute -- Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Mute Long name: Mute -- Values -- FALSE -- Control 2: Volume -- Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Volume Long name: Volume -- Values -- 0xffff on a scale of 0x0 to 0xffff -- 1: HDMI Audio (Contoso -- Device ID: 1 Manufacturer identifier: 1 Product identifier: 104 Driver version: 6.2 Product name: HDMI Audio (Contoso Support: 0x0 Destinations: 1 -- Destination 0: Master Volume -- Destination: 0 Source: -1 Line ID: 0xffff0000 Status: MIXERLINE_LINEF_ACTIVE (1) User: 0x00000000 Component Type: MIXERLINE_COMPONENTTYPE_DST_DIGITAL (1) Channels: 1 Connections: 2 Controls: 2 Short name: Volume Long name: Master Volume -- Target: -- Type: MIXERLINE_TARGETTYPE_UNDEFINED (0) Device ID: 0 Manufacturer identifier: 65535 Product identifier: 65535 Driver version: 0.0 Product name: -- Control 1: Mute -- Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Mute Long name: Mute -- Values -- FALSE -- Control 2: Volume -- Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Volume Long name: Volume -- Values -- 0xffff on a scale of 0x0 to 0xffff -- 2: Speakers (Contoso -- Device ID: 2 Manufacturer identifier: 1 Product identifier: 104 Driver version: 6.2 Product name: Speakers (Contoso Support: 0x0 Destinations: 1 -- Destination 0: Master Volume -- Destination: 0 Source: -1 Line ID: 0xffff0000 Status: MIXERLINE_LINEF_ACTIVE (1) User: 0x00000000 Component Type: MIXERLINE_COMPONENTTYPE_DST_SPEAKERS (4) Channels: 1 Connections: 2 Controls: 2 Short name: Volume Long name: Master Volume -- Target: -- Type: MIXERLINE_TARGETTYPE_UNDEFINED (0) Device ID: 0 Manufacturer identifier: 65535 Product identifier: 65535 Driver version: 0.0 Product name: -- Control 1: Mute -- Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Mute Long name: Mute -- Values -- FALSE -- Control 2: Volume -- Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Volume Long name: Volume -- Values -- 0xffff on a scale of 0x0 to 0xffff -- 3: Contoso headset -- Device ID: 3 Manufacturer identifier: 1 Product identifier: 104 Driver version: 6.2 Product name: Contoso headset Support: 0x0 Destinations: 1 -- Destination 0: Master Volume -- Destination: 0 Source: -1 Line ID: 0xffff0000 Status: MIXERLINE_LINEF_ACTIVE (1) User: 0x00000000 Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7) Channels: 1 Connections: 1 Controls: 2 Short name: Volume Long name: Master Volume -- Target: Contoso headset -- Type: MIXERLINE_TARGETTYPE_WAVEIN (2) Device ID: 0 Manufacturer identifier: 1 Product identifier: 101 Driver version: 6.2 Product name: Contoso headset -- Control 1: Mute -- Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Mute Long name: Mute -- Values -- FALSE -- Control 2: Volume -- Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Volume Long name: Volume -- Values -- 0xf332 on a scale of 0x0 to 0xffff -- 4: Microphone (Contoso -- Device ID: 4 Manufacturer identifier: 1 Product identifier: 104 Driver version: 6.2 Product name: Microphone (Contoso Support: 0x0 Destinations: 1 -- Destination 0: Master Volume -- Destination: 0 Source: -1 Line ID: 0xffff0000 Status: MIXERLINE_LINEF_ACTIVE (1) User: 0x00000000 Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7) Channels: 1 Connections: 1 Controls: 2 Short name: Volume Long name: Master Volume -- Target: Microphone (Contoso -- Type: MIXERLINE_TARGETTYPE_WAVEIN (2) Device ID: 1 Manufacturer identifier: 1 Product identifier: 101 Driver version: 6.2 Product name: Microphone (Contoso -- Control 1: Mute -- Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Mute Long name: Mute -- Values -- FALSE -- Control 2: Volume -- Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001) Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1) Item count: 0 Short name: Volume Long name: Volume -- Values -- 0xf332 on a scale of 0x0 to 0xffff • #### Muting all audio outputs with IAudioEndpointVolume • 0 Comments I have a selfhost tool that I use to mute all audio outputs programmatically. Pseudocode: IMMDeviceEnumerator::EnumAudioEndpoints for each device: IMMDevice::Activate(IAudioEndpointVolume) IAudioEndpointVolume::SetMute(TRUE) Source and binaries attached. • #### Implementing a "say" command using ISpVoice from the Microsoft Speech API • 0 Comments I've known for a while that Microsoft Windows comes with text-to-speech and speech-to-text APIs, which power the Narrator and Speech Recognition features respectively. This forum post prompted me to mess around with them a little. I came up with this implementation of a say.exe command which takes a single argument as text, and then uses the ISpVoice text-to-speech API to have the computer speak it aloud. Source and binaries attached. Pseudocode: CoInitialize(nullptr); CoCreateInstance(ISpVoice) pSpVoice->Speak(text); Usage: >say.exe "Daisy, Daisy; give me your answer, do." More information on the Speech APIs available here: http://msdn.microsoft.com/en-us/library/ms723627(v=vs.85).aspx • #### unattend.xml: turning on Remote Desktop automatically • 0 Comments Here are the portions of my unattend.xml file which are needed to turn on Remote Desktop automatically. This piece flips the "no remote desktop" kill switch to "allow." <settings pass="specialize"> ... <component name="Microsoft-Windows-TerminalServices-LocalSessionManager" ...> <fDenyTSConnections>false</fDenyTSConnections> That's not enough; it is also necessary to poke a hole in the firewall to allow inbound connections. I use an indirect string for the Group name, to allow for installing localized builds. This points to the "Remote Desktop" feature group. <settings pass="specialize"> ... <component name="Networking-MPSSVC-Svc" ...> <FirewallGroups> <FirewallGroup wcm:action="add" wcm:keyValue="RemoteDesktop"> <Active>true</Active> <Profile>all</Profile> <Group>@FirewallAPI.dll,-28752</Group> If your user account is a member of the "Administrators" group, you're done: <settings pass="oobeSystem"> <component name="Microsoft-Windows-Shell-Setup" ...> <UserAccounts> <LocalAccounts> <LocalAccount wcm:action="add"> <Password> <Value>#PASSWORD_ADMIN#</Value> <PlainText>true</PlainText> </Password> <Name>Admin</Name> <Group>Administrators</Group> But if you're like me and you don't want to live in the Administrators group, you need to join the Remote Desktop Users group to be able to log in remotely: <settings pass="oobeSystem"> <component name="Microsoft-Windows-Shell-Setup" ...> <UserAccounts> <DomainAccounts> <DomainAccountList wcm:action="add"> <Domain>redmond.corp.microsoft.com</Domain> <DomainAccount wcm:action="add"> <Group>RemoteDesktopUsers</Group> <Name>MatEer</Name> • #### Weighing the Sun and the Moon • 0 Comments In an earlier post I mentioned how the Cavendish experiment allowed us to weigh the Earth - to determine the mass of the Earth mE. Newton knew the acceleration due to gravity on the surface of the Earth and was able to use that to find the product G mE; Cavendish determined G directly, and was thus able to solve for mE. He would also have been able to find the mass of the sun as follows: mE aE = G mE mS / rE2 G, rE, and aE = vE2 / rE are known, so we can solve for mS. But calculating the mass of the moon is trickier. Once we were able to put a satellite around the moon we could measure its orbital radius and speed, deduce the acceleration, and use that plus the known G to calculate the mass of the moon. But prior to that we were limited to techniques like: The moon does not exactly orbit the Earth, but instead orbits the center of mass of the moon/Earth system. By careful observation we can determine where this center of mass is. We can then measure the distance between the center of mass and the Earth's center. This plus the known mass of the Earth and the distance of the Earth from the Moon allows us to determine the mass of the Moon. If we're lucky enough to see a foreign object come close to the moon, we can determine how much it is accelerated by the Moon. This will allow us to determine the mass of the Moon using the technique above. (We won't be able to determine the mass of the foreign object, but we don't need it.) When the USSR launched Sputnik, American scientists really wanted to know what its mass was. But because none of the techniques above were useful, they were unable to determine it. • #### Programmatically rearranging displays • 0 Comments Most of my test machines and my laptop have a single display; but I have two dev machines which are each connected to two displays. When I clean install Windows, I sometimes need to rearrange the displays: Since I clean install Windows frequently, I wrote myself a little C++ app which does this programmatically using EnumDisplayDevices / EnumDisplaySettings / ChangeDisplaySettingsEx. Source and binaries attached. Pseudocode: for (each device returned by EnumDisplayDevices) { grab the position and the height/width using EnumDisplaySettings } calculate the desired position of the secondary monitor Set it using ChangeDisplaySettingsEx with DM_POSITION Call as: >swapmonitors Moved secondary monitor to (1920, 0) EDIT: Oops: 0 should be CDS_GLOBAL | CDS_UPDATEREGISTRY, to make the settings apply to all users, and to persist across display resets / reboots LONG status = ChangeDisplaySettingsEx( nameSecondary, &mode, nullptr, // reserved CDS_GLOBAL | CDS_UPDATEREGISTRY, // was 0 nullptr // no video parameter ); • #### Windows Sound test team rowing morale event • 0 Comments Last Friday the Windows Sound test team went kayaking. We went to the Agua Verde paddle club and kayaked around Union Bay for a while. Here's the route we took: More detail: http://connect.garmin.com/activity/179545084 • #### Why square waves have ears: Gibbs' phenomenon (Wilbraham's phenomenon) • 0 Comments In a recent post I sung the praises of square waves as a way to get a heckuva lot of power (3 dB more power than a sine wave) into a sample-range-limited signal. It's time to take them down a notch now. A problem with square waves is they're impossible to generate in the analog domain. In fact, you can't even get close. Signals generated in the analog domain are subject to physical laws regarding continuity (no teleportation) and whatnot. A common way to model these is to express (periodic) analog signals using a basis of sine waves with integral periods. Suppose I want to generate the square wave:  f(x) = 1, -π < x < 0 -1, 0 < x < π Graphed below are some approximations of this function using sine waves as a basis. Note that only odd values of n are used in the sums of sin(nx). The sums converge to +/-1 quite well, but there are definite "ears" at x near 0 where there's overshoot. This doesn't appear to die down. A closeup of one of the "ears": If anything, rather than dying down, the "ears" converge to max(fn) → about 1.18, or about 9% of the "jump" from -1 to 1. (Dym and McKean, in their 1972 book Fourier Series and Integrals, get the 9% right but incorrectly assert that the convergence is to 1.09.) This mathematical phenomenon - Gibbs' phenomenon - is a good illustration of the difference between convergence of a series of functions and uniform convergence. In this case, the series of partial sums pointwise converge to the square wave... for any given point x > 0 and ε > 0, the ear will eventually move to the left, and I can choose an N such that fn(x) is within of ε of 1 for all n > N... ... but the series does not uniformly converge to the square wave. The following assertion is false: "for any given ε > 0, I can pick an N such that fn(x) is within of ε of 1 for all n > N and all x > 0." This can be demonstrated by picking ε = 0.17, say. For any n, even, say, n = 10100, there is an x close to 0 where f1e100(x) > 1.17. • #### Minimal unsatisfiable regular expression, XPath query • 0 Comments Regular expressions are a tool for matching generic text. XPath queries are a tool for matching chunks of XML. Both are search technologies. When using search technologies it is occasionally quite useful to have a query that will never match anything - for SQL, this would be something like "SELECT 1 WHERE 1 = 0". My candidates for minimal unsatisfiable regular expression: /a\bc/ \b is a zero-width assertion that matches a boundary at the beginning or end of a word - specifically, it is true between a word-ish character (\w) and a non-wordish character (\W). Since literal "a" and "c" are both wordish characters, this will never match. Or, if you allow Perl extensions: /(?!)/ This is a negative lookahead for an empty string. Since the empty string always matches everywhere, this will never match. My candidate for minimal unsatisfiable XPath query: /parent::* This matches everything at or under the parent of the root element. Since, by definition, the root element has no parent, this will never match. • #### Second cousins, cousins once removed; relationships by generations to common ancestor • 0 Comments Raymond Chen explains some common terms for blood relatives of varying distance across cultures in his blog post "What kind of uncle am I?" He links to a diagram on genealogy.com that I felt was lacking something... so here's my version, with consanguinary colors. Red means "marriage is almost certainly legally prohibited." Yellow means "marriage may be legally prohibited - check your region's laws." Green means "marriage is amost certainly legal."  Relationship by generations to common ancestor # 0 1 2 3 4 ... m 0 self father/mother grand(father/mother) great‑grand(father/mother) (great‑)2grand(father/mother) (great-)m ‑ 2grand(father/mother) 1 son/daughter brother/sister aunt/uncle grand(aunt/uncle) great‑grand(aunt/uncle) (great‑)m ‑ 3grand(aunt/uncle) 2 grand(son/daughter) niece/nephew (first) cousin first cousin,once removed first cousin,twice removed first cousin,(m ‑ 2) times removed 3 great‑grand(son/daughter) grand(niece/nephew) first cousin,once removed second cousin second cousin,once removed second cousin,(m ‑ 3) times removed 4 (great‑)2grand(son/daughter) great-grand(niece/nephew) first cousin,twice removed second cousin,once removed third cousin third cousin,(m ‑ 4) times removed ... n (great‑)n ‑ 2grand(son/daughter) (great‑)n ‑ 3grand(niece/nephew) first cousin,(n ‑ 2) times removed second cousin,(n ‑ 3) times removed third cousin,(n ‑ 4) times removed (n == m) ? ((n ‑ 1)th cousin) : ((min(n, m) ‑ 1)th cousin, |n ‑ m| times removed) • #### Bad Perl: locker problem • 0 Comments Bad Perl solution to the "print the open lockers" problem: perl -e"print join', ',map{$_*$_}1..sqrt pop" 100 54 characters. I prefer this to the 53-character solution obtained by omitting the space after the first comma. EDIT: 49 characters: perl -e"print map{$_*$_,' '}1..sqrt pop" 100 EDIT: 48: perl -e"print map{$_*$_.$/}1..sqrt pop" 100

EDIT: 47:

perl -e"map{print$/.$_*$_}1..sqrt pop" 100 I still think "say" is cheating but it does afford this very short solution: perl -E"map{say$_*$_}1..sqrt pop" 100 EDIT: Apparently I need to learn how to count. Counts above are off. Anyway, 41: perl -e"print$_*$_,$/for 1..sqrt pop" 100

• #### Good Perl, Bad Perl

One of my favorite languages is Perl.  Perl has an ambivalent reputation; some people take to it, some accuse it of being a syntax-complete language.  (There's some truth to this.)

My view is that Perl gives you a very direct link into the mind of the programmer - much more so than other languages.  Perl is designed very much like a spoken language, perhaps because Larry Wall's background is linguistics.

There was a little girl
Right in the middle of her forehead.
And when she was good,
She was very, very, good;
She was horrid.

(In an English accent, "forehead" and "horrid" actually rhyme.)

Two examples of my own Perl to illustrate my point.  This is in my email signature:

perl -e "print join er,reverse',','l hack',' P','Just anoth'"

And this little seasonal gem:

use strict;use warnings;sub receive($);my @ordinals = qw( zeroth first second third fourth fifth sixth seventh eighth ninth tenth eleventh twelfth);my @gifts = reverse split /\n/, <<END_OF_LIST; Twelve drummers drumming; Eleven pipers piping; Ten lords a-leaping; Nine ladies dancing; Eight maids a-milking; Seven swans a-swimming; Six geese a-laying; Five golden ringeds; Four colly birds; Three French hens; Two turtle doves; A partridge in a pear tree.END_OF_LISTfor (my$day = 1; $day <= 12;$day++) {	receive($day);}sub receive($) {	my $day = shift; print("On the ",$ordinals[$day], " day of Christmas, my true love sent to me:\n"); for (my$i = $day;$i > 0; $i--) { my$gift = $gifts[$i - 1];		if ($i == 1 &&$day != 1) {			$gift =~ s/^(\s*)A/$1And a/;		}		print $gift, "\n"; } if ($day != 12) {		print "\n";	}}

The latter kind of Perl I like to call "good Perl".  It's easy to read, I think.  There are a couple of idioms that take getting used to, just like with any new language, but well-written Perl is (I think) easier to read than any other language.

But flexibility has its dark sides as well.  Black Perl is the canonical example, but there are others such as Perl golf.  This kind of thing (the first sample above is an example) is responsible for at least part of Perl's reputation for opacity; its compatibility with shell scripting, and most particularly its embedded regular expression support, is responsible for much of the rest.

Exercise: duplicate the output of the second sample above using as short a Perl program as possible.

Page 5 of 6 (141 items) «23456