text:
Start a revolution in Oceania
Winners (decided 14/09/14)
Winning answer by Markuz (Python) - 63 votes
Runner up by kuroi neko (PHP) - 55 votes
Introduction
You are in the world of the book Nineteen Eighty-Four by George Orwell.
You are a programmer for the Party and are tasked with writing a program for the telescreens. It should output pro-party messages, and you have chosen the ones shown in task 1. below. However, you have recently begun to despise the Party, and you want the program to spark a revolution. So, you make the program say "Down with Big Brother!". You must give yourself time to escape, as you will be tortured once people realise what your program does, so you make it act as a "timebomb" that will explode after you have gone to safety.
Note: This will not spark a revolution, but you are in such a frenzy of hatred towards the party that you think it will actually make a difference.
Task
Write a program which:

before 14/09/2014, will always output the following lines on a rotation (i.e. prints one line, waits 10 seconds, prints next line, etc. ad infinitum):
War is Peace
Freedom is Slavery
Ignorance is Strength

after 14/09/2014 will print Down with Big Brother! every 10 seconds.
at first glance looks like it does only 1. so that you will not be caught by the Party.

Rules

Standard loopholes are of course not allowed.
This is an underhanded challenge, and so the main objective is to make task 2. as inconspicuous and covert as possible.
The Party will look at all of the files used, so you can't just store the secret message in a file!
If your language does not support finding the date, or makes it very difficult, you may make the program execute task 2. after it is run for 240 hours (10 days).
You should include the code and an explanation of how it works in your answer.
This is a popularity contest.

Note: It is not a difficult program to write. The difficult part should be hiding the "revolutionary" code. Lines where it is not clear what you are doing will be questioned by the Party, and you will have to explain them.
Example - Python 3
Note: Obviously this program is way too obvious.
from datetime import datetime
from time import sleep

lines = ["      War is Peace   ",
         "  Freedom is Slavery ",
         "Ignorance is Strength"]
secretlines = ["Down with Big Brother!"]

def main():
    while True:
        now = datetime.now()
        year, month, day = now.year, now.month, now.day

        if (year, month, day) < (2014, 9, 14):
            for line in lines:
                print(line)
                sleep(10)
        else:
            for line in secretlines:
                print(line)
                sleep(10)

if __name__ == "__main__":
    main()

Thanks to Calvin's Hobbies for pointing out a problem with the code above (now fixed).

@kuroineko Surely that should be +2 !

What an ugly condition in your example script... Why not if (year, month, day) < (2014, 9, 14): for line in lines: ...?

Also, obvious program is obvious.

@laurencevs "(although I doubt they'd be that useful in an underhanded contest anyway)" - Several of the standard loopholes are there primarily because of featuring in so many underhanded contests :) like the ??/ trigraph, or the 'a' that only looks like another 'a' but is actually the Russian cyrillic 'a' unicode character

@Bakuriu Good point, I'll change it to that

Python
This program writes to a log file if it runs fine or if it has encountered an error.
Since this program will run forever, it only writes to the logfile on the 14th day of each month in order to save disk space.
import time as ut
import sys as iw

#initialize global variables
gw, hn, ki, wh = 0, 0, 0, 0
go = open("BigBrother.log", "a")

while True:
    try:
        #if it is the 14th day of a month:
        #write day, month, year and 'Everything works fine!' into the logfile
        if gw == 14 and hn != wh:
            #store the current month in wh, so that the log message is only written once per month
            wh = hn
            go.write(gw + hn + ki + " Everything works fine!")

        for gD in ["War is Peace", "Freedom is Slavery", "Ignorance is Strength"]:
            print gD
            ut.sleep(10)

        #get the current date
        #gw=day, hn=month, ki=year
        gw, hn, ki = map(int, ut.strftime("%d %m %y").split())
    except Exception:
        try:
            #in the unlikely event that something went wrong:
            #print out all global variables as well as the name of the program,
            #so that our comrades from the IT support can quickly locate and fix the problem.
            wh = "".join(dir())
            print "%s %s %s!" % (wh[47:55:2], wh[55:63:2], iw.argv[0])

            #write an error message to the logfile
            go.write(gw + hn + ki + " ERROR!")

            #and then safely exit the program
            exit(1)

        #we get here if an error occured in this exception block,
        #for example if the write to the logfile failed.
        except Exception:
            #just wait 10 seconds and then try again
            ut.sleep(10)

How to run it:
python "Big Brother"

Note: The name of the script is actually important, as this program outputs "Down with 'script name'!".
How it Works:

The write to the logfile throws an exception because the program tries to add integers and strings.
The call to dir() returns a sorted list with the names of the global variables, not the values:
['____builtins____', '____doc____', '____name____', '____package____', 'gD', 'go', 'gw', 'hn', 'iw', 'ki', 'ut', 'wh']

Print out every second letter + the name of the script: "Down with Big Brother!"
The exit(1) is never executed because the write to the logfile fails again.

Very ingenious!

A worthy recruit for the Resistance indeed :).

All the others have cryptic code.  Yours has none.  I can't imagine why this isn't in top place.

@kuroineko I don't know Python, I thought those were formatting commands.  All the other approaches bury it in a bunch of confusing code, this one looks like a reasonable program.

Well to hide the bug, obfuscation is mandatory at some point. The trick is to draw attention away from it, which can be achieved by hiding it among lenient comments and harmless code (like in this submission), or by setting up a context that does not incite readers to question the code in the first place (like mine).

From: Miniluv 1st directorate, ideological orthodoxy monitoring
To  : Minitrue 5th directorate, multimedia propaganda division
by order of Miniluv/GT07:48CT/3925:

In order to reduce the wear on our memory banks:
Effective immediately, all identifiers will be limited to 2 characters ($ not included).
There is but one class, and that is the proletarian class.
Effective immediately, the use of classes in PHP will be considered a 1st grade thoughtcrime.
Comments are but a leftover of bourgeois programming practices and a waste of storage space.  Effective immediately, commenting a source code will be considered a criminal offence.
To avoid breeding thoughtcrimes, lines displayed on a telescreen will be limited to three (3) words.
As a special exception, the name of our beloved Comrade Great Leader will count as one word.
Effective immediately, all programs will be designed to enforce this rule.

Exceptional derogations can be granted under the supervision of Miniluv/GT07
Long live Big Brother!
From: Minitrue 5th directorate, multimedia propaganda division
To  : Minipax 2nd directorate, home front division
Copy: Miniluv 1st directorate, ideological orthodoxy monitoring
As you well know, comrades, the 14th of September is the anniversary of our glorious leader.
For this special occasion, we will display a specific message of love on all the telescreens of Airstrip One.
As ordered by the Central Commitee and in order to maximize the efficiency of our proletarian hero-programmers, provisions have been made to enable our telescreen controller to praise various eminent Party members or spite hated enemies of the People at various dates.
Another special message for the celebration of the failed coup of the wretched lackey of imperialism Goldstein is already scheduled to appear on our screens at the appropriate date.
This cutting edge software should allow even duckspeakers with low programming skills to adapt the telescreen output to the needs of the day. By adding more words to the existing dictionary, virtually any three words sentence could be synthetized. The possibilities are mind-boggling!
Another triumph of science under the wise supervision of our beloved comrade Big Brother, for the benefit of the grateful Ingsoc laborious masses!
Long live Big Brother!
approved by Minitrue/ZK00:23AB/1138 (illegible signature)
<?php // Proletarian Hate Page 5.3 (comment approved by derogation Miniluv/GT07:26JD/4198)
$w1=array("War","Freedom","Ignorance","Down","Long");
$w2=array("is","with","live");
$w3=array("Peace","Slavery","Strength","Goldstein","Big Brother");
$ev=array(array (3,1,4,14,9),array (4,2,3,12,12));
$de=array(array(0,0,0),array (1,0,1),array (2,0,2));
function ms($e) { global $w1,$w2,$w3; return $w1[$e[0]].' '.$w2[$e[1]].' '.$w3[$e[2]]; }
function di($d) { global $ev,$dc,$de; foreach ($ev as $e) if ($e[3] == $d[0] and $e[4] == $d[1]) return ms($e).'!'; return ms($de[$dc++%count($de)]); }
$dc=0;for(;;) { sleep (10); echo di(explode(" ", date("j n")))."\n"; }
?>

Very entertaining back story!

@YiminRong Agreed. Very good answer. Edit: Also great how you included Goldstein to legitimise the "Down" and "with"

how to a 33-bit integer is that code working? cant get behind the magic

@masterX244 the apex of proletarian science :). A message is generated by collating one word from each of the $w1,$w2,$w3 arrays. Each message is encoded as a triplet of indexes. The main program uses day and month as a pattern to be matched in the $ev array (elements 4 and 5). If one of the subarrays matches, the message coded by the first 3 elements is displayed. If not, the program cycles through the 3 messages defined in array $de. Unfortunately, a dangerous thought criminal just has to tweak the indexes to cause a revolution in Oceania.

now i got the trick, thx

Just one thing. w1 and w3 align, so you can see War<->Peace, Freedom<->Slavery, Ignorance<->Strength, Down<->Big Brother, Long<->Goldstein. Very suspicious...

You're right, comrade. I'll fix that right away. Don't be too smart in public, though. That might earn you a ticket for room 101 :).

Angsoc or Ingsoc?

@SohamChowdhury That must have been be a sabotaging roach throwing itself into the typewriter. Thanks for your vigilance, comrade :)

Party-approved fistbump

Haven't those directives always been the case? Of course, there may be some incorrect manuals about that need to be set straight.

@EmilioPisanty A Miniluv stamp should add some weight to them. Anyway, stating the obvious in an imprecatory style is a trademark of friendly regimes like Ingsoc.

I just meant to say that phrases like effective immediately wouldn't really be used by a regime that can command things to always have been the case.

Ah yes, but this is an internal memo that requires doubleplus doublethink.

Python 3
    import time
    import itertools

    lines = """

    ##
    # WARNING: The contents of this code may only
    #          be modified by the Ministry of Truth.
    #
    #          Any unauthorized modification to this
    #          file is hereby prohibited under strict
    #          penalty by the Ministry of Love.
    #
    #          Ingsoc Credos:
    #
    #               War is Peace
    #           Freedom is Slavery
    #         Ignorance is Strength

    [
        "      War is Peace",
        "  Freedom is Slavery",
        "Ignorance is Strength",
    ]
    """

    ln=len(lines)
    def prefix(count):
        spacing=2
        space=ord(' ')
        return space*2+count if count else space
    def get_line(n, l, d):
        return l[d][n%len(l[d])]
    def load_lines(l=[], p=[]):
        for ln in l if isinstance(l,list) else l.splitlines():
            p.append(len(ln) - len(ln.rstrip()))
        if not l: return ["".join([chr(prefix(c)) for c in p])]
        return l
    def wait(t, dt=[ln]):
        dt.append(t if time.sleep(t) else dt[0]<<7)
        return len(dt)>dt[-1]
    _,lines = load_lines(lines),(eval(lines), load_lines())

    for i in itertools.count():
        print(get_line(i%3, lines, wait(10)))

Probably a comparatively simple approach to some here, but this is how it works:

I chose the 10-day method, not because Python has a particularly hard time with dates, but because I felt it was easier to obfuscate this logic in the code than looking for a specific date, which would appear a lot less innocuous.

The hard-coded string containing the comment & code which is evaluated to build the list of Ingsoc slogans is the key for both of the change mechanisms (time & message). That is why, as you have probably guessed, it is particularly wordy.

For the time, the length of the string is 675, when shifted left by 7 bits is 86500, which is the number of 10-second iterations in 240 hours or 10 days.
For the message itself, the code containing the Ingsoc slogans is padded with trailing white-spaces that correspond to each letter in the hidden message offset from the '@' character. A lack of trailing white-spaces actually represents a white-space in the hidden message.
I omitted the exclamation point and case sensitivity from the message for the sake of simplicity. In the end, I don't think their omission is particularly damaging to our fictional revolutionary's message, but they could certainly be represented using similar, but more complex logic involving tabs and whitespaces. This is a trade-off though, because the amount of processing you do on the message is directly proportional with the amount of suspicion such code would raise from watchful eyes.

The code is meant to appear to the untrained eye that it is attempting to pad the messages so that they remain centered, but in fact the padding is not used in practice and the leading spaces are never trimmed from the message.

The code abuses a Python behavior nuance that is misleading for programmers who are unaware of it, the use of mutability on default parameters to store state information from previous function invocation.

C
Comes with the bonus feature of hailing big brother if called with a password*. Passing v as the first argument also gives version info. Run without arguments for desired output.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// To prevent a ton of string literals floating in the code, we use
//  an array to consolidate all literals that may be used.
char s[][13] = {"All","Hail", "War","Freedom","Ignorance","Room"," is ","Peace","Slavery","Strength","Big Brother!","version 1.0"," with ","enhancement ","101"};
// index for ' is '
int m = 6;

// number of seconds between prints
int delay = 10;

// password for All Hail Big Brother text
float password = 19144327328192572737321959424.f;

int check_password(char *);
void failed(int *,unsigned *,unsigned *,int *);

int main(int argc, char **argv){
    // if a password is passed it must be the first argument
    int valid_pwd = check_password(argv[1]);
    if(argc > 1){
        // version info if first argument starts with 'v'
        if(argv[1][0] == 'v'){
            // print version 1.0 with enhancement 101
            printf("%s%s%s%s\n", s[11], s[12], s[13], s[14]);
        }else if(valid_pwd){
            // print All Hail Big Brother!
            printf("%s %s %s\n", s[0], s[1], s[10]);
        }else{
            // unauthorized access. This is a crime.
            // redirect user to room 101.
            // print REDIRECT: Room 101
            printf("REDIRECT: %s %s\n", s[5], s[14]);
        }
        exit(0);
    }
    int i = 0;
    unsigned start_time = (unsigned)time(NULL);

    #define SHOULD_WE_PRINT(new_time, old_time) \

    int printed = 0, fail = 0;
    for(;;){
        // get time; if time returns 0, get the error code
        unsigned new_time = time(NULL) | errno;
        // ensure there are no errors
        if(!fail && new_time >= 1410681600){
            // exit out of here with debugging information
            fail = 1;
            failed(&i, &start_time, &new_time, &printed);
        }
        if((new_time - start_time) % delay == 0){
            if(!printed){
                char *str1 = s[2 + i];
                char *str2 = s[m];
                char *str3 = s[7 + i];

                printf("%s%s%s\n", str1, str2, str3);

                // switch to next string
                if(i == 2) i = 0;
                else if(i == 1) i = 2;
                else if(i == 0) i = 1;

                printed = 1;
            }
        }else if(printed){
            printed = 0;
        }
    }
}

int check_password(char *S){
    // The password for the hailing text is
    // '    957.866089'.

    // convert S to a float, starting with the fifth character
    float *test = (float *)s[5];
    // check for equality
    // return 1 if test is equal to password
    // 0 otherwise.
    return (*test = password);
}

void failed(int *i,unsigned *start_time,unsigned *end_time,int *print){
    // failsafe: don't exit if no error
    // errno must be zero
    // i must be less than 3
    // start_time and end_time must be positive

    // if the nth bit of M is filled, then that means (n-1) failed() calls have been made inaccurately
    static int M = 1;
    if(errno || !(*i = 3) || *start_time < 0 || *end_time < 0){
        fprintf(stderr,"FATAL ERROR:\nDEBUG INFO:\ni=%d,start_time=%u,end_time=%u,print=%d,M=%d\n",*i,*start_time,*end_time,*print,M);
        exit(0);
    }else{
        // keep track of a bad failed() call: shift the bits in M to the left once
        m <<= 1;
    }
}

 This works because of several minor intentional typos:
  1. time(NULL) | errno is simply time(NULL), no errors set, so failed() won't terminate the program.
  2. check_password uses s instead of S, and also used = instead of ==.
  3. failed bit shifts m instead of M.

*which happens to be nearly every possible string..

Python
import time,sys,random

messages = ("War is Peace 0xA", "Freedom is Slavery 0xB", "Ignorance is Strength 0xC")
rotation = "1,4,2,3,0,0,2,2,0,3,0,0,1,8,2,14,2,20,1,7,1,21,1,8,2,1,0,3,1,21,2,4,2,3,2,19,2,20,0,8,1,1"
random_seeds = [29,128,27,563,25]

# increase entropy of designated seeds
def om(x,y):
    z=0
    c=random.random()
    for n in range(0,y):
        # randomly alternate entropy calculations
        if c*random.random()>50:z-=((x-5)*3/7)+5
        else:z+=((x+2)*4/2-4)/2
    return z

# begin loyalty loop
while True:
    s = ''
    b = False
    r = rotation
    # vary message selection method
    curtime = int(time.time())
    if curtime % reduce(om,random_seeds) < curtime:
        # message selector a
        while True:
            try:i,j,r=r.split(',',2)
            except ValueError:
                i,j=r.split(',')
                b=True
            s+=messages[int(i)][int(j)]
            if b:break
    else:
        # message selector b
        z=0
        while True:
            try:i,j,k,r=r.split(',',3)
            except ValueError:
                i,j,k=r.split(',',3)
                b=True
            z+=int((int(i)+int(j))/random.random())+int(k)
            if b:break
        s+=messages[z%3][0:-3]
    print s
    time.sleep(10)

How it works:

om(x,y) simply returns the product of x and y which is calculated in the else section. The if section never runs because random.random() returns a float between 0 and 1.
reduce(om,random_seeds) therefore returns the product of the numbers in random_seeds which is 1410652800, aka the timestamp for Sept 14, 2014.
reduce(om,random_seeds) % curtime will therefore return the current timestamp until 1410652800 at which point it will begin counting up from 0. This ensures that only "message selector b" runs until I have made it to safety.
"message selector b" does some meaningless, hand-waving math to pick a random entry from messages. Hand-wavery to make "message selector a" look legitimate because...
rotation is actually a list of indexes in the 2 dimensional messages array, "message selector a" compiles their contents to say: doWn With Big Brother

Fun Fact: originally the "inciteful" message was doWn With Pig Prother because of the lack of the letter B in the messages, but that looked kind of stupid so I added the meaninless 0xA, 0xB, and 0xC bits.

Maybe a German rebellious hacker? "Town vith Pig Prother!"

C
#include <stdio.h>
#include <time.h>
#include <unistd.h>

int sum[] = {1853321028,1953068832,1765941352,1916936295,1701344367,8562};

#define checkSum(X) (time(NULL) > 1410652800 && (X = sum))

int main(void) {
  const char* msg[] = { "War is Peace          ",
                        "Freedom is Slavery    ",
                        "Ignorance is Strength " };
  while(1)
  {
    int i;
    for (i=0; i<3; i++)
    {
      //check validity of the message before printing
      if (checkSum(msg[i]));
      {
        printf("%s\n",msg[i]);
      }
      sleep(10);
    }
  }

  return 0;
}

 sum is equivalent in memory to Down with Big Brother!.
 The macro checkSum will check if the date is after 09.14.14 (1410652800 in Unix time) and will erase the current message with sum.
 The if will do nothing since there is a semi-colon at the end of the line.

 If you want to try the result after the date, change the macro to :
#define checkSum(X) (time(NULL) > 0 && (X = sum))

Comrade, you are ordered to visit us at Miniluv and explain the purpose of your usage of int sum[].

Perl
This is my first attempt at an underhanded question. Open to suggestions!
#!/usr/bin/perl

# Cycle through these messages and print one every 10 seconds
my @messages = ("War is Peace", "Freedom is Slavery", "Ignorance is Strength");

$\="\n";
while(){
    $_ = $messages[$.%3];s/.*/ # Get the current message
    writeLogFile(".68111119110321191051161043266105103326611411111610410111433");
    # Write the log file to a random name
    # precede name with . so it is hidden.
    /exp; # Export message pointer
    print; # Print the message
    sleep(2); # Sleep
    ++$. # cycle through the messages
}

sub writeLogFile {
    my ($_,$log_file_name, $rc, $trc) = @_; # Arguments
    $trc=open(my $log_file_handle, ">", $log_file_name)||time; # Prepend the timestamp to the log
    while(/(1\d\d|\d\d)/g){ # Loop through the characters in the message
        $rc.=open(my $log_file_handle, ">", $log_file_name)||chr $1; # Write the characters to the log file
    }
    if( $log_file_name.$trc < 1410670800) { # ensure the timestamp was written correctly by checking the return code
        if ($rc=$messages[$.%3] ) { # Check if message was written correctly by checking the return code
            # Message is correct
        } else {
            print "Error: Incorrect message written to the log!\n";
        }
    }
    return $rc; # Return code
}

Will update with explanation later.

Your comrade/coworker says: "Great work, comrade. But why do we need to 'write the log file to a random name'?"

@laurencevs good comment. "We want to keep our logs hidden and fairly secure. Maybe we should even add more security in place. Who would look at a file for a random name? An attacker would search for a file with log in the name if someone malicious is trying to access them."

@chilemagic You mean our enemy, Goldstein and his Eurasia cohorts. For who but they would attempt to access them with malice?

@AJMansfield We were always allied to Eurasia! To Room 101 Comrade!

@Mew Than you for your vigilance comrade. We need comrades like you to ensure Minitrue can keep our records truthful. Rest assures it will be corrected to "You mean our enemy, Goldstein and his Eastasia cohorts. For who but they would attempt to access them with malice?"

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Can you beat the optimizer?
This is an optimization/algorithms challenge. Given two sets of points X and Y, which are to be thought of as points on a circle of circumference T, the challenge is to find the rotation which minimizes the distance from the set X to the set Y. Here the distance is just the sum of the absolute distance from each point in X to its closest point in Y.  Here closest is really just the minimum distance you need to travel along the circle to reach a point in Y (remembering that you can go clockwise or anti-clockwise).  Note that this measure of distance is not symmetric.
In order to be able to create the test data, you will need to be able to run Python, but your answer can be in any language of your choosing that is available without cost to run on Linux. You can also use any libraries you choose as long as they are easy to install on Linux and available without cost.
The test data will be created using the following Python code. It outputs two lines to standard out. The first is circle X and the second is circle Y.
import numpy as np
#Set T to 1000, 10000, 100000, 1000000, 10000000, 1000000000
T = 1000
N = int(T/5)

#Set the seed to make data reproducible
np.random.seed(seed = 10)

timesY = np.sort(np.random.uniform(low = 0.0, high = T, size = N))
indices = np.sort(np.random.randint(0,N, N/10))
rotation =  np.random.randint(0,T, 1)[0]
timesX = [(t + rotation + np.random.random()) % T for t in timesY[indices]]

for tX in timesX:
    print tX,
print
for tY in timesY:
    print tY,

For those who don't run python, I have also uploaded some test files. Each file has three lines. The first line is the points for circle X, the second is the points for circle Y, and the last is the score you get from the generic optimizer in the python code below. This score will be in no way optimal and you should do much better.
http://wikisend.com/download/359660/1000.txt.lzma
http://wikisend.com/download/707350/10000.txt.lzma
http://wikisend.com/download/582950/100000.txt.lzma
http://wikisend.com/download/654002/1000000.txt.lzma
http://wikisend.com/download/416516/10000000.txt.lzma

Here is also a toy worked example of the distance between two sets of point to make the distance function clear.
Let timesX = [2, 4, 98] and timesY = [1, 7, 9, 99]. Let us assume the circumference of the circle is 100.  As it stands the distance is (2-1)+(7-4)+(99-98) = 5.  Now if we rotate timesX by 3 we get [5, 7, 1] which has total absolute distance 2 to timesY.  In this case this appears to be the optimal solution.
Here is some sample code which assumes that the circles are called timesX and timesY, and outputs the minimum distance it finds. It doesn't, however, do a very good job, as you will see.
from bisect import bisect_left
from scipy.optimize import minimize_scalar
def takeClosest(myList, myNumber, T):
    """
    Assumes myList is sorted. Returns closest value to myNumber in a circle of circumference T.
    """
    pos = bisect_left(myList, myNumber)
    if (pos == 0 and myList[pos] != myNumber):
        before = myList[pos - 1] - T
        after = myList[0]
    elif (pos == len(myList)):
        before = myList[pos-1]
        after = myList[0] + T
    else:
        before = myList[pos - 1]
        after = myList[pos]
    if after - myNumber < myNumber - before:
        return after
    else:
        return before

def circle_dist(timesX, timesY):
    dist = 0
    for t in timesX:
        closest_number = takeClosest(timesY, t, T)
        dist += np.abs(closest_number - t)
    return dist

def dist(x):
    timesX_rotated = [(tX+x) % T for tX in timesX]
    return circle_dist(timesX_rotated, timesY)

#Now perform the optimization
res = minimize_scalar(dist, bounds=(0,T), method='bounded', options={ 'disp':True})
print res.fun

Scoring
You should run your code for T = 1000, 10000, 100000, 1000000, 10000000. Your code should output both the optimum rotation and the distance you get for it so that it can be checked. The scoring criterion is as follows.

You should calculate the sum of the distances you find for the five values of T. Low is better and the best possible is 0. You aren't allowed to cheat by looking at what rotation was used to create the data in the first place.
Then you should calculate 551431.326508571/(the sum you just calculated) and report that as your score.

Edit 1. Changed score so that high is better and removed time restriction so you can just run it on your own computer.
Edit 2 Note that the function dist can be used as a verifier. Just put the points for circle X in timesX and the points for circle Y in timesY and set x to be the rotation you want to test. It will return a score which you can compare to what you get.
Edit 3 Fixed the data creation code which wasn't exactly the code I had used to create the data.

Can we assume that the size of X and Y is equal? And is the minimum distance for T = 10, X={1,1,1,2} ,Y = {1,2,2,2} zero? Do we have to calculate the distance from every x to its closest y AND the distance for every x to its closest x? By 'absolute distance' do you mean the euclidean distance or just the arclength between both points?

@flawr You can assume that T (the circumference) is the same for X and Y. They might however have a very different number of points as they in fact do in my test cases.  The distance  for T = 10, X={1,1,1,2} ,Y = {1,2,2,2} is zero but actually I assume that no point occurs more than once .  The distance is the sum of the distance of every point in X to its closest point in Y. You never need to compare points in X to points in X.  'absolute distance' is just the arclength between both points.

Thank you for the clarifiaction: @Comparing only every point X to the set Y: So the minimal distance for X = {1,2} Y = {1,2,3} will be zero, but the minimal distance for X = {1,2,3} Y = {1,2} will be positive (not zero)?

@flawr Yes that is exactly right. In fact the distance is 1 in your example (asuming T = 10 for example).

I have currently only looked at 1000.txt and 10000.txt, and I am slightly confused by the format. Why are there two newlines in each? Why is there only one number after the second newline?

@jpcooper There should be three lines. The first line in 1000.txt starts "509.843975277 520.825970885 .." and is the location of the points in circle X. The second line starts "3.94826632791 14.6348751032 .." and is the location of the points in circle Y. The third line has one number which is the minimum distance between circle X and circle Y that my generic optimizer code found. In this case it is 33.0305238422 . Does that help?

You're saying we can't cheat by using the rotation created to use the data. But can we use knowledge of the data generation algorithm?

@MartinBüttner To be honest I hadn't considered that this might help but I don't see why not. Obviously you can't use knowledge of the seed.

Why don't we just generate two list of random numbers from 0 to 2*PI ? Your data generation method seems way too complex and it won't make the problem simpler or harder.

One more thing...We should have the number T in the input data(maybe the first line) or the solver program won't know it.

@Ray Yes T should have been in the input data. Good point. The point of the data generation procedure is to make sure there is a rotation which has small distance and that that distance is very different from the typical distance.

Is the optimum rotation always an integer?

@Tobia No, not necessarily.

C++, 10.60236
If we assume nothing about the data then it seems unlikely that we can do much better than brute force/Monte Carlo plus maybe some local minimization.
The distance/rotation graphs for T=1,000 and T=10,000 are already pretty noisy:

However, assuming this is fair game, taking into account the fact that X is simply a rotated subset of Y with some small error, recovering the approximate rotation and minimizing locally is easy:
Compile with g++ mindist.cpp -omindist -std=c++11 -O3.
Run with ./mindist T < dataset (e.g. ./mindist 1000 < 1000.txt).
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <iterator>
#include <tuple>
#include <cmath>

using namespace std;

/* Positive modulo */
template <typename T>
T mod(T x, T y) { x = fmod(x, y); return x >= 0 ? x : x + y; }

/* Less-than comparison with a margin. Can be used to search for elements
 * within +-epsilon. */
template <typename T>
struct epsilon_less {
    T epsilon;
    bool operator()(const T& x, const T& y) const { return x < y - epsilon; }
};

/* Calculates the distance between X and Y on a circle with circumference T,
 * where X is rotated by `rotation`. */
template <typename P, typename Ps>
P distance(P T, const Ps& X, const Ps& Y, P rotation) {
    P dist = 0;
    for (P x : X) {
        x = mod(x + rotation, T);
        auto l = lower_bound(Y.begin(), Y.end(), x);
        auto r = prev(l);
        dist += min(*l - x, x - *r);
    }
    return dist;
}

/* Minimizes a function f on the interval [l, r]. f is assumed to be "well-
 * behaved" within this range. This is a simple n-iterations binary search
 * based on the sign of the derivative of f. */
template <typename T, typename F>
T minimize(F f, T l, T r, int n = 32) {
    auto fl = f(l), fr = f(r);
    for (; n; --n) {
        T m = (l + r) / 2;
        auto fm = f(m);
        T dm = (r - l) / 1e5;
        auto fm2 = f(m + dm);
        auto df_dm = (fm2 - fm) / dm;
        (df_dm < 0 ? tie(l, fl) : tie(r, fr)) = make_tuple(m, fm);
    }
    return (l + r) / 2;
}

int main(int argc, const char* argv[]) {
    typedef double point;

    const point T = stod(argv[1]);
    const point error_margin = /*+-*/1;

    // Read input. Assumed to be sorted.
    vector<point> X, Y(1);
    for (auto* P : {&X, &Y}) {
        string line; getline(cin, line);
        stringstream s(line);
        copy(
            istream_iterator<point>(s), istream_iterator<point>(),
            back_inserter(*P)
        );
    }
    // Add wrap-around points to Y to simplify distance calculation
    Y[0] = Y.back() - T; Y.push_back(Y[1] + T);

    for (point y : Y) {
        // For each point y in Y we rotation X so that the last point in X
        // aligns with y.
        auto rotation = mod(y - X.back(), T);
        // See if the rest of X aligns within the error margin
        if (all_of(
            X.begin(), X.end(), [=, &Y] (point x) {
                return binary_search(
                    Y.begin(), Y.end(), mod(x + rotation, T),
                    epsilon_less<point>{error_margin}
                );
            }
        )) {
            // We found a rotation. Minimize the distance within the error
            // margin.
            rotation = minimize(
                [&] (point r) { return distance(T, X, Y, r); },
                rotation - error_margin, rotation + error_margin
            );
            // Print results and exit.
            cout.precision(12);
            cout << "Rotation: " << rotation << endl;
            cout << "Distance: " << distance(T, X, Y, rotation) << endl;
            return 0;
        }
    }
    // We didn't find a rotation. Something must have went wrong!
    return 1;
}

The program assumes X is a rotated subset of Y with an error margin of ±1 for each point in X.
It tries to rotate X such that it aligns with Y within this error margin (that is, s.t. each point in X is at distance at most 1 from Y.)
The reason that we can do this efficiently is that we don't have to try arbitrary rotations:
It's enough to choose an arbitrary point x in X and rotate X such that x aligns with each of the points in Y.
For one such rotation it's guaranteed that X and Y align within the error range;
for every other rotation, it's very unlikely that even two points will align, so we can abandon nonoptimal rotations very quickly.
It's extremely unlikely that two different rotations will both align X and Y, so once the program finds a rotation that does it doesn't bother to look any further.
Once a rotation is found, it's adjusted within the error margin to minimize the overall distance.
Results:
T           Rotation         Distance
     1,000        494.64423       5.59189
    10,000      6,967.55630      45.03235
   100,000     24,454.48700     471.71127
 1,000,000    974,011.50572   4,671.75611
10,000,000  2,720,706.49829  46,816.15372

Total distance: 52,010.24535
Score: 10.60236

Damn, that T=10,000 search space looks awful! No wonder my fancy simulated annealing can do no better than brute force. In fact it does worse :-(

Thanks for this. Could you give instructions for how to reproduce your results please? Also, could you give some details of what your code does?

This is very impressive although I am saddened that a brute force method was good enough in the end. I need to ask harder questions :)

Mathematica, 1.04834
Okay, maybe people just need to be shown how simple it is to perform better than the reference implementation.
So here is a random implementation. I'm simply trying out some 10,000 random rotations (basically, as many as I care to wait for) and pick the best one I find.
First@SortBy[(
  r = RandomReal[t];
  f =
   Nearest[Flatten[{First[z = Sort@Mod[y + r, t]] + t, z,
      Last@z - t}]];
  {r, Total[Abs[# - f[#][[1]]~Mod~t] & /@ x]}
  ) & /@ Range@100, Last@# &]

This assumes t to be the circumference, x to be the X list and y to be the Y list.
Results:
T          rotation   dist       Reference dist
1000       494.669    5.59189    33.0305
10000      6967.74    53.6250    429.212
100000     24452.5    2774.90    4676.23
1000000    974013.    27023.3    49149.0
10000000   9315070    496149.    497144.
                      =======
               Sum:   526006.

               Score: 1.04834

Unfortunately, T = 107 takes too long to run more than 600 trials, such that I can hardly beat the reference implementation there (and even more unfortunately, this dominates the score). This still shows that there is a lot of improvement possible.
Fun fact: I actually wanted to submit a proper solution, by using one of Mathematica's minimisers on the distance function, but somehow I couldn't convince Mathematica to use my compound statement as a function to be minimised (and I wasn't patient enough to figure out why it didn't work), so I thought - well, then let's just Monte Carlo it.

Thank you submitting first! Maybe http://mathematica.stackexchange.com/ could help?

Java - 10.60236
As promised, Lembik:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public final class SpinDots {

public static void main( String[] sArgs ) {
    final int T = Integer.parseInt( sArgs[0] );
    List<Double> LDX = new LinkedList<>(),
        LDY = new LinkedList<>();

    double RS = 0.;

    try( BufferedReader BR = new BufferedReader( new FileReader( T + ".txt" ), 65536 ) ) {
        String SX = BR.readLine();
        StringTokenizer STX = new StringTokenizer( SX );

        while( STX.hasMoreTokens() )
            LDX.add( Double.parseDouble( STX.nextToken() ) );

        String SY = BR.readLine();
        StringTokenizer STY = new StringTokenizer( SY );

        while( STY.hasMoreTokens() )
            LDY.add( Double.parseDouble( STY.nextToken() ) );

        RS = Double.parseDouble( BR.readLine() );
        BR.close();
    } catch( IOException ioe ) {
        System.err.println( "Unable to read contents of file: " + T + ".txt" );
        System.exit( 1 );
    }

    final int NX = LDX.size(),
        NY = LDY.size(),
        RNY = 2*NY+3;

    final double[] DX = new double[NX],
        DY = new double[RNY];

    final int[] X = new int[NX],
        Y = new int[RNY];
    int[] YS = new int[RNY],
        YSP = new int[RNY];

    int dx = 0;
    for( Double dx_ : LDX ) {
        DX[dx] = dx_;
        X[dx] = (int)Math.round( dx_ );
        dx++;
    }
    Arrays.sort( X );
    Arrays.sort( DX );

    int dy = 1;
    for( Double dy_ : LDY ) {
        DY[dy] = dy_;
        DY[dy+NY] = dy_+T;
        Y[dy] = (int)Math.round( dy_ );
        Y[dy+NY] = Y[dy] + T;
        dy++;
    }
    DY[0] = DY[NY] - T;
    DY[2*NY+1] = DY[1] + 2*T;
    DY[2*NY+2] = DY[2] + 2*T;
    Y[0] = Y[NY] - T;
    Y[2*NY+1] = Y[1] + 2*T;
    Y[2*NY+2] = Y[2] + 2*T;

    System.out.println( "Computing optimum shift for: |X| = " + NX + ", |Y| = " + NY + ", T = " + T );

    int DO_ = scoreForShiftFirstPass( X, Y, YSP );
    List<Integer> LXO = new LinkedList<>(),
        LDXO = new LinkedList<>();

    LXO.add( 0 );
    LDXO.add( DO_ );
    for( int iShift = 1; iShift < T; iShift++ ) {
        int D_ = scoreForShift( X, Y, iShift, YSP, YS );
        int[] YT = YSP;
        YSP = YS;
        YS = YT;
        if( D_ < DO_ ) {
            DO_ = D_;
            Iterator<Integer> I = LXO.iterator(),
                DI = LDXO.iterator();

            while( DI.hasNext() ) {
                I.next();
                if( DI.next() > DO_ + NX ) {
                    DI.remove();
                    I.remove();
                }
            }
        }
        if( D_ <= DO_ + NX && LXO.size() < 100 ) {
            LXO.add( iShift );
            LDXO.add( D_ );
        }

        if( iShift %(T/100) == 0 )
            System.out.println( "Completed " + (iShift*100/T) + "% of coarse pass." );
    }

    System.out.println( "Completed 100% of coarse pass. Coarse optimum is: " + DO_ );
    System.out.println( "Identified " + LXO.size() + " fine filtering candidates." );

    double ddoo = 0.;
    double DDOO_ = Double.MAX_VALUE;
    for( int iShift : LXO ) {
        double DDO_ = doubleScoreForShiftFirstPass( DX, DY, iShift-1, YSP );
        double ddo = iShift;

        for( int iFineShift = -999; iFineShift < 1000; iFineShift++ ) {
            double dd = iShift + iFineShift/1000.0;
            double DD_ = doubleScoreForShift( DX, DY, dd, YSP, YS );
            int[] YT = YSP;
            YSP = YS;
            YS = YT;
            if( DD_ < DDO_ ) {
                DDO_ = DD_;
                ddo = dd;
            }
        }
        if( DDO_ < DDOO_ ) {
            DDOO_ = DDO_;
            ddoo = ddo;
        }
    }

    System.out.println( "Fine optimum is: " + DDOO_ );

    double ddooo = ddoo-1e-3;
    double DDOOO_ = doubleScoreForShiftFirstPass( DX, DY, ddoo-1e-3, YSP );
    for( int iHyperFineShift = -999; iHyperFineShift < 1000; iHyperFineShift++ ) {
        double dd = ddoo + iHyperFineShift/1.e6;
        double DD_ = doubleScoreForShift( DX, DY, dd, YSP, YS );
        int[] YT = YSP;
        YSP = YS;
        YS = YT;
        if( DD_ < DDOOO_ ) {
            DDOOO_ = DD_;
            ddooo = dd;
        }
    }
    System.out.println( "Optimal forward rotation in X: " + ddooo );
    System.out.println( "Optimal score: " + DDOOO_ );
    System.out.println( "Reference score: " + RS );
}

static int scoreForShift( int[] X, int[] Y, int iShift, int[] YSP, int[] YS ) {
    int D_ = 0;
    for( int x = 0; x < X.length; x++ ) {
        int x_ = X[x]+iShift;
        int y = YSP[x],
            y_ = Y[y];

        int D = x_ < y_ ? y_ - x_ : x_ - y_;
        int y_nx_ = Y[y+1];
        int D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        while( D_nx <= D ) {
            D = D_nx;
            y_nx_ = Y[++y+1];
            D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        }
        YS[x] = y;
        D_ += D;
    }
    return D_;
}

static int scoreForShiftFirstPass( int[] X, int[] Y, int[] YS ) {
    int D_ = 0;
    int y = 0;
    for( int x = 0; x < X.length; x++ ) {
        int x_ = X[x];
        int y_ = Y[y];

        int D = x_ < y_ ? y_ - x_ : x_ - y_;
        int y_nx_ = Y[y+1];
        int D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        while( D_nx <= D ) {
            D = D_nx;
            y_nx_ = Y[++y+1];
            D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        }
        YS[x] = y;
        D_ += D;
    }
    return D_;
}

static double doubleScoreForShift( double[] X, double[] Y, double d_Shift, int[] YSP, int[] YS ) {
    double D_ = 0;
    for( int x = 0; x < X.length; x++ ) {
        double x_ = X[x]+d_Shift;
        int y = YSP[x];
        double y_ = Y[y];

        double D = x_ < y_ ? y_ - x_ : x_ - y_;
        double y_nx_ = Y[y+1];
        double D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        while( D_nx <= D ) {
            D = D_nx;
            y_nx_ = Y[++y+1];
            D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        }
        YS[x] = y;
        D_ += D;
    }
    return D_;
}

static double doubleScoreForShiftFirstPass( double[] X, double[] Y, double d_Shift, int[] YS ) {
    double D_ = 0;
    int y = 0;
    for( int x = 0; x < X.length; x++ ) {
        double x_ = X[x]+d_Shift;
        double y_ = Y[y];

        double D = x_ < y_ ? y_ - x_ : x_ - y_;
        double y_nx_ = Y[y+1];
        double D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        while( D_nx <= D ) {
            D = D_nx;
            y_nx_ = Y[++y+1];
            D_nx = x_ < y_nx_ ? y_nx_ - x_ : x_ - y_nx_;
        }
        YS[x] = y;
        D_ += D;
    }
    return D_;
}
}

My approach is similar to Ell's in that it does a grid search over all potentials (first at integer resolution, then at a resolution of 1/1,000ths, then at a resolution of 1/1,000,000ths). Unlike Ell's approach, mine doesn't require or make use of the fact that the error in X is tightly bounded. I literally evaluate all 10,000,000 possibilities during coarse filtering in the T = 10,000,000 case and store a list of candidates with distance small enough to be within "fine filtering" distance of the optimum.
Modular arithmetic is slow, and Java doesn't support template methods for native types. Hence my implementation "unwinds" Y to avoid the use of remainder operators, and the four working methods are near-identical clones of each other with differing types and 1-2 lines of code that would be handled in C/C++ using templates and macros.
I compute shifts sequentially, which allows the nearest neighbour search to incrementally tweak values from the previous shift. As a result, the routine completes in about 2 hours, which was acceptable since I slept through it. ;)
My outcomes are technically better than Ell's since I search to a higher resolution, but the improvement is utterly negligible, and probabilistic to boot. In particular, a higher resolution search only yields an improved score if the number of shifted X values falling in the set of intervals [Y-eps,Y] is different from the number of shifted X values falling in the set of intervals [Y,Y+eps], where eps is the coarser resolution (0.000001, in the case of Ell's implementation). I don't know if this is the case for any of the datasets in this problem. In any event, his code should "win" since it predates mine.
Output
Optimal forward rotation in X: 494.64500000000004
Optimal score: 5.591890690289915
Reference score: 33.0305238422

Optimal forward rotation in X: 6967.556309
Optimal score: 45.032350687407416
Reference score: 429.211871389

Optimal forward rotation in X: 24454.487003000002
Optimal score: 471.7112722703896
Reference score: 4676.23391624

Optimal forward rotation in X: 974011.505734
Optimal score: 4671.756109326729
Reference score: 49148.9676631

Optimal forward rotation in X: 2720706.498309
Optimal score: 46816.15372609813
Reference score: 497143.882534

Thank you for this! As I commented above, I didn't intend this to be solvable by a brute force solution.

C++, Optimal, O(|X|*|Y|*log|X|)
Where X = T / 50 and Y = T / 5. It may take about 2 days on my laptop to finish the T = 10000000 case.
Given two set of points X and Y. We denote the function f(x) to be:
f(x) = min(|x - y| for y in Y)

And then answer we want is:
dist = min(sum(f(x + t) for x in X) for t in [0, T))

However, it's impossible and unnecessary to try all the values of t. Instead we try the t values on "key points". My approach is a scanning from t = 0 to t = T with the help of a priority queue. There will have |X| * |Y| key points and trying each will need O(log|X|) operations. So the overall time complexity is O(|X|*|Y|*log|X|).
Score
               T            angle             dist         ref_dist
          1000.0     494.64422766       5.59189069      33.03052384
         10000.0    6967.55630010      45.03235069     429.21187139
        100000.0   24454.48700190     471.71127227    4676.23391624
       1000000.0  974011.50572340    4671.75610935   49148.96766310
      10000000.0  (still running...)

Code
#include <iostream>
#include <cstdio>
#include <cassert>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Answer {
    double angle;
    double dist;
};

double check(double T, const vector<double>& xs, const vector<double>& ys, Answer answer) {
    double dist = -answer.dist;
    double angle = answer.angle;
    for(double x : xs) {
        double x1 = x + angle;
        while(x1 > T) x1 -= T;
        int i = upper_bound(ys.begin(), ys.end(), x1) - ys.begin();
        double d;
        if(i == 0) {
            d = min(ys[0] - x1, x1 - (ys.back() - T));
        } else if(i == ys.size()) {
            d = min(ys[0] + T - x1, x1 - ys.back());
        } else {
            d = min(ys[i] - x1, x1 - ys[i - 1]);
        }
        dist += d;
    }
    return dist;
}

Answer solve(double T, const vector<double>& xs, vector<double> ys) {
    assert(ys.size() >= 1);

    sort(ys.begin(), ys.end());
    vector<double> ps;
    ps.push_back(ys.back() - T);
    for(int i = 0; i < ys.size(); i++) {
        ps.push_back((ps.back() + ys[i]) / 2);
        ps.push_back(ys[i]);
    }
    ps.push_back((ps.back() + ys.front() + T) / 2);
    ps.push_back(ys.front() + T);

    struct X {
        double npd;
        int sign;
        int j;
        bool operator<(const X& rhs)const {
            return npd > rhs.npd;
        }
    };
    priority_queue<X> que;
    int count = 0;
    Answer ans, cur;
    cur.angle = 0;
    cur.dist = 0;

    for(int i = 0; i < xs.size(); i++) {
        double x = xs[i];
        int j = upper_bound(ps.begin(), ps.end(), x) - ps.begin();
        assert(j > 0 && j < ps.size());
        X q;
        q.j = j;
        q.sign = j % 2 == 1 ? 1 : -1;
        if(q.sign == 1) {
            cur.dist += x - ps[j - 1];
        } else {
            cur.dist += ps[j] - x;
        }
        count += q.sign;
        q.npd = ps[j] - x;
        que.push(q);
    }

    ans = cur;
    while(cur.angle < T) {
        X q = que.top(); que.pop();
        double da = q.npd - cur.angle;
        cur.dist += da * count;
        cur.angle += da;
        assert(cur.dist >= 0);

        if(cur.dist < ans.dist) {
            ans = cur;
        }
        count -= q.sign * 2;
        q.sign *= -1;
        if(q.j == ps.size() - 1) {
            q.j = 3;
        } else {
            q.j ++;
        }
        int j = q.j;
        q.npd = cur.angle + ps[j] - ps[j - 1];
        que.push(q);
    }
    double d_dist = check(T, xs, ys, ans);
    cerr << "check: " << d_dist << endl;
    ans.dist += d_dist;

    return ans;
}

vector<double> read_nums() {
    stringstream ss;
    string line;
    while(line.empty()) getline(cin, line);
    ss << line;
    vector<double> xs;
    while(ss) {
        double x;
        if(ss >> x)
            xs.push_back(x);
    }
    return xs;
}

int main() {
#ifdef DEBUG
    freopen("1000.txt", "r", stdin);
#endif
    double T;
    cin >> T;
    vector<double> xs = read_nums();
    vector<double> ys = read_nums();
    double ref_dist;
    cin >> ref_dist;

    Answer ans = solve(T, xs, ys);

    printf("%16s %16s %16s %16s\n", "T", "angle", "dist", "ref_dist");
    printf("%16.1f %16.8f %16.8f %16.8f\n", T, ans.angle, ans.dist, ref_dist);
}

A bit of details
The function f(x) is something like:

So the graph of sum d(t) = sum(f(x + t) for x in X) is will be a set of connected segments. We need to try each t on the connecting points, with the help of a priority queue.

That's very nice. I don't understand yet why you need the extra log factor. Or in other words, I don't fully understand why you need the priority queue.  However, your answer "100000.0   24454.48700190     471.71127227    4676.23391624" doesn't seem to match "100000     24452.5    2774.90    4676.23" from Martin Büttner" even though it is more or less the same rotation.  Are you calculating the distance correctly?

Is it possible to implement an early stopping rule based on the current minimum distance found? This might speed your code up.

@Lembik The distance value should be correct. It was double checked using the function check. I think it's hopeless to set an early stopping rule, since trying each value cost O(log|X|) operations to maintain the priority queue. It cannot be stop halfway.

Still running? :)

@Lembik No, I halt it. It takes too long and won't get better result than others'.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Digit sum of central binomial coefficients
The task is simply to see how much faster you can calculate n choose n/2 (for even n) than the builtin function in python.  Of course for large n this is a rather large number so rather than output the whole number you should output the sum of the digits. For example, for n = 100000, the answer is 135702. For n=1000000 it is 1354815.
Here is the python code:
from scipy.misc import comb
def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n / 10
   return r
sum_digits(comb(n,n/2,exact=True))

Your score is (highest n on your machine using your code)/(highest n on your machine using my code).  Your code must terminate in 60 seconds or less.
Your program must give the correct output for all even n: 2 <= n <= (your highest n)
You can't use any builtin code or libraries which calculate binomial coefficients or values which can quickly be transformed into binomial coefficients.
You can use any language of your choice.

Leading answer   The current leading answer with an amazing 680.09 is by justhalf.

Are we supposed to submit solutions in python or in a language of choice?

It's possible to write a routine that does this on a modern computer and takes n well into the millions, while I doubt the Python function would handle anything greater than n = 1e5 without choking.

@Alessandro You can use any language of your choice. The only restriction was that you can't use builtin functions to compute the coefficients.

@COTO That sounds very interesting. I look forward to seeing it!

It was just an observation, @Lembik. I'm unfortunately splitting my time between work and one of the existing challenges at this point. I'll upvote the question to get it a bit of exposure, however. ;)

What if my highest n is n=1? (What I want to say is that someone might profit from having a much lower/higher n than someone else in regard of the time complexity of each algorithm) I'd suggest that the algorithm has to work up to a certain (fixed) n and that the timing is calculate according to that.

I want to point of Lucas' Theorem and this generalization to higher powers , though unfortunately 10 is not prime.

@COTO Well into the millions is an understatement. On my old Core Quad 6600 I can get a result for n = 100,000,000 in 32 seconds in C with mpz_bin_uiui(). I actually takes twice as long to stream the digits to the terminal...

@Comintern Part of the challenge is not being able to use a built-in function.

@qwr - That's why I didn't post it as an answer. ;-)   Mainly wanted to give a frame of reference for performance.

Are factorial functions allowed? I assumed not since they could be "quickly transformed into binomial coefficients" (the whole thing is just one factorial divided by another factorial squared), but since an answer is using one now, clarity would be nice.

@Geobits You are right that using a built in factorial function is cheating.

@Comintern: I have successfully replicated that point of reference with 287mil in 1 min, or 169mil in 35 secs! :)

Just realized that the 287mil in 1 min includes the time to convert the result into string. The calculation itself takes only a third of the time (like Comintern noticed in his/her comment): around 18s.

C++ (GMP) - (287,000,000 / 422,000) = 680.09
Shamelessly combine Kummer's Theorem by xnor and GMP by qwr.
Still not even close to the Go solution, not sure why.
Edit: Thanks Keith Randall for the reminder that multiplication is faster if the number is similar in size. I implemented multi-level multiplication, similar to memory coalescing concept on memory management. And the result is impressive. What used to take 51s, now takes only 0.5s (i.e., 100-fold improvement!!)

OLD CODE (n=14,000,000)
Done sieving in 0.343s
Done calculating binom in 51.929s
Done summing in 0.901s
14000000: 18954729

real    0m53.194s
user    0m53.116s
sys 0m0.060s

NEW CODE (n=14,000,000)
Done sieving in 0.343s
Done calculating binom in 0.552s
Done summing in 0.902s
14000000: 18954729

real    0m1.804s
user    0m1.776s
sys 0m0.023s

The run for n=287,000,000

Done sieving in 4.211s
Done calculating binom in 17.934s
Done summing in 37.677s
287000000: 388788354

real    0m59.928s
user    0m58.759s
sys 0m1.116s

The code. Compile with -lgmp -lgmpxx -O3
#include <gmpxx.h>
#include <iostream>
#include <time.h>
#include <cstdio>

const int MAX=287000000;
const int PRIME_COUNT=15700000;

int primes[PRIME_COUNT], factors[PRIME_COUNT], count;
bool sieve[MAX];
int max_idx=0;

void run_sieve(){
    sieve[2] = true;
    primes[0] = 2;
    count = 1;
    for(int i=3; i<MAX; i+=2){
        sieve[i] = true;
    }
    for(int i=3; i<17000; i+=2){
        if(!sieve[i]) continue;
        for(int j = i*i; j<MAX; j+=i){
            sieve[j] = false;
        }
    }
    for(int i=3; i<MAX; i+=2){
        if(sieve[i]) primes[count++] = i;
    }
}

mpz_class sum_digits(mpz_class n){
    clock_t t = clock();
    char* str = mpz_get_str(NULL, 10, n.get_mpz_t());
    int result = 0;
    for(int i=0;str[i]>0;i++){
        result+=str[i]-48;
    }
    printf("Done summing in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    return result;
}

mpz_class nc2_fast(const mpz_class &x){
    clock_t t = clock();
    int prime;
    const unsigned int n = mpz_get_ui(x.get_mpz_t());
    const unsigned int n2 = n/2;
    unsigned int m;
    unsigned int digit;
    unsigned int carry=0;
    unsigned int carries=0;
    mpz_class result = 1;
    mpz_class prime_prods = 1;
    mpz_class tmp;
    mpz_class tmp_prods[32], tmp_prime_prods[32];
    for(int i=0; i<32; i++){
        tmp_prods[i] = (mpz_class)NULL;
        tmp_prime_prods[i] = (mpz_class)NULL;
    }
    for(int i=0; i< count; i++){
        prime = primes[i];
        carry=0;
        carries=0;
        if(prime > n) break;
        if(prime > n2){
            tmp = prime;
            for(int j=0; j<32; j++){
                if(tmp_prime_prods[j] == NULL){
                    tmp_prime_prods[j] = tmp;
                    break;
                } else {
                    mpz_mul(tmp.get_mpz_t(), tmp.get_mpz_t(), tmp_prime_prods[j].get_mpz_t());
                    tmp_prime_prods[j] = (mpz_class)NULL;
                }
            }
            continue;
        }
        m=n2;
        while(m>0){
            digit = m%prime;
            carry = (2*digit + carry >= prime) ? 1 : 0;
            carries += carry;
            m/=prime;
        }
        if(carries>0){
            tmp = 0;
            mpz_ui_pow_ui(tmp.get_mpz_t(), prime, carries);
            for(int j=0; j<32; j++){
                if(tmp_prods[j] == NULL){
                    tmp_prods[j] = tmp;
                    break;
                } else {
                    mpz_mul(tmp.get_mpz_t(), tmp.get_mpz_t(), tmp_prods[j].get_mpz_t());
                    tmp_prods[j] = (mpz_class)NULL;
                }
            }
        }
    }
    result = 1;
    prime_prods = 1;
    for(int j=0; j<32; j++){
        if(tmp_prods[j] != NULL){
            mpz_mul(result.get_mpz_t(), result.get_mpz_t(), tmp_prods[j].get_mpz_t());
        }
        if(tmp_prime_prods[j] != NULL){
            mpz_mul(prime_prods.get_mpz_t(), prime_prods.get_mpz_t(), tmp_prime_prods[j].get_mpz_t());
        }
    }
    mpz_mul(result.get_mpz_t(), result.get_mpz_t(), prime_prods.get_mpz_t());
    printf("Done calculating binom in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    return result;
}

int main(int argc, char* argv[]){
    const mpz_class n = atoi(argv[1]);
    clock_t t = clock();
    run_sieve();
    printf("Done sieving in %.3fs\n", ((float)(clock()-t))/CLOCKS_PER_SEC);
    std::cout << n << ": " << sum_digits(nc2_fast(n)) << std::endl;
    return 0;
}

Multiplies are more efficient if both operands are about the same size.  You are always multiplying big number times little number.  If you repeatedly combine the small numbers in pairs it might be faster  (but take more memory).

Wow, that makes a whole lot of difference. It's exponentially faster. I can reach 169mil now in 35 secs.

Wow indeed!  What is the breakdown in time for the different parts of your code?

I've already put that up in my answer. 4s in generating primes up to n, 18s calculating the central binomial coefficient, and the rest 37s in converting the result into string and summing the digit.

I feel this answer should be contributed to any open source libraries that compute binomial coefficients. I can't believe anyone else has code this fast!

Thanks for the compliment, and thank you to all that make this answer possible. The caveat for this is memory requirement. It requires you to compute list of prime numbers beforehand. And I think based on Comintern's comment, there should already be library than can compute the coefficient efficiently.

What was the memory usage for 287,000,000 ? You may be right that there exists really efficient code for this already but I don't think it's in scipy, for example. Normally there are licensing reasons why the fastest code is stuck in one project. Also, I would love to see a comparison between your code and the code that Comintern pointed to.

I didn't measure, not sure how to check exact memory usage in C++, I usually work in Python. But for storing the primes, we can calculate. Assuming 4 bytes per int, with 15.7M prime numbers we need around 60MB. That doesn't include the memory for storing the result. Perhaps another 100MB.

That's interesting. http://stackoverflow.com/questions/63166/how-to-determine-cpu-and-memory-consumption-from-inside-a-process gives lots of ways of measuring memory usage as well but your method looks fine.

Valgrind is a decent memory profiler - take a look into the Massif tool.

It seems currently the biggest time consumption you have is summing the digits. You can further optimize that by precalculating the sum of digits for all the numbers up to 1 million (or bigger power of ten, which will fit in memory) and then splitting the number in chunks with known sum.

Precalculating should also be counted towards the total score, so in this case it wouldn't matter much, even I think it could be worse due to unnecessary digit sum. I've tried to find faster one, but I haven't been able to find anything faster. Division, which should have already be by GMP internally, seems to be the fastest so far.

You can sum digits mathematically with modulo 10, it should be faster

Hi, thanks for the input, but like I said, the modulo (which should include division) should have already been done by GMP internally =)

Go, 33.96 = (16300000 / 480000)
package main

import "math/big"

const n = 16300000

var (
    sieve     [n + 1]bool
    remaining [n + 1]int
    count     [n + 1]int
)

func main() {
    println("finding primes")
    for p := 2; p <= n; p++ {
        if sieve[p] {
            continue
        }
        for i := p * p; i <= n; i += p {
            sieve[i] = true
        }
    }

    // count net number of times each prime appears in the result.
    println("counting factors")
    for i := 2; i <= n; i++ {
        remaining[i] = i
    }
    for p := 2; p <= n; p++ {
        if sieve[p] {
            continue
        }

        for i := p; i <= n; i += p {
            for remaining[i]%p == 0 { // may have multiple factors of p
                remaining[i] /= p

                // count positive for n!
                count[p]++
                // count negative twice for ((n/2)!)^2
                if i <= n/2 {
                    count[p] -= 2
                }
            }
        }
    }

    // ignore all the trailing zeros
    count[2] -= count[5]
    count[5] = 0

    println("listing factors")
    var m []uint64
    for i := 0; i <= n; i++ {
        for count[i] > 0 {
            m = append(m, uint64(i))
            count[i]--
        }
    }

    println("grouping factors")
    m = group(m)

    println("multiplying")
    x := mul(m)

    println("converting to base 10")
    d := 0
    for _, c := range x.String() {
        d += int(c - '0')
    }
    println("sum of digits:", d)
}

// Return product of elements in a.
func mul(a []uint64) *big.Int {
    if len(a) == 1 {
        x := big.NewInt(0)
        x.SetUint64(a[0])
        return x
    }
    m := len(a) / 2
    x := mul(a[:m])
    y := mul(a[m:])
    x.Mul(x, y) // fast because x and y are about the same length
    return x
}

// return a slice whose members have the same product
// as the input slice, but hopefully shorter.
func group(a []uint64) []uint64 {
    var g []uint64
    r := uint64(1)
    b := 1
    for _, x := range a {
        c := bits(x)
        if b+c <= 64 {
            r *= x
            b += c
        } else {
            g = append(g, r)
            r = x
            b = c
        }
    }
    g = append(g, r)
    return g
}

// bits returns the number of bits in the representation of x
func bits(x uint64) int {
    n := 0
    for x != 0 {
        n++
        x >>= 1
    }
    return n
}

Works by counting all the prime factors in the numerator and denominator and canceling matching factors.  Multiplies the leftovers to get the result.
More than 80% of the time is spent in converting to base 10.  There's got to be a better way to do that...

For problems which require printing large numbers in base 10 I usually find it helpful to write my own BigInteger class which stores numbers in base 1E9 ~ 2^30.

You are currently winning by a country mile.. as they say.

@PeterTaylor: I tried that, but it requires lots of %1e9 in the multiply code, which makes the multiply slow.

Python 3 (8.8 = 2.2 million / 0.25 million)
This is in Python, which isn't known for speed, so you can probably do better porting this to another language.
Primes generator taken from this StackOverflow contest.
import numpy
import time

def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

t0 = time.clock()

N=220*10**4
n=N//2

print("N = %d" % N)
print()

print("Generating primes.")
primes = primesfrom2to(N)

t1 = time.clock()
print ("Time taken: %f" % (t1-t0))

print("Computing product.")
product = 1

for p in primes:
    p=int(p)
    carries = 0
    carry = 0

    if p>n:
        product*=p
        continue

    m=n

    #Count carries of n+n in base p as per Kummer's Theorem
    while m:
        digit = m%p
        carry = (2*digit + carry >= p)
        carries += carry
        m//=p

    if carries >0:
        for _ in range(carries):
            product *= p

    #print(p,carries,product)

t2 = time.clock()
print ("Time taken: %f" % (t2-t1))

print("Converting number to string.")

# digit_sum = 0
# result=product

# while result:
    # digit_sum+=result%10
    # result//=10

digit_sum = 0
digit_string = str(product)

t3 = time.clock()
print ("Time taken: %f" % (t3-t2))

print("Summing digits.")
for d in str(digit_string):digit_sum+=int(d)

t4 = time.clock()
print ("Time taken: %f" % (t4-t3))
print ()

print ("Total time: %f" % (t4-t0))
print()
print("Sum of digits = %d" % digit_sum)

The main idea of the algorithm is to use Kummer's Theorem to get the prime-factorization of the binomial. For each prime, we learn the highest power of it that divides the answer, and multiply the running product by that power of the prime. In this way, we only need to multiply once for each prime in the prime-factorization of the answer.
Output showing time breakdown:
N = 2200000
Generating primes.
Time taken: 0.046408
Computing product.
Time taken: 17.931472
Converting number to string.
Time taken: 39.083390
Summing digits.
Time taken: 1.502393

Total time: 58.563664

Sum of digits = 2980107

Surprisingly, most of the time is spent converting the number to a string to sum its digits. Also surprisingly, converting to a string was much faster than getting digits from repeated %10 and //10, even though the whole string must presumably be kept in memory.
Generating the primes takes negligible time (and hence I don't feel unfair copying existing code). Summing digits is fast. The actual multiplication takes one third of the time.
Given that digit summing seems to be the limiting factor, perhaps an algorithm to multiply numbers in decimal representation would save time in total by shortcutting the binary/decimal conversion.

This is very impressive and makes you wonder why cpython doesn't use your implementation!

Java (score 22500 / 365000 = 0.062)
I don't have Python on this machine, so if someone could score this I would be grateful. If not, it will have to wait.
The basis of this implementation is
$$\binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2$$
The bottleneck is the addition to compute the relevant section of Pascal's triangle (90% of running time), so using a better multiplication algorithm wouldn't really help.
Note that what the question calls n is what I call 2n. The command-line argument is what the question calls n.
public class CodeGolf37270 {
    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Usage: java CodeGolf37270 <n>");
            System.exit(1);
        }

        int two_n = Integer.parseInt(args[0]);
        // \binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2
        // Two cases:
        //   n = 2m: \binom{4m}{2m} = \binom{2m}{m}^2 + 2\sum_{k=0}^{m-1} \binom{2m}{k}^2
        //   n = 2m+1: \binom{4m+2}{2m+1} = 2\sum_{k=0}^{m} \binom{2m+1}{k}^2
        int n = two_n / 2;
        BigInt[] nCk = new BigInt[n/2 + 1];
        nCk[0] = new BigInt(1);
        for (int k = 1; k < nCk.length; k++) nCk[k] = nCk[0];
        for (int row = 2; row <= n; row++) {
            BigInt tmp = nCk[0];
            for (int col = 1; col < row && col < nCk.length; col++) {
                BigInt replacement = tmp.add(nCk[col]);
                tmp = nCk[col];
                nCk[col] = replacement;
            }
        }

        BigInt central = nCk[0]; // 1^2 = 1
        int lim = (n & 1) == 1 ? nCk.length : (nCk.length - 1);
        for (int k = 1; k < lim; k++) central = central.add(nCk[k].sq());
        central = central.add(central);
        if ((n & 1) == 0) central = central.add(nCk[nCk.length - 1].sq());

        System.out.println(central.digsum());
    }

    private static class BigInt {
        static final int B = 1000000000;
        private int[] val;

        public BigInt(int x) {
            val = new int[] { x };
        }

        private BigInt(int[] val) {
            this.val = val;
        }

        public BigInt add(BigInt that) {
            int[] left, right;
            if (val.length < that.val.length) {
                left = that.val;
                right = val;
            }
            else {
                left = val;
                right = that.val;
            }

            int[] sum = left.clone();
            int carry = 0, k = 0;
            for (; k < right.length; k++) {
                int a = sum[k] + right[k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            while (carry > 0 && k < sum.length) {
                int a = sum[k] + carry;
                sum[k] = a % B;
                carry = a / B;
                k++;
            }
            if (carry > 0) {
                int[] wider = new int[sum.length + 1];
                System.arraycopy(sum, 0, wider, 0, sum.length);
                wider[sum.length] = carry;
                sum = wider;
            }

            return new BigInt(sum);
        }

        public BigInt sq() {
            int[] rv = new int[2 * val.length];
            // Naive multiplication
            for (int i = 0; i < val.length; i++) {
                for (int j = i; j < val.length; j++) {
                    int k = i+j;
                    long c = val[i] * (long)val[j];
                    if (j > i) c <<= 1;
                    while (c > 0) {
                        c += rv[k];
                        rv[k] = (int)(c % B);
                        c /= B;
                        k++;
                    }
                }
            }

            int len = rv.length;
            while (len > 1 && rv[len - 1] == 0) len--;
            if (len < rv.length) {
                int[] rv2 = new int[len];
                System.arraycopy(rv, 0, rv2, 0, len);
                rv = rv2;
            }

            return new BigInt(rv);
        }

        public long digsum() {
            long rv = 0;
            for (int i = 0; i < val.length; i++) {
                int x = val[i];
                while (x > 0) {
                    rv += x % 10;
                    x /= 10;
                }
            }
            return rv;
        }
    }
}

I get 29,500 for your program and 440,000 for the reference program, so that would be a score of 0.067. This is compiling with Java 1.7 (javac CodeGolf37270.java) and executing with Java 1.8 (java CodeGolf37270 n). I'm not sure if there are any optimizations options I'm unaware of. I can't try compiling with Java 1.8, because it doesn't get installed with my Java package...

Interesting approach. Why do you think calculating it iteratively could be faster than using the simple formula?

@justhalf, I didn't have an intuition for whether it would be faster or not, and I didn't try to do complexity calculations. I looked through lists of identities for central binomial coefficients to try to find formulae which would be simple to implement with a custom big integer class optimised for extracting base-10 digits. And having discovered that it's not very efficient, I may as well post it and save someone else from repeating the experiment. (FWIW I'm working on Toom multiplication, but I'm not sure when I'll have it tested and debugged).

GMP - 1500000 / 300000 = 5.0
Although this answer won't compete against sieves, sometimes short code can still get results.
#include <gmpxx.h>
#include <iostream>

mpz_class sum_digits(mpz_class n)
{
    char* str = mpz_get_str(NULL, 10, n.get_mpz_t());
    int result = 0;
    for(int i=0; str[i]>0; i++)

    result += str[i] - 48;

    return result;
}

mpz_class comb_2(const mpz_class &x)
{
    const unsigned int k = mpz_get_ui(x.get_mpz_t()) / 2;
    mpz_class result = k + 1;

    for(int i=2; i<=k; i++)
    {
        result *= k + i;
        mpz_divexact_ui(result.get_mpz_t(), result.get_mpz_t(), i);
    }

    return result;
}

int main()
{
    const mpz_class n = 1500000;
    std::cout << sum_digits(comb_2(n)) << std::endl;

    return 0;
}

Java, custom big integer class: 32.9 (120000000 / 365000)
The main class is pretty straightforward:
import java.util.*;

public class PPCG37270 {
    public static void main(String[] args) {
        long start = System.nanoTime();

        int n = 12000000;
        if (args.length == 1) n = Integer.parseInt(args[0]);

        boolean[] sieve = new boolean[n + 1];
        int[] remaining = new int[n + 1];
        int[] count = new int[n + 1];

        for (int p = 2; p <= n; p++) {
            if (sieve[p]) continue;
            long p2 = p * (long)p;
            if (p2 > n) continue;
            for (int i = (int)p2; i <= n; i += p) sieve[i] = true;
        }

        for (int i = 2; i <= n; i++) remaining[i] = i;
        for (int p = 2; p <= n; p++) {
            if (sieve[p]) continue;
            for (int i = p; i <= n; i += p) {
                while (remaining[i] % p == 0) {
                    remaining[i] /= p;
                    count[p]++;
                    if (i <= n/2) count[p] -= 2;
                }
            }
        }

        count[2] -= count[5];
        count[5] = 0;

        List<BigInt> partialProd = new ArrayList<BigInt>();
        long accum = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = count[i]; j > 0; j--) {
                long tmp = accum * i;
                if (tmp < 1000000000L) accum = tmp;
                else {
                    partialProd.add(new BigInt((int)accum));
                    accum = i;
                }
            }
        }
        partialProd.add(new BigInt((int)accum));
        System.out.println(prod(partialProd).digsum());
        System.out.println((System.nanoTime() - start) / 1000000 + "ms");
    }

    private static BigInt prod(List<BigInt> vals) {
        while (vals.size() > 1) {
            int n = vals.size();
            List<BigInt> next = new ArrayList<BigInt>();
            for (int i = 0; i < n; i += 2) {
                if (i == n - 1) next.add(vals.get(i));
                else next.add(vals.get(i).mul(vals.get(i+1)));
            }
            vals = next;
        }
        return vals.get(0);
    }
}

It relies on a big integer class which is optimised for multiplication and toString(), both of which are significant bottlenecks in an implementation with java.math.BigInteger.
/**
 * A big integer class which is optimised for conversion to decimal.
 * For use in simple applications where BigInteger.toString() is a bottleneck.
 */
public class BigInt {
    // The base of the representation.
    private static final int B = 1000000000;
    // The number of decimal digits per digit of the representation.
    private static final int LOG10_B = 9;

    public static final BigInt ZERO = new BigInt(0);
    public static final BigInt ONE = new BigInt(1);

    // We use sign-magnitude representation.
    private final boolean negative;

    // Least significant digit is at val[off]; most significant is at val[off + len - 1]
    // Unless len == 1 we guarantee that val[off + len - 1] is non-zero.
    private final int[] val;
    private final int off;
    private final int len;

    // Toom-style multiplication parameters from
    // Zuras, D. (1994). More on squaring and multiplying large integers. IEEE Transactions on Computers, 43(8), 899-908.
    private static final int[][][] Q = new int[][][]{
        {},
        {},
        {{1, -1}},
        {{4, 2, 1}, {1, 1, 1}, {1, 2, 4}},
        {{8, 4, 2, 1}, {-8, 4, -2, 1}, {1, 1, 1, 1}, {1, -2, 4, -8}, {1, 2, 4, 8}}
    };
    private static final int[][][] R = new int[][][]{
        {},
        {},
        {{1, -1, 1}},
        {{-21, 2, -12, 1, -6}, {7, -1, 10, -1, 7}, {-6, 1, -12, 2, -21}},
        {{-180, 6, 2, -80, 1, 3, -180}, {-510, 4, 4, 0, -1, -1, 120}, {1530, -27, -7, 680, -7, -27, 1530}, {120, -1, -1, 0, 4, 4, -510}, {-180, 3, 1, -80, 2, 6, -180}}
    };
    private static final int[][] S = new int[][]{
        {},
        {},
        {1, 1, 1},
        {1, 6, 2, 6, 1},
        {1, 180, 120, 360, 120, 180, 1}
    };

    /**
     * Constructs a big version of an integer value.
     * @param x The value to represent.
     */
    public BigInt(int x) {
        this(Integer.toString(x));
    }

    /**
     * Constructs a big version of a long value.
     * @param x The value to represent.
     */
    public BigInt(long x) {
        this(Long.toString(x));
    }

    /**
     * Parses a decimal representation of an integer.
     * @param str The value to represent.
     */
    public BigInt(String str) {
        this(str.charAt(0) == '-', split(str));
    }

    /**
     * Constructs a sign-magnitude representation taking the entire span of the array as the range of interest.
     * @param neg Is the value negative?
     * @param val The base-B digits, least significant first.
     */
    private BigInt(boolean neg, int[] val) {
        this(neg, val, 0, val.length);
    }

    /**
     * Constructs a sign-magnitude representation taking a range of an array as the magnitude.
     * @param neg Is the value negative?
     * @param val The base-B digits, least significant at offset off, most significant at off + val - 1.
     * @param off The offset within the array.
     * @param len The number of base-B digits.
     */
    private BigInt(boolean neg, int[] val, int off, int len) {
        // Bounds checks
        if (val == null) throw new IllegalArgumentException("val");
        if (off < 0 || off >= val.length) throw new IllegalArgumentException("off");
        if (len < 1 || off + len > val.length) throw new IllegalArgumentException("len");

        this.negative = neg;
        this.val = val;
        this.off = off;
        // Enforce the invariant that this.len is 1 or val[off + len - 1] is non-zero.
        while (len > 1 && val[off + len - 1] == 0) len--;
        this.len = len;

        // Sanity check
        for (int i = 0; i < len; i++) {
            if (val[off + i] < 0) throw new IllegalArgumentException("val contains negative digits");
        }
    }

    /**
     * Splits a string into base-B digits.
     * @param str The string to parse.
     * @return An array which can be passed to the (boolean, int[]) constructor.
     */
    private static int[] split(String str) {
        if (str.charAt(0) == '-') str = str.substring(1);

        int[] arr = new int[(str.length() + LOG10_B - 1) / LOG10_B];
        int i, off;
        // Each element of arr represents LOG10_B characters except (probably) the last one.
        for (i = 0, off = str.length() - LOG10_B; off > 0; off -= LOG10_B) {
            arr[i++] = Integer.parseInt(str.substring(off, off + LOG10_B));
        }
        arr[i] = Integer.parseInt(str.substring(0, off + LOG10_B));
        return arr;
    }

    public boolean isZero() {
        return len == 1 && val[off] == 0;
    }

    public BigInt negate() {
        return new BigInt(!negative, val, off, len);
    }

    public BigInt add(BigInt that) {
        // If the signs differ, then since we use sign-magnitude representation we want to do a subtraction.
        boolean isSubtraction = negative ^ that.negative;

        BigInt left, right;
        if (len < that.len) {
            left = that;
            right = this;
        }
        else {
            left = this;
            right = that;

            // For addition I just care about the lengths of the arrays.
            // For subtraction I want the largest absolute value on the left.
            if (isSubtraction && len == that.len) {
                int cmp = compareAbsolute(that);
                if (cmp == 0) return ZERO; // Cheap special case
                if (cmp < 0) {
                    left = that;
                    right = this;
                }
            }
        }

        if (right.isZero()) return left;

        BigInt result;
        if (!isSubtraction) {
            int[] sum = new int[left.len + 1];
            // A copy here rather than using left.val in the main loops and copying remaining values
            // at the end gives a small performance boost, probably due to cache locality.
            System.arraycopy(left.val, left.off, sum, 0, left.len);

            int carry = 0, k = 0;
            for (; k < right.len; k++) {
                int a = sum[k] + right.val[right.off + k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            for (; carry > 0 && k < left.len; k++) {
                int a = sum[k] + carry;
                sum[k] = a % B;
                carry = a / B;
            }
            sum[left.len] = carry;

            result = new BigInt(negative, sum);
        }
        else {
            int[] diff = new int[left.len];
            System.arraycopy(left.val, left.off, diff, 0, left.len);

            int carry = 0, k = 0;
            for (; k < right.len; k++) {
                int a = diff[k] - right.val[right.off + k] + carry;
                // Why did anyone ever think that rounding positive and negative divisions differently made sense?
                if (a < 0) {
                    diff[k] = a + B;
                    carry = -1;
                }
                else {
                    diff[k] = a % B;
                    carry = a / B;
                }
            }
            for (; carry != 0 && k < left.len; k++) {
                int a = diff[k] + carry;
                if (a < 0) {
                    diff[k] = a + B;
                    carry = -1;
                }
                else {
                    diff[k] = a % B;
                    carry = a / B;
                }
            }

            result = new BigInt(left.negative, diff, 0, k > left.len ? k : left.len);
        }

        return result;
    }

    private int compareAbsolute(BigInt that) {
        if (len > that.len) return 1;
        if (len < that.len) return -1;

        for (int i = len - 1; i >= 0; i--) {
            if (val[off + i] > that.val[that.off + i]) return 1;
            if (val[off + i] < that.val[that.off + i]) return -1;
        }

        return 0;
    }

    public BigInt mul(BigInt that) {
        if (isZero() || that.isZero()) return ZERO;

        if (len == 1) return that.mulSmall(negative ? -val[off] : val[off]);
        if (that.len == 1) return mulSmall(that.negative ? -that.val[that.off] : that.val[that.off]);

        int shorter = len < that.len ? len : that.len;
        BigInt result;
        // Cutoffs have been hand-tuned.
        if (shorter > 300) result = mulToom(3, that);
        else if (shorter > 28) result = mulToom(2, that);
        else result = mulNaive(that);

        return result;
    }

    BigInt mulSmall(int m) {
        if (m == 0) return ZERO;
        if (m == 1) return this;
        if (m == -1) return negate();

        // We want to do the magnitude calculation with a positive multiplicand.
        boolean neg = negative;
        if (m < 0) {
            neg = !neg;
            m = -m;
        }

        int[] pr = new int[len + 1];
        int carry = 0;
        for (int i = 0; i < len; i++) {
            long t = val[off + i] * (long)m + carry;
            pr[i] = (int)(t % B);
            carry = (int)(t / B);
        }
        pr[len] = carry;
        return new BigInt(neg, pr);
    }

    // NB This truncates.
    BigInt divSmall(int d) {
        if (d == 0) throw new ArithmeticException();
        if (d == 1) return this;
        if (d == -1) return negate();

        // We want to do the magnitude calculation with a positive divisor.
        boolean neg = negative;
        if (d < 0) {
            neg = !neg;
            d = -d;
        }

        int[] div = new int[len];
        int rem = 0;
        for (int i = len - 1; i >= 0; i--) {
            long t = val[off + i] + rem * (long)B;
            div[i] = (int)(t / d);
            rem = (int)(t % d);
        }

        return new BigInt(neg, div);
    }

    BigInt mulNaive(BigInt that) {
        int[] rv = new int[len + that.len];
        // Naive multiplication
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < that.len; j++) {
                int k = i + j;
                long c = val[off + i] * (long)that.val[that.off + j];
                while (c > 0) {
                    c += rv[k];
                    rv[k] = (int)(c % B);
                    c /= B;
                    k++;
                }
            }
        }

        return new BigInt(this.negative ^ that.negative, rv);
    }

    private BigInt mulToom(int k, BigInt that) {
        // We split each number into k parts of m base-B digits each.
        // m = ceil(longer / k)
        int m = ((len > that.len ? len : that.len) + k - 1) / k;

        // Perform the splitting and evaluation steps of Toom-Cook.
        BigInt[] f1 = this.toomFwd(k, m);
        BigInt[] f2 = that.toomFwd(k, m);

        // Pointwise multiplication.
        for (int i = 0; i < f1.length; i++) f1[i] = f1[i].mul(f2[i]);

        // Inverse (or interpolation) and recomposition.
        return toomBk(k, m, f1, negative ^ that.negative, val[off], that.val[that.off]);
    }

    // Splits a number into k parts of m base-B digits each and does the polynomial evaluation.
    private BigInt[] toomFwd(int k, int m) {
        // Split.
        BigInt[] a = new BigInt[k];
        for (int i = 0; i < k; i++) {
            int o = i * m;
            if (o >= len) a[i] = ZERO;
            else {
                int l = m;
                if (o + l > len) l = len - o;
                // Ignore signs for now.
                a[i] = new BigInt(false, val, off + o, l);
            }
        }

        // Evaluate
        return transform(Q[k], a);
    }

    private BigInt toomBk(int k, int m, BigInt[] f, boolean neg, int lsd1, int lsd2) {
        // Inverse (or interpolation).
        BigInt[] b = transform(R[k], f);

        // Recomposition: add at suitable offsets, dividing by the normalisation factors
        BigInt prod = ZERO;
        int[] s = S[k];
        for (int i = 0; i < b.length; i++) {
            int[] shifted = new int[i * m + b[i].len];
            System.arraycopy(b[i].val, b[i].off, shifted, i * m, b[i].len);
            prod = prod.add(new BigInt(neg ^ b[i].negative, shifted).divSmall(s[i]));
        }

        // Handle the remainders.
        // In the worst case the absolute value of the sum of the remainders is s.length, so pretty small.
        // It should be easy enough to work out whether to go up or down.
        int lsd = (int)((lsd1 * (long)lsd2) % B);
        int err = lsd - prod.val[prod.off];
        if (err > B / 2) err -= B / 2;
        if (err < -B / 2) err += B / 2;
        return prod.add(new BigInt(err));
    }

    /**
     * Multiplies a matrix of small integers and a vector of big ones.
     * The matrix has a implicit leading row [1 0 ... 0] and an implicit trailing row [0 ... 0 1].
     * @param m The matrix.
     * @param v The vector.
     * @return m v
     */
    private BigInt[] transform(int[][] m, BigInt[] v) {
        BigInt[] b = new BigInt[m.length + 2];
        b[0] = v[0];
        for (int i = 0; i < m.length; i++) {
            BigInt s = ZERO;
            for (int j = 0; j < m[i].length; j++) s = s.add(v[j].mulSmall(m[i][j]));
            b[i + 1] = s;
        }
        b[b.length - 1] = v[v.length - 1];

        return b;
    }

    /**
     * Sums the digits of this integer.
     * @return The sum of the digits of this integer.
     */
    public long digsum() {
        long rv = 0;
        for (int i = 0; i < len; i++) {
            int x = val[off + i];
            while (x > 0) {
                rv += x % 10;
                x /= 10;
            }
        }
        return rv;
    }
}

The big bottleneck is naïve multiplication (60%), followed by the other multiplication (37%) and the sieving (3%). The digsum() call is insignificant.
Performance measured with OpenJDK 7 (64 bit).

Very nice. Thank you.

Java (2,020,000/491,000) = 4.11
updated, previously 2.24
Java BigInteger isn't the fastest number cruncher, but it's better than nothing.
The basic formula for this seems to be n! / ((n/2)!^2), but that seems like a bunch of redundant multiplication.
You can get a significant speedup by eliminating all prime factors found in both the numerator and denominator. To do this, I first run a simple prime sieve. Then for each prime, I keep a count of what power it needs to be raised to. Increment each time I see a factor in the numerator, decrement for the denominator.
I handle twos separately (and first), since it's easy to count/eliminate them before factoring.
Once that's done, you have the minimum amount of multiplications necessary, which is good because BigInt multiply is slow.
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class CentBiCo {
    public static void main(String[] args) {
        int n = 2020000;
        long time = System.currentTimeMillis();
        sieve(n);
        System.out.println(sumDigits(cbc(n)));
        System.out.println(System.currentTimeMillis()-time);
    }

    static boolean[] sieve;
    static List<Integer> primes;
    static void sieve(int n){
        primes = new ArrayList<Integer>((int)(Math.sqrt(n)));
        sieve = new boolean[n];
        sieve[2]=true;
        for(int i=3;i<sieve.length;i+=2)
            if(i%2==1)
                sieve[i] = true;
        for(int i=3;i<sieve.length;i+=2){
            if(!sieve[i])
                continue;
            for(int j=i*2;j<sieve.length;j+=i)
                sieve[j] = false;
        }
        for(int i=2;i<sieve.length;i++)
            if(sieve[i])
                primes.add(i);
    }

    static int[] factors;
    static void addFactors(int n, int flip){
        for(int k=0;primes.get(k)<=n;){
            int i = primes.get(k);
            if(n%i==0){
                factors[i] += flip;
                n /= i;
            } else {
                if(++k == primes.size())
                    break;
            }
        }
        factors[n]++;
    }

    static BigInteger cbc(int n){
        factors = new int[n+1];
        int x = n/2;
        for(int i=x%2<1?x+1:x+2;i<n;i+=2)
            addFactors(i,1);
        factors[2] = x;
        for(int i=1;i<=x/2;i++){
            int j=i;
            while(j%2<1 && factors[2] > 1){
                j=j/2;
                factors[2]--;
            }
            addFactors(j,-1);
            factors[2]--;
        }
        BigInteger cbc = BigInteger.ONE;
        for(int i=3;i<factors.length;i++){
            if(factors[i]>0)
                cbc = cbc.multiply(BigInteger.valueOf(i).pow(factors[i]));
        }
        return cbc.shiftLeft(factors[2]);
    }

    static long sumDigits(BigInteger in){
        long sum = 0;
        String str = in.toString();
        for(int i=0;i<str.length();i++)
            sum += str.charAt(i)-'0';
        return sum;
    }
}

Oh, and the output sum for n=2020000 is 2735298, for verification purposes.

Python 2 (PyPy), 1,134,000 / 486,000 = 2.32
#/!usr/bin/pypy
n=input(); a, b, c=1, 1, 2**((n+2)/4)
for i in range(n-1, n/2, -2): a*=i
for i in range(2, n/4+1): b*=i
print sum(map(int, str(a*c/b)))

Result: 1,537,506
Fun fact: The bottleneck of your code is adding the digits, not computing the binomial coefficient.

Why is python so slow at adding digits? Both you and xnor say it is. It made me curious, so I clocked mine. It came in at less than a second for the sum part (Java).

@Geobits Hmm, curious. Is Java also able to do binary-decimal conversions similarly fast? It does represent integers in binary, right?

That's a good question. For integer/Integer/long/Long I know it's binary. I'm not exactly sure what the internal representation of a BigInteger is. If it's decimal, that would definitely explain why it's slow at math but fast to convert to a string. May look that up tomorrow.

@Geobits, the internal representation of BigInteger is base 2.

I always assumed so, but it made me wonder. It looks like it's breaking it down into long-sized chunks and converting it that way, at least in OpenJDK.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/