About Me

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

Archives

Common Tasks

| |

Matthew van Eerde's web log

Triangular primes: or, the dangers of non-rigorous proofs

Posted over 5 years ago

by Maurits [MSFT]
- 7 Comments
Beware of bugs in the above code; I have only proved it correct, not tried it.
-- Donald Knuth

If you've bowled, you know the arrangement of the bowling pins forms a triangle.
(Image courtesy of the International Pumpkin Federation.)
If you've played eight-ball, you know the arrangement of the fifteen billiard balls forms a triangle.

Ten, fifteen... what other numbers form a triangle? The common arrangement of nine-ball and ninepins doesn't count because it's a diamond, not a triangle.
You can start with ten and add five balls to make a triangle of fifteen... then add six more to make a triangle of 21... then seven more to make a triangle of 28... and so on, with this sequence:
..., 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231...
Start looking for patterns. What do you see? Nothing jumps out right away. Are there any primes? Ones that end in 0, 2, 4, 6, or 8 are obviously even and therefore not primes... ones that end in 5 are divisible by 5 and therefore not primes... the remaining ones fall due to specific cases (21 = 3 x 7; 91 = 7 x 13; 153 = 3 x 3 x 17; 171 = 3 x 3 x 19; 231 = 3 x 7 x 11...)
In fact, gosh darn it, it seems like none of these numbers are prime, no matter how far we extend that "..." on the right! Can this be a coincidence?
A few mental coruscations later I have an idea that it is not a coincidence... that triangular numbers, by there very nature, cannot be prime. In fact I'm even willing to call it a "proof." Here it is.
"Theorem": there are no triangular primes.

First we need to generate a formula for the triangular numbers. Note that if you take an n x (n + 1) rectangle and draw a zig-zag line like so, you get two triangles.

Each of these triangles is composed of n diagonals, the shortest of which is 1, and the longest of which is n. That is to say, each of the triangles is composed of t_n squares. So we know that the total number of squares in the rectangle is 2t_n.

But we also know that the total number of squares is the base times the height, or n(n + 1). This gives us 2t_n = n(n + 1), or t_n = n(n + 1)/2.

The next part of the "proof" breaks down into case analysis. n can be odd (as in the diagram, where n is 5) or even.

Case where n is even:

n is an even positive number. Therefore n/2 is a positive number (maybe odd, maybe even; doesn't matter.) t_n can be written as (n/2)(n + 1), and is therefore not prime, since it has at least four factors: 1, n/2, n + 1, and t_n.

Case where n is odd:

n is an odd positive number. Therefore n + 1 is an even positive number. Therefore (n + 1)/2 is a positive number (maybe odd, maybe even; doesn't matter.) t_n can be written as (n)([n + 1]/2), and is therefore not prime, since it has at least four factors: 1, n, (n + 1)/2, and t_n.

Note that the "proof" that t_n is not prime inevitably concludes in a stronger result - that t_n has at least four factors... not only is t_n not prime, it can't even have as few as three factors. (Some numbers with three factors: 4, 9, 25, 49...)

Exercise: what kind of numbers have exactly three factors?

A beautiful proof. Perhaps the two cases can be elegantly folded together to normalize it a bit better. That is not a serious problem.

There is a serious problem.

The proof of our result is doomed.

Why?

Because the result does not hold! There is a triangular prime.

Exercise: find a triangular prime.

After having recovered from the shocking revelation that, our beautiful proof to the contrary, a triangular prime is so rude as to exist, a little self-examination is in order. What is wrong with the proof? This... and not the existence of triangular primes... is the lesson to be learned: that beauty is not always truth.
The great tragedy of Science -- the slaying of a beautiful hypothesis by an ugly fact.
-- Thomas Huxley
Matthew van Eerde's web log

Sample: find out if your default audio playback and audio capture devices are on the same hardware

Posted over 5 years ago

by Maurits [MSFT]
- 5 Comments
vbBretty on the audio forums asked how to tell if a given audio output and a given audio input were on the same physical audio card.
I found the exercise interesting enough to share here:

// main.cpp

#define INITGUID

#include <windows.h>
#include <tchar.h>

const GUID GUID_NULL = { 0 };

#include <atlstr.h>
#include <mmdeviceapi.h>
#include <devicetopology.h>
#include <functiondiscoverykeys.h>

#define LOG(formatstring, ...) _tprintf(formatstring _T("\n"), __VA_ARGS__)

// helper class to CoInitialize/CoUninitialize
class CCoInitialize {
private:
    HRESULT m_hr;
public:
    CCoInitialize(PVOID pReserved, HRESULT &hr)
        : m_hr(E_UNEXPECTED) { hr = m_hr = CoInitialize(pReserved); }
    ~CCoInitialize() { if (SUCCEEDED(m_hr)) { CoUninitialize(); } }
};

// helper class to CoTaskMemFree
class CCoTaskMemFreeOnExit {
private:
    PVOID m_p;
public:
    CCoTaskMemFreeOnExit(PVOID p) : m_p(p) {}
    ~CCoTaskMemFreeOnExit() { CoTaskMemFree(m_p); }
};

// helper class to PropVariantClear
class CPropVariantClearOnExit {
private:
    PROPVARIANT *m_p;
public:
    CPropVariantClearOnExit(PROPVARIANT *p) : m_p(p) {}
    ~CPropVariantClearOnExit() { PropVariantClear(m_p); }
};

// find the default capture and render audio devices
// determine whether they are on the same audio hardware
int _tmain() {
    HRESULT hr = S_OK;

    // initialize COM
    CCoInitialize ci(NULL, hr);
    if (FAILED(hr)) {
        LOG(_T("CoInitialize failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    // get enumerator
    CComPtr<IMMDeviceEnumerator> pMMDeviceEnumerator;
    hr = pMMDeviceEnumerator.CoCreateInstance(__uuidof(MMDeviceEnumerator));
    if (FAILED(hr)) {
        LOG(_T("CoCreateInstance(IMMDeviceEnumerator) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    // get default render/capture endpoints
    CComPtr<IMMDevice> pRenderEndpoint;
    hr = pMMDeviceEnumerator->GetDefaultAudioEndpoint(eRender, eConsole, &pRenderEndpoint);
    if (FAILED(hr)) {
        LOG(_T("GetDefaultAudioEndpoint(eRender, eConsole) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    CComPtr<IMMDevice> pCaptureEndpoint;
    hr = pMMDeviceEnumerator->GetDefaultAudioEndpoint(eCapture, eConsole, &pCaptureEndpoint);
    if (FAILED(hr)) {
        LOG(_T("GetDefaultAudioEndpoint(eCapture, eConsole) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    // get endpoint device topologies
    CComPtr<IDeviceTopology> pRenderEndpointTopology;
    hr = pRenderEndpoint->Activate(__uuidof(IDeviceTopology), CLSCTX_ALL, NULL, (void**)&pRenderEndpointTopology);
    if (FAILED(hr)) {
        LOG(_T("Render endpoint Activate(IDeviceTopology) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    CComPtr<IDeviceTopology> pCaptureEndpointTopology;
    hr = pCaptureEndpoint->Activate(__uuidof(IDeviceTopology), CLSCTX_ALL, NULL, (void**)&pCaptureEndpointTopology);
    if (FAILED(hr)) {
        LOG(_T("Capture endpoint Activate(IDeviceTopology) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    // get KS filter device IDs
    LPWSTR szRenderFilterId;
    CComPtr<IConnector> pConnector;
    hr = pRenderEndpointTopology->GetConnector(0, &pConnector);
    if (FAILED(hr)) {
        LOG(_T("Render endpoint topology GetConnector(0) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    hr = pConnector->GetDeviceIdConnectedTo(&szRenderFilterId);
    if (FAILED(hr)) {
        LOG(_T("Render connector GetDeviceIdConnectedTo() failed: hr = 0x%08x"), hr);
        return __LINE__;
    }
    CCoTaskMemFreeOnExit freeRender(szRenderFilterId);
    LOG(_T("KS filter ID for render endpoint:\n\t%ls"), szRenderFilterId);

    LPWSTR szCaptureFilterId;
    pConnector = NULL;
    hr = pCaptureEndpointTopology->GetConnector(0, &pConnector);
    if (FAILED(hr)) {
        LOG(_T("Capture endpoint topology GetConnector(0) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    hr = pConnector->GetDeviceIdConnectedTo(&szCaptureFilterId);
    if (FAILED(hr)) {
        LOG(_T("Capture connector GetDeviceIdConnectedTo() failed: hr = 0x%08x"), hr);
        return __LINE__;
    }
    CCoTaskMemFreeOnExit freeCapture(szCaptureFilterId);
    LOG(_T("KS filter ID for capture endpoint:\n\t%ls"), szCaptureFilterId);

    // get IMMDevices for each associated devnode
    CComPtr<IMMDevice> pRenderDevnode;
    hr = pMMDeviceEnumerator->GetDevice(szRenderFilterId, &pRenderDevnode);
    if (FAILED(hr)) {
        LOG(_T("Getting render devnode via IMMDeviceEnumerator::GetDevice(\"%ls\") failed: hr = 0x%08x"), szRenderFilterId, hr);
        return __LINE__;
    }

    CComPtr<IMMDevice> pCaptureDevnode;
    hr = pMMDeviceEnumerator->GetDevice(szCaptureFilterId, &pCaptureDevnode);
    if (FAILED(hr)) {
        LOG(_T("Getting capture devnode via IMMDeviceEnumerator::GetDevice(\"%ls\") failed: hr = 0x%08x"), szCaptureFilterId, hr);
        return __LINE__;
    }
    LOG(_T(""));

    // open property set on each devnode
    CComPtr<IPropertyStore> pRenderDevnodePropertyStore;
    hr = pRenderDevnode->OpenPropertyStore(STGM_READ, &pRenderDevnodePropertyStore);
    if (FAILED(hr)) {
        LOG(_T("Getting render devnode property store failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    CComPtr<IPropertyStore> pCaptureDevnodePropertyStore;
    hr = pCaptureDevnode->OpenPropertyStore(STGM_READ, &pCaptureDevnodePropertyStore);
    if (FAILED(hr)) {
        LOG(_T("Getting capture devnode property store failed: hr = 0x%08x"), hr);
        return __LINE__;
    }

    // get PKEY_Device_InstanceId property
    PROPVARIANT varRenderInstanceId; PropVariantInit(&varRenderInstanceId);
    CPropVariantClearOnExit clearRender(&varRenderInstanceId);
    hr = pRenderDevnodePropertyStore->GetValue(PKEY_Device_InstanceId, &varRenderInstanceId);
    if (FAILED(hr)) {
        LOG(_T("Render devnode property store GetValue(PKEY_Device_InstanceId) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }
    if (VT_LPWSTR != varRenderInstanceId.vt) {
        LOG(_T("Render instance id variant type is %u - expected VT_LPWSTR"), varRenderInstanceId.vt);
        return __LINE__;
    }
    LOG(_T("Instance Id of default render device: %ls"), varRenderInstanceId.pwszVal);

    PROPVARIANT varCaptureInstanceId; PropVariantInit(&varCaptureInstanceId);
    CPropVariantClearOnExit clearCapture(&varCaptureInstanceId);
    hr = pCaptureDevnodePropertyStore->GetValue(PKEY_Device_InstanceId, &varCaptureInstanceId);
    if (FAILED(hr)) {
        LOG(_T("Capture devnode property store GetValue(PKEY_Device_InstanceId) failed: hr = 0x%08x"), hr);
        return __LINE__;
    }
    if (VT_LPWSTR != varCaptureInstanceId.vt) {
        LOG(_T("Capture instance id variant type is %u - expected VT_LPWSTR"), varCaptureInstanceId.vt);
        return __LINE__;
    }
    LOG(_T("Instance Id of default capture device: %ls"), varCaptureInstanceId.pwszVal);

    LOG(_T(""));

    // paydirt
    if (0 == _wcsicmp(varRenderInstanceId.pwszVal, varCaptureInstanceId.pwszVal)) {
        LOG(_T("Default render and capture audio endpoints ARE on the same hardware."));
    } else {
        LOG(_T("Default render and capture audio endpoints ARE NOT on the same hardware."));
    }

    return 0;
}
Matthew van Eerde's web log

Blown movie lines - Casablanca

Posted over 5 years ago

by Maurits [MSFT]
- 2 Comments
Ah... Casablanca.

Arguably the best movie of all time. And yet a blown line? How could I be so bold?

The line:

Play it [As Time Goes By] again, Sam. -- Casablanca

Wow... that line, blown? Am I way off base here? Arguably the best line of arguably the best movie... blown? How so?

Well, for two reasons.
1. The line does not actually appear in the movie at all.
  
  There are two scenes where Sam is urged to play As Time Goes By to recall the Paris romance between the two major characters. Here is the dialog from both scenes:
  
  Ilsa: Play it once, Sam. For old times' sake.
  Sam: I don't know what you mean, Miss Ilsa.
  Ilsa: Play it, Sam. Play "As Time Goes By."
  
  ... and later...
  
  Rick: You played it for her, you can play it for me!
  Sam: Well, I don't think I can remember...
  Rick: If she can stand it, I can! Play it!
  
  "Play it again, Sam" has thus entered the pantheon of unforgettable movie lines... even though it was never actually said.
2. The song was nearly changed.
  
  The film composer - a fellow named Max Steiner - did a very good job on the film. As Time Goes By is, thanks to his score, now indelibly etched in the ears of many a classic movie buff.
  
  But he hated the song! He attempted to convince the producers of the film that the song was boring, and that he could write a much better song.
  
  Shame, Mr. Steiner. Shame.
  
  What's worse... the producers went along with it! They agreed to allow him to write a song to replace As Time Goes By. There were only a couple of scenes that needed to be reshot, and they started the logistical machinery to recall the cast in those scenes to do the reshooting.
  
  Unfortunately... or rather, fortunately... Ingrid Bergman had already moved on to For Whom The Bell Tolls... and she had cut her hair...
The topic of this arguably-best-line of the arguably-best-movie was thus saved by a haircut.