Dmitry Brant – Page 26

My Conversation with God

I had a conversation with God last night. Really, I did! I was just re-reading through portions of Neale Donald Walsch‘s wildly popular Conversations with God series, and I couldn’t help but wonder how any self-respecting God, if one exists, would allow such lunacy to continue. And, wouldn’t you know it, God responded!

An uncommon dialogue

DB: Son of a bitch, this stuff is giving me a migraine…

God: Hello!!! This is… Gaaawwwwwwwwwwd.

DB: Holy crap, you do exist! Silly me, I thought you were a logical impossibility!

God: Oh, I am an impossibility. Of awesomeness!

DB: But how do I know it’s really you?

God: Well, I can’t really prove anything to you at this point. Maybe it’s really me, or maybe it’s a drug-induced hallucination. And the headcheese hoagie you ate for dinner can’t be helping, either.

God's image DB: You know–

God: I’m–

DB: Oh, sorry, go ahead.

God: No, no, you spoke first.

DB: I’ve actually had a few burning questions to ask you, now that you’re here. Do you mind?

God: Burning questions are better answered by Satan. Get it?!

DB: Wow… that is just awful.

God: I’m just joshin’ you. Go ahead and shoot away.

DB: You know who Neale Donald Walsch is, right? He has built a multi-million dollar empire from his “Conversations with God” books.

God: Yes, I’ve heard… such things.

DB: Well, was it really you speaking to him? Because, forgive me, but it sounds an awful lot like Walsch’s conversations are between himself and his gigantic ego, instead of a deity like yourself.

God: You’re absolutely right. I’ve never spoken to him in any way, not in print, writing, thoughts, or conversation. He is a dangerous cult leader, and I’m amazed that more and more people keep on feeding his ego trip. You can quote me on that.

DB: Oh, good, I’m glad I’m not the only one who thinks so. It will be interesting to see what my readers think of your opinion on this, o Lord. So, let me ask you this. How can I make a million dollars from this conversation that we’re having right now?

God: It’s simple! People are idiots. I created them that way, because I felt like it. All you have to do is sprinkle this conversation with some positive messages, appeal to their fantasies and desires, and subtly inject your own agenda at your leisure! Tell people that, by just reading this conversation, their lives will improve and become filled with happiness. Also, use words like “Eastern” and “alternative.” Then all you do is sell, sell, sell!!! Write books, have seminars, workshops, retreats, cruises, and charge as much as you want! They’ll pay, and beg for more! Make sure to nickel-and-dime at every turn, so they get used to paying whenever they hear your name. And of course, make sure to copyright everything you do, and insist that you’re the only one with the true message.

DB: Awesome! But what if people’s lives don’t improve from reading this conversation?

God: Tell them it’s their own damn fault. Use an excuse like “you create your own reality” or “you are your own god.” That will shut them up real quick, and give them some much-needed guilt, so they’ll buy even more stuff from you! If they still insist that their lives aren’t changing, wave your hands in the air and tell them that they haven’t “opened their mind” enough, and offer to clear their mind for an additional charge.

DB: Wow, it sounds so simple when you put it like that!

God: I know, right?! Oh, and one more thing. When selling this stuff, you really have to stand out, or no one will notice you. You have to be really flamboyant. I mean extremely flamboyant. Flail your arms around when speaking, and dance around on the stage. Change the emotion in your voice randomly from one sentence to another, just to throw them off.

DB: But what if people accuse me of being a fraud?

God: So what? Just tell them they can believe whatever they want! Maybe you spoke to God, maybe you didn’t! Here’s a good one to throw at them: “we’re all god!” I’m God, you’re God, this rock is God! Did you talk to a rock today? Boom, you talked with God, and I just blew your mind! Is that profound enough for you? How about them apples, Debbie Downer?

DB: Okay, let me give it a try real quick, and tell me if I’ve got it.

God: Alright, let’s see what you’ve got.

DB: [Clears throat] Umm…

Eastern religion… is… awesome. You people are… fantastic. Leading a healthy lifestyle is… great. Come to my workshops and, for $500, I will repeat these platitudes to you!

God: No, no, no, you have to do a lot better than that! First of all, you can’t just ask for money. What are you, a wimp? You have to demand money. You have to make them assume that they need to give you money to get anywhere!

DB: [loosens up] OK, let me try again…

We’re all connected! If you try hard, you can accomplish things in life! Don’t harm animals! America! Sex is good for you! Think about money and it will come to you! You must give me $1200, so that I can show you how to make $500!

God: Ehh… good, not great. Here, take an example from the master. Now watch what I do, and listen closely: I’m just going to speak naturally, and say whatever comes to mind… [Clears throat]

According to the scientifically proven Law of Attraction, which we all know is true, quantum reality can be manipulated by something as simple as your thoughts! Since your consciousness exists both in the physical and spiritual realm, according to scientists, you can consciously use quantum effects like entanglement and superposition, to literally change the world around you. Once you master this simple skill, which we’re all born with, you can attract prosperity, health, love, power, and anything else you want in your life.

At my upcoming workshop, for an introductory fee of $10000, I’ll teach you to channel your life-force energy through scientifically verified quantum field points on your body, allowing you to heal yourself and others, enjoy a better love life, create wealth, and finally be the master of your quantum world. Also, for an additional $200 per 10 minutes, I will hold an attunement session with you, where I will use my mastery of the quantum field to unblock your chakras, one at a time, and re-enable the flow of magneto-electric spiritual energy throughout your body!

…You see? Damn, I’m good! I didn’t even have to think about that! The bullshit just flows so naturally. It’s a gift, really, but you too can learn to talk like this, if you keep practicing.

DB: Wow, I am speechless. I threw up in my mouth a little, but that is just brilliant! God, you’re a genius. Let me just write this all down…

God's image God: Well, what did you expect, a retard for a god? Would a retarded god sacrifice himself to himself to atone for the sins of his own creations?

DB: Hmm… why don’t we save that question for a future conversation?

God: Absolutely! Feel free to contact me anytime. You know how to reach me!

DB: Actually, I’m not sure how I reached you. You just started talking to me.

God: Exactly! Cheerioooooo!…

DB: Wait, just one more thing! How can you, in good conscience, allow people like Walsch to continue to do what they do?

God: How am I supposed to do anything when I don’t exist? Jackass.

Money, please!

So there you have it, dear readers, straight from the horse’s mouth. Neale Donald Walsch never had a conversation with anything but his own giant head. I spoke with the real God, as you can plainly see above. So… give me money. Come on, cough it up.

This just in: You create your own reality!

When proponents of pseudoscience talk amongst each other, any doubts about the validity of their claims hardly ever arise. When two pseudoscientists have roughly the same beliefs, they will never question one another, and no attempt to verify their claims will be made. It’s assumed, as a given, that what they believe is real and true.

It’s only when pseudoscientists are confronted by skeptics that they try to cobble together actual pet theories of how their claims can be justified. These theories are usually ad hoc (as in, invented right on the spot), just to get the skeptic off the pseudoscientist’s back. There are, however, certain theories that seem to permeate the pseudoscientific community, and are used universally for all brands of quackery.

One of my favorites is the argument that each of us “creates our own reality.” And that’s not in the weak sense of “our life is what we make of it,” with which I completely agree. It’s in the strong sense that physical reality actually bends to our will in real time! This is reminiscent of the philosophy of solipsism, where all of reality is in the mind of the observer. The pseudoscientists, however, dress up the argument in the usual array of loosely-knit scientific terms hijacked from quantum mechanics, such as taking the idea of quantum entanglement to mean that “everything is connected,” among other nonsense.

To the untrained skeptic, this might seem like a powerful argument. And it is, in most cases, a debate-stopper. I mean, if we all create our own reality, then surely we can create whatever physical laws we like! Skeptics create realities of strict, unchanging physics and lead boring and unfulfilled lives, while pseudoscientists create realities where “anything is possible.” Or so the argument goes. This argument, however, is a debate-stopper for the wrong reason: not because it’s so airtight that it checkmates the skeptical opponent, but because it’s so devoid of meaning that no further discussion can logically continue.

Because of this, the “argument” serves as the foundation for the most weasely excuses for why a quack treatment won’t work on skeptics:

My treatment won’t work on you because you created a reality that stops it from working!
You have to want the treatment to work. You must open your mind to it.
Your skeptical presence in the room will stop the treatment from working.
The outcome of the test will be whatever you believe it should be. Your presence will skew the results in your favor.

Poverty of the argument

My contention is that the idea that “we create our own reality” is an empty philosophy, a cowardly withdrawal from reason. It’s intellectually lazy, and ultimately useless as a means of understanding our existence. Allow me to illustrate how I arrived at this with a series of observations and rhetorical questions.

If we create our own reality, then why don’t we have intimate knowledge of its innermost workings? For instance, why isn’t everyone endowed with instinctual knowledge of physics? And I don’t mean Newtonian physics, or even quantum physics, but the “true” physics that governs all the fundamental forces and encompasses what quantum mechanics and general relativity only approximate? If we are the architects of our world, surely we should know how it works!
On a related note, how is it possible that so many discoveries about our world have been totally counterintuitive, like the roundness of the Earth, heliocentricity, or the curvature of spacetime? If we are the ones who create our world, it would stand to reason that our intuition should naturally guide us towards understanding its nature. And yet, from the most profound breakthroughs in our history, we’ve observed the exact opposite.
Taking the above points a bit further, how can there be anything in the world that is “unknown” to me? That is, why am I not omniscient with respect to my reality, since it’s all my creation? For example, how can I be surprised when I taste a certain food for the first time? Why am I awed when I walk into a cathedral I’ve never visited before?
If I create my own reality, why are there people in the world who are better than me at various activities? For example, if I pick up and start reading Andrew Wiles’s proof of Fermat’s Last Theorem, there’s a good chance that I won’t understand a word of it. But why is that? If Andrew Wiles and his proof are products of my imagination, then why can’t I understand the proof that my imagination created?

Because you wanted to create a proof that you couldn’t understand.

No, I didn’t! Being a world-renowned mathematician was one of my earliest dreams. So why hasn’t that reality been realized?

Because you created a reality wherein you have to learn and grow in order to understand it.

If this is the case, then the whole argument becomes an easy candidate for Occam’s Razor. Why would I voluntarily limit my understanding of reality, and then spend my life attempting to rediscover this understanding, while never quite approaching the level of understanding I must have had in order to create reality in the first place?
If our understanding of reality is deliberately limited, then attempting to expand our understanding of it would ultimately require cautious use of the scientific method, which is precisely what we do in understanding the real world! It should be apparent that this argument eventually achieves a one-to-one correspondence with plain old realism, albeit in a roundabout way that has emotional appeal for those unwilling to face realism head on.
Why is the reality we create imperfect? This boils down to the Problem of Evil, which is ever so inconvenient for believers in omnipotent, benevolent gods. When someone uses the argument that “you create your own reality”, they’re essentially transferring the burden of the problem from God to “you,” since you now become the god of your reality.
So then why do I, as a god, create a reality that is not perfect? At what point did I decide to create a reality where I’m a common citizen who has to work for a living and deal with the everyday problems of middle-class life? When did I decide to give HIV to a quarter of the population in Africa? And when did I decide to create a vast number of people who delude themselves with imaginary realities and magical thinking, and kill each other over whose beliefs are holier? None of the above creations are things that I ever wanted. And yet they exist.
If we create our own reality, then why is reality so difficult to alter? Specifically, why doesn’t reality automatically bend to our will, like the pseudoscientists say it should? If the state of reality is guided by our deepest desires, why doesn’t reality rebuild itself according to what we want at any given time? It seems like the only way to make actual changes to our reality is by doing physical work, or paying someone to do it for us. It almost seems like we have no cognitive control over external elements in our reality!

I could go on, but the conclusion will remain the same. No matter how we approach this argument, like any other pseudoscience, it will eventually reduce to absurdity. So, please, next time you hear this nugget of pseudo-reasoning, recognize it for the intellectual poverty it represents, and challenge the speaker with a much-needed dose of skepticism.

Binomial Coefficients and Stirling Numbers in C#

As long as I’m on a roll with my posts on number theory in C#, I thought I’d briefly discuss how to generate binomial coefficients, and then move on to Stirling numbers of the second kind, both of which are extremely useful in combinatorics and finite calculus.

Some prerequisites for calculating binomial coefficients include a standard factorial function, nothing special:

long factorial(long n)
{
    if (n == 0) return 1;
    long t = n;
    while(n-- > 2) t *= n;
    return t;
}

Note that I use longs whenever possible because, despite the performance hit from 64-bit operations, it’s worth it to be able to work with numbers that are double the magnitude of ints.

We will also need a function for calculating a falling power of a number, which is defined as: $$x^{\underline{n}} = x(x-1)(x-2)\ldots(x-(n-1))$$You’ll see why in a moment.

long fallingPower(long n, long p)
{
    long t = 1;
    for (long i = 0; i < p; i++) t *= n--;
    return t;
}

Notice that the above function handles the case $$n^{\underline{0}}$$ returning 1. However, it does not handle the case of p > n, which would give an incorrect result, but this is not necessary for our purposes.

Binomial Coefficients

Recall that the definition for the binomial coefficient is $${n \choose k} = \frac{n!}{k!(n-k)!}$$ However, using this exact formula to compute binomial coefficients is a bit naive. If we use falling powers (sometimes called falling factorials), the above formula easily reduces to: $$\frac{n^{\underline{k}}}{k!}$$

We can improve the algorithm a bit more by adding the condition:

$${n \choose k} =
\begin{cases}
\frac{n^{\underline{k}}}{k!} \quad \mbox{if } k \leq \lfloor n/2 \rfloor,\\
\frac{n^{\underline{n-k}}}{(n-k)!} \quad \mbox{if } k > \lfloor n/2 \rfloor.
\end{cases}
$$

Not only is this algorithm faster, but it can also handle larger coefficients than the original formula, since neither the falling power nor the factorial ever gets larger than n/2.
The code for this is straightforward:

long binomialCoeff(long n, long k)
{
    if ((k < 0) || (k > n)) return 0;
    k = (k > n / 2) ? n - k : k;
    return fallingPower(n, k) / factorial(k);
}

However, this is still not as optimal as it can be. The most optimal approach would be to accumulate the falling power while dividing by each factor of the factorial in place. This would minimize the chance of overflow errors, and allow for even larger coefficients to be calculated. The disadvantage of this algorithm is the necessary use of floating-point math:

long binomialCoeff(long n, long k) {
    if ((k < 0) || (k > n)) return 0;
    k = (k > n / 2) ? n - k : k;
    double a = 1;
    for (long i = 1; i <= k; i++) a = (a * (n-k+i)) / i;
    return a + 0.5;
}

Stirling Numbers

Stirling numbers (of the second kind) are useful for, among other things, enumerating the coefficients of the falling-power expansion of a regular power. For example, how would we express x³ in terms of falling powers of x? That is, how do we arrive at an equation of the form $$x^3 = ax^{\underline 3} + bx^{\underline 2} + cx^{\underline 1}$$ Well, we could just solve the equation directly, but this would get unwieldy for higher powers. A neat way of doing this involves the use of Stirling numbers of the second kind, $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$$ A useful theorem for computing these numbers is

$$ \left\{\begin{matrix} n \\ k \end{matrix}\right\}=\frac{1}{k!} \sum_{i=0}^{k}(-1)^i{k \choose i}(k-i)^n $$$

long stirling(long n, long k)
{
    long sum = 0, neg = 1;
    for (long i = 0; i <= k; i++)
    {
        sum += neg * binomialCoeff(k, i) * pow(k - i, n);
        neg = -neg;
    }
    sum /= factorial(k);
    return sum;
}

With the Stirling numbers in hand, we can now obtain the coefficients for falling power expansions:

$$x^m = \sum_{k=0}^{m}\left\{\begin{matrix} m \\ k \end{matrix}\right\}x^{\underline k}$$

Project Euler — Problem 197

I never thought that solving random math problems can be addictive, but Project Euler does exactly that. Not only does it make you flex your math muscles, it also challenges you to take your programming language of choice to its limits. So it’s a total win-win: you brush up on your math skills, and broaden your programming repertoire at the same time.

Once I discovered Project Euler, I couldn’t pull myself away from the computer until I solved as many problems as I could. As of this writing I’ve solved 187 of their 211 problems.

Problem 197 has to do with finding the n^th term of a particular recursively defined sequence: $$u_{n+1} = f(u_n)$$ with $$u_0 = -1, f(x) = \lfloor 2^{30.403243784-x^2}\rfloor \cdot 10^{-9}$$

Of course, as with most Project Euler problems, the value for n is set ridiculously high, presumably to eliminate the possibility of brute-forcing the problem (within the lifetime of the universe).

Fortunately, it takes little more than a superficial examination to see that this problem is actually quite simple in disguise. If we look at the first few terms of the sequence, we can already guess that this sequence appears to be “converging” to a function that oscillates between two values, approximately 0.681 and 1.029 (I won’t give precise numbers, since that would give away the solution).

This means that all we need to do is go far enough into the sequence that the deviation of the oscillations is less than the desired precision asked by the problem (10^-9). And it so happens that we don’t need to go out far at all. The sequence actually settles on its two oscillatory values as early as the 1000^th term (probably even earlier)! Therefore, the sum of the 1000^th and 1001^st term will be equivalent to the sum of the 10^12th and (10¹²+1)^st term, which is what the problem asks for!

The code to do this is elementary. I accomplished it with a mere 5 lines of C# code. Can you do better?

Elementary Number Theory in C#

I thought I’d post a few code snippets in C# that have to do with basic number theory, since I use them in my programs from time to time. These snippets are by no means optimized, and the use of C# pretty much precludes their use in high-performance applications. Still, for relatively small arguments, these routines run surprisingly fast.

Prime numbers

To generate a list of prime numbers, we use the familiar Sieve of Eratosthenes. We can write one routine to generate the sieve:

bool[] GetPrimeSieve(long upTo)
{
    long sieveSize = upTo + 1;
    bool[] sieve = new bool[sieveSize];
    Array.Clear(sieve, 0, (int)sieveSize);
    sieve[0] = true;
    sieve[1] = true;
    long p, max = (long)Math.Sqrt(sieveSize) + 1;
    for (long i = 2; i <= max; i++)
    {
        if (sieve[i]) continue;
        p = i + i;
        while (p < sieveSize) { sieve[p] = true; p += i; }
    }
    return sieve;
}

The above function returns an array of booleans (the size of the given parameter), each of which is false if the array index is a prime number, or true if it's not a prime number. To get an actual list of prime numbers, we can use a function such as this:

long[] GetPrimesUpTo(long upTo)
{
    if (upTo < 2) return null;
    bool[] sieve = GetPrimeSieve(upTo);
    long[] primes = new long[upTo + 1];

    long index = 0;
    for (long i = 2; i <= upTo; i++) if (!sieve[i]) primes[index++] = i;

    Array.Resize(ref primes, (int)index);
    return primes;
}

The above function returns an actual list of primes less than or equal to the specified high limit. This means that we can easily compute the prime-counting function $$\pi(x)$$ for any integer x by counting the number of elements in the array returned by the function. We can write a similar function to generate a list of composites:

long[] GetCompositesUpTo(long upTo)
{
    if (upTo < 2) return null;
    bool[] sieve = GetPrimeSieve(upTo);
    long[] composites = new long[upTo + 1];

    long index = 0;
    for (long i = 2; i <= upTo; i++)
        if (sieve[i]) composites[index++] = i;

    Array.Resize(ref composites, (int)index);
    return composites;
}

As for determining if a single certain number is prime (without having to generate a giant sieve), we can simply use a function that attempts to factor the number. If the number happens to be divisible by an integer greater than 1 and less than or equal to its square root, then the number is not prime:

bool IsPrime(long n)
{
    long max = (long)Math.Sqrt(n);
    for (long i = 2; i <= max; i++)
        if (n % i == 0)
            return false;
    return true;
}

Greatest Common Divisor and Totient

To obtain the greatest common divisor (GCD) of two numbers, we use the usual Euclidean algorithm:

long gcd(long a, long b)
{
    long temp;
    while (b != 0)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

There is a slightly different binary algorithm for computing the GCD which is theoretically more efficient, but in practice (at least in C#) it's actually slightly less efficient than the algorithm above:

ulong gcdb(ulong a, ulong b)
{
    int shift;
    if (a == 0 || b == 0) return a | b;

    for (shift = 0; ((a | b) & 1) == 0; ++shift) { a >>= 1; b >>= 1; }
    while ((a & 1) == 0) a >>= 1;

    do {
        while ((b & 1) == 0) b >>= 1;

        if (a < b) {
            b -= a;
        } else {
            ulong temp = a - b;
            a = b;
            b = temp;
        }
        b >>= 1;
    } while (b != 0);
    return a << shift;
}

With the GCD readily available, determining whether two numbers are coprime is just a matter of telling whether or not their GCD is equal to 1. Also, calculating the LCM (least common multiple) of two numbers becomes trivial:

long lcm(long a, long b)
{
    long ret = 0, temp = gcd(a, b);
    if (temp != 0)
    {
        if (b > a) ret = (b / temp) * a;
        else ret = (a / temp) * b;
    }
    return ret;
}

Also using the GCD algorithm, it becomes easy to calculate Euler's totient function for a certain number, since the totient function is simply the number of integers less than or equal to n that are coprime to n:

long eulerTotient(long n)
{
    long sum = 0;
    for (long i = 1; i <= n; i++)
        if (gcd(i, n) == 1) sum++;
    return sum;
}

The above is a really naive algorithm. A much more efficient algorithm (one that is usually given in textbooks) is as follows:

int eulerTotient(int n)
{
    primes = GetPrimesUpTo(n+1);    //this can be precalculated beforehand
    int numPrimes = primes.Length;

    int totient = n;
    int currentNum = n, temp, p, prevP = 0;
    for (int i = 0; i < numPrimes; i++)
    {
        p = (int)primes[i];
        if (p > currentNum) break;
        temp = currentNum / p;
        if (temp * p == currentNum)
        {
            currentNum = temp;
            i--;
            if (prevP != p) { prevP = p; totient -= (totient / p); }
        }
    }
    return totient;
}