Agora que todos desenvolveram sua (muitas vezes incrível) experiência em codificação de baixo nível para Quão lento é realmente o Python? (Ou qual a velocidade da sua linguagem?) E Qual a velocidade do Python (parte II)? é hora de um desafio que também aumentará sua capacidade de melhorar um algoritmo.

O código a seguir calcula uma lista de comprimento 9. A posição ina lista conta o número de vezes que iforam encontrados pelo menos zeros consecutivos ao calcular os produtos internos entre Fe S. Para fazer isso exatamente, ele itera sobre todas as listas possíveis Fde comprimento ne listas Sde comprimento n+m-1.

#!/usr/bin/python
import itertools
import operator

n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
            leadingzerocounts[i] +=1
            i+=1
print leadingzerocounts

A saída é

[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]

Se você aumentar n para 10,12,14,16,18,20 usando esse código, muito rapidamente se tornará muito lento.

Regras

• O desafio é fornecer a saída correta para o maior número possível de n. Apenas valores pares de n são relevantes.
• Se houver um empate, a vitória vai para o código mais rápido da minha máquina para o maior n.
• Reservo-me o direito de não testar o código que leva mais de 10 minutos.
• Você pode alterar o algoritmo da maneira que desejar, desde que ele produza a saída correta. Na verdade, você terá que alterar o algoritmo para fazer um progresso decente em direção à vitória.
• O vencedor será premiado uma semana a partir do momento em que a pergunta foi feita.
• A recompensa será concedida no vencimento, um pouco depois do vencimento do vencedor.

Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos. Isso também significa que eu preciso poder executar seu código. Como conseqüência, use apenas software livre facilmente disponível e inclua instruções completas sobre como compilar e executar seu código.

Status .

• C . n = 12 em 49 segundos por @Fors
• Java . n = 16 em 3:07 por @PeterTaylor
• C ++ . n = 16 em 2:21 por @ilmale
• Rpython . n = 22 em 3:11 por @primo
• Java . n = 22 em 6:56 por @PeterTaylor
• Nimrod . n = 24 em 9:28 segundos por @ReimerBehrends

O vencedor foi Reimer Behrends com uma entrada em Nimrod!

Como verificação, a saída para n = 22 deve ser [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680].

A competição terminou agora ... Oferecerei 200 pontos por cada envio que aumentar n em 2 (dentro de 10 minutos no meu computador) até que eu fique sem pontos. Esta oferta está aberta para sempre .

Nimrod (N = 22)

import math, locks

const
  N = 20
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, int]
  ComputeThread = TThread[int]

var
  leadingZeros: ZeroCounter
  lock: TLock
  innerProductTable: array[0..FMax, int8]

proc initInnerProductTable =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)

initInnerProductTable()

proc zeroInnerProduct(i: int): bool =
  innerProductTable[i] == 0

proc search2(lz: var ZeroCounter, s, f, i: int) =
  if zeroInnerProduct(s xor f) and i < M:
    lz[i] += 1 shl (M - i - 1)
    search2(lz, (s shr 1) + 0, f, i+1)
    search2(lz, (s shr 1) + SStep, f, i+1)

when defined(gcc):
  const
    unrollDepth = 1
else:
  const
    unrollDepth = 4

template search(lz: var ZeroCounter, s, f, i: int) =
  when i < unrollDepth:
    if zeroInnerProduct(s xor f) and i < M:
      lz[i] += 1 shl (M - i - 1)
      search(lz, (s shr 1) + 0, f, i+1)
      search(lz, (s shr 1) + SStep, f, i+1)
  else:
    search2(lz, s, f, i)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for f in countup(base, FMax div 2, numThreads):
    for s in 0..FMax:
      search(lz, s, f, 0)
  acquire(lock)
  for i in 0..M-1:
    leadingZeros[i] += lz[i]*2
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

Ajuntar com

nimrod cc --threads:on -d:release count.nim

(O Nimrod pode ser baixado aqui .)

Isso é executado no tempo alocado para n = 20 (e para n = 18 ao usar apenas um único encadeamento, levando cerca de 2 minutos no último caso).

O algoritmo usa uma pesquisa recursiva, removendo a árvore de pesquisa sempre que um produto interno diferente de zero é encontrado. Também cortamos o espaço de pesquisa pela metade, observando que, para qualquer par de vetores (F, -F), precisamos considerar apenas um porque o outro produz exatamente os mesmos conjuntos de produtos internos (negando Stambém).

A implementação usa os recursos de metaprogramação do Nimrod para desenrolar / alinhar os primeiros níveis da pesquisa recursiva. Isso economiza um pouco de tempo ao usar o gcc 4.8 e 4.9 como o back-end do Nimrod e uma quantidade razoável de clang.

O espaço de pesquisa poderia ser ainda mais podado, observando que só precisamos considerar valores de S que diferem em um número par das primeiras posições N da escolha de F. de N, dado que o corpo do loop é completamente ignorado nesses casos.

Tabular onde o produto interno é zero parece ser mais rápido do que usar qualquer funcionalidade de contagem de bits no loop. Aparentemente, acessar a tabela tem uma boa localidade.

Parece que o problema deve ser passível de programação dinâmica, considerando como a pesquisa recursiva funciona, mas não há uma maneira aparente de fazer isso com uma quantidade razoável de memória.

Exemplo de saídas:

N = 16:

@[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]

N = 18:

@[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

N = 20:

@[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

Para fins de comparação do algoritmo com outras implementações, N = 16 leva cerca de 7,9 segundos na minha máquina ao usar um único encadeamento e 2,3 segundos ao usar quatro núcleos.

N = 22 leva cerca de 15 minutos em uma máquina de 64 núcleos com o gcc 4.4.6, como o back-end do Nimrod e transborda números inteiros de 64 bits leadingZeros[0](possivelmente os não assinados, que ainda não viram).

Atualização: Encontrei espaço para mais algumas melhorias. Primeiro, para um determinado valor de F, podemos enumerar as 16 primeiras entradas dos Svetores correspondentes com precisão, porque elas devem diferir exatamente em N/2locais. Portanto, pré-calculamos uma lista de vetores de bits de tamanho Ncom N/2bits definidos e os usamos para derivar a parte inicial de Sfrom F.

Segundo, podemos melhorar a pesquisa recursiva, observando que sempre sabemos o valor de F[N](como o MSB é zero na representação de bits). Isso nos permite prever com precisão em qual ramo recorreremos do produto interno. Embora isso nos permita transformar toda a pesquisa em um loop recursivo, isso acaba atrapalhando bastante a previsão do ramo, por isso mantemos os níveis mais altos em sua forma original. Ainda economizamos algum tempo, principalmente reduzindo a quantidade de ramificações que estamos realizando.

Para alguma limpeza, o código agora está usando números inteiros não assinados e os corrige em 64 bits (caso alguém queira executar isso em uma arquitetura de 32 bits).

A aceleração geral está entre um fator de x3 e x4. N = 22 ainda precisa de mais de oito núcleos para rodar em menos de 10 minutos, mas em uma máquina de 64 núcleos agora é de cerca de quatro minutos (com numThreadsaumento de acordo). Não acho que haja muito mais espaço para melhorias sem um algoritmo diferente.

N = 22:

@[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

Atualizado novamente, fazendo uso de outras reduções possíveis no espaço de pesquisa. É executado em cerca de 9:49 minutos para N = 22 na minha máquina quadcore.

Atualização final (eu acho). Melhores classes de equivalência para opções de F, reduzindo o tempo de execução de N = 22 para 3:19 minutos e 57 segundos (editar: eu acidentalmente executei isso com apenas um thread) na minha máquina.

Essa alteração utiliza o fato de que um par de vetores produz os mesmos zeros à esquerda se um puder ser transformado no outro girando-o. Infelizmente, uma otimização de baixo nível bastante crítica exige que o bit superior de F na representação de bits seja sempre o mesmo e, ao usar essa equivalência, reduziu bastante o espaço de pesquisa e reduziu o tempo de execução em cerca de um quarto, usando um espaço de estado diferente redução em F, a sobrecarga de eliminar mais a otimização de baixo nível do que compensá-la. No entanto, verifica-se que esse problema pode ser eliminado considerando-se também o fato de que F que são inversos um do outro também são equivalentes. Embora isso tenha aumentado um pouco a complexidade do cálculo das classes de equivalência, ele também me permitiu manter a otimização de baixo nível mencionada, levando a uma aceleração de cerca de x3.

Mais uma atualização para oferecer suporte a números inteiros de 128 bits para os dados acumulados. Para compilar com 128 bit inteiros, você vai precisar longint.nimde aqui e para compilar com -d:use128bit. N = 24 ainda leva mais de 10 minutos, mas incluí o resultado abaixo para os interessados.

N = 24:

@[761152247121980686336, 122682715414070296576, 19793870419291799552, 3193295704340561920, 515628872377565184, 83289931274780672, 13484616786640896, 2191103969198080, 359662314586112, 60521536552960, 10893677035520, 2293940617216, 631498735616, 230983794688, 102068682752, 48748969984, 23993655296, 11932487680, 5955725312, 2975736832, 1487591936, 743737600, 371864192, 185931328, 92965664]

import math, locks, unsigned

when defined(use128bit):
  import longint
else:
  type int128 = uint64 # Fallback on unsupported architectures
  template toInt128(x: expr): expr = uint64(x)

const
  N = 22
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, uint64]
  ZeroCounterLong = array[0..M-1, int128]
  ComputeThread = TThread[int]
  Pair = tuple[value, weight: int32]

var
  leadingZeros: ZeroCounterLong
  lock: TLock
  innerProductTable: array[0..FMax, int8]
  zeroInnerProductList = newSeq[int32]()
  equiv: array[0..FMax, int32]
  fTable = newSeq[Pair]()

proc initInnerProductTables =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)
    if innerProductTable[i] == 0:
      if (i and 1) == 0:
        add(zeroInnerProductList, int32(i))

initInnerProductTables()

proc ror1(x: int): int {.inline.} =
  ((x shr 1) or (x shl (N-1))) and FMax

proc initEquivClasses =
  add(fTable, (0'i32, 1'i32))
  for i in 1..FMax:
    var r = i
    var found = false
    block loop:
      for j in 0..N-1:
        for m in [0, FMax]:
          if equiv[r xor m] != 0:
            fTable[equiv[r xor m]-1].weight += 1
            found = true
            break loop
        r = ror1(r)
    if not found:
      equiv[i] = int32(len(fTable)+1)
      add(fTable, (int32(i), 1'i32))

initEquivClasses()

when defined(gcc):
  const unrollDepth = 4
else:
  const unrollDepth = 4

proc search2(lz: var ZeroCounter, s0, f, w: int) =
  var s = s0
  for i in unrollDepth..M-1:
    lz[i] = lz[i] + uint64(w)
    s = s shr 1
    case innerProductTable[s xor f]
    of 0:
      # s = s + 0
    of -1:
      s = s + SStep
    else:
      return

template search(lz: var ZeroCounter, s, f, w, i: int) =
  when i < unrollDepth:
    lz[i] = lz[i] + uint64(w)
    if i < M-1:
      let s2 = s shr 1
      case innerProductTable[s2 xor f]
      of 0:
        search(lz, s2 + 0, f, w, i+1)
      of -1:
        search(lz, s2 + SStep, f, w, i+1)
      else:
        discard
  else:
    search2(lz, s, f, w)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for fi in countup(base, len(fTable)-1, numThreads):
    let (fp, w) = fTable[fi]
    let f = if (fp and (FSize div 2)) == 0: fp else: fp xor FMax
    for sp in zeroInnerProductList:
      let s = f xor sp
      search(lz, s, f, w, 0)
  acquire(lock)
  for i in 0..M-1:
    let t = lz[i].toInt128 shl (M-i).toInt128
    leadingZeros[i] = leadingZeros[i] + t
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

Java ( n=22?)

Penso que a maioria das respostas é melhor do que n=16usar uma abordagem semelhante a essa, embora elas diferem nas simetrias que exploram e na maneira como dividem a tarefa entre os threads.

Os vetores definidos na pergunta podem ser substituídos por cadeias de bits, e o produto interno com XOR na janela sobreposta e verificando se há exatamente os n/2bits definidos (e, portanto, os n/2bits limpos). Existem n! / ((n/2)!)(coeficiente binomial central) cadeias de nbits com n/2bits configurados (que eu chamo de cadeias balanceadas ); portanto, para qualquer dado dado, Fexistem muitas janelas Sque dão um produto interno nulo. Além disso, a ação de deslizar Sao longo de uma e verificar se ainda podemos encontrar um bit de entrada que dê um produto interno zero corresponde a procurar uma aresta em um gráfico cujos nós são as janelas e cujas arestas vinculam um nó ua um nó vcujos primeiros n-1bits são os últimosn-1pedaços de u.

Por exemplo, com n=6e F=001001obtemos este gráfico:

e para F=001011obtermos este gráfico:

Então precisamos contar para cada ia partir 0de nquantos caminhos de comprimento ihá, somando sobre os gráficos para cada F. Eu acho que a maioria de nós está usando a pesquisa profunda.

Observe que os gráficos são escassos: é fácil provar que cada nó possui um grau máximo de 1 e um grau máximo de um. Isso também significa que as únicas estruturas possíveis são cadeias simples e loops simples. Isso simplifica um pouco o DFS.

Exploro algumas simetrias: as seqüências balanceadas são fechadas sob bits inversos (a ~operação em vários idiomas da família ALGOL) e sob rotação de bits, para que possamos agrupar valores Frelacionados por essas operações e fazer apenas o DFS uma vez.

public class CodeGolf26459v8D implements Runnable {
    private static final int NUM_THREADS = 8;

    public static void main(String[] args) {
        v8D(22);
    }

    private static void v8D(int n) {
        int[] bk = new int[1 << n];
        int off = 0;
        for (int i = 0; i < bk.length; i++) {
            bk[i] = Integer.bitCount(i) == n/2 ? off++ : -1;
        }

        int[] fwd = new int[off];
        for (int i = 0; i < bk.length; i++) {
            if (bk[i] >= 0) fwd[bk[i]] = i;
        }

        CodeGolf26459v8D[] runners = new CodeGolf26459v8D[NUM_THREADS];
        Thread[] threads = new Thread[runners.length];
        for (int i = 0; i < runners.length; i++) {
            runners[i] = new CodeGolf26459v8D(n, i, runners.length, bk, fwd);
            threads[i] = new Thread(runners[i]);
            threads[i].start();
        }

        try {
            for (int i = 0; i < threads.length; i++) threads[i].join();
        }
        catch (InterruptedException ie) {
            throw new RuntimeException("This shouldn't be reachable", ie);
        }

        long surviving = ((long)fwd.length) << (n - 1);
        for (int i = 0; i <= n; i++) {
            for (CodeGolf26459v8D runner : runners) surviving -= runner.survival[i];
            System.out.print(i == 0 ? "[" : ", ");
            java.math.BigInteger result = new java.math.BigInteger(Long.toString(surviving));
            System.out.print(result.shiftLeft(n + 1 - i));
        }
        System.out.println("]");
    }

    public final int n;
    protected final int id;
    protected final int numRunners;
    private final int[] bk;
    private final int[] fwd;

    public long[] survival;

    public CodeGolf26459v8D(int n, int id, int numRunners, int[] bk, int[] fwd) {
        this.n = n;
        this.id = id;
        this.numRunners = numRunners;

        this.bk = bk;
        this.fwd = fwd;
    }

    private int dfs2(int[] graphShape, int flip, int i) {
        if (graphShape[i] != 0) return graphShape[i];

        int succ = flip ^ (fwd[i] << 1);
        if (succ >= bk.length) succ ^= bk.length + 1;

        int j = bk[succ];
        if (j == -1) return graphShape[i] = 1;

        graphShape[i] = n + 1; // To detect cycles
        return graphShape[i] = dfs2(graphShape, flip, j) + 1;
    }

    @Override
    public void run() {
        int n = this.n;
        int[] bk = this.bk;
        int[] fwd = this.fwd;

        // NB The initial count is approx 2^(2n - 1.33 - 0.5 lg n)
        // For n=18 we overflow 32-bit
        // 64-bit is good up to n=32.
        long[] survival = new long[n + 1];
        boolean[] visited = new boolean[1 << (n - 1)];
        int th = 0;
        for (int f = 0; f < visited.length; f++) {
            if (visited[f]) continue;

            int m = 1, g = f;
            while (true) {
                visited[g] = true;
                int ng = g << 1;
                if ((ng >> (n - 1)) != 0) ng ^= (1 << n) - 1;
                if (ng == f) break;
                m++;
                g = ng;
            }

            if (th++ % numRunners != id) continue;

            int[] graphShape = new int[fwd.length];
            int flip = (f << 1) ^ f;
            for (int i = 0; i < graphShape.length; i++) {
                int life = dfs2(graphShape, flip, i);
                if (life <= n) survival[life] += m;
            }
        }

        this.survival = survival;
    }
}

No meu Core 2 de 2,5 GHz, recebo

# n=18
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

real    0m3.131s
user    0m10.133s
sys     0m0.380s

# n=20
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

real    1m8.706s
user    4m20.980s
sys     0m0.564s

# n=22
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

real    20m10.654s
user    76m53.880s
sys     0m6.852s

Como o computador de Lembik possui 8 núcleos e executou meu programa de thread único anterior duas vezes mais rápido que o meu, estou otimista de que seja executado n=22em menos de 8 minutos.

C

É basicamente apenas uma implementação levemente otimizada do algoritmo na questão. Ele pode gerenciar n=12dentro do prazo.

#include <stdio.h>
#include <inttypes.h>

#define n 12
#define m (n + 1)

int main() {
    int i;
    uint64_t S, F, o[m] = {0};
    for (S = 0; S < (1LLU << (n + m - 1)); S += 2)
        for (F = 0; F < (1 << (n - 1)); F++)
            for (i = 0; i < m; i++)
                if (__builtin_popcount(((S >> i) & ((1 << n) - 1)) ^ F) == n >> 1)
                    o[i] += 4;
                else
                    break;
    for (i = 0; i < m; i++)
        printf("%" PRIu64 " ", o[i]);
    return 0;
}

Execução de teste para n=12, incluindo compilação:

$ clang -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall fast.c
$ time ./a.out 
15502147584 3497066496 792854528 179535872 41181184 9826304 2603008 883712 381952 177920 85504 42560 21280 
real    0m53.266s
user    0m53.042s
sys     0m0.068s
$

Comentário: Acabei de ligar meu cérebro e usei algumas combinatórias simples para calcular que o primeiro valor sempre será n! / ((n / 2)!)^2 * 2^(n + m - 1). Parece-me que deve haver uma solução completamente algébrica para esse problema.

Java, n=16

Para qualquer valor dado de, Fexistem \binom{n}{n/2}vetores que possuem um produto interno nulo. Assim, podemos construir um gráfico cujos vértices são os vetores correspondentes e cujas bordas correspondem à mudança de S, e então precisamos contar os caminhos de comprimento até no gráfico.

Eu não tentei microoptimizar isso substituindo condicionais por operações bit a bit, mas cada incremento duplo de naumenta o tempo de execução em cerca de 16 vezes, para que isso não faça diferença suficiente, a menos que eu esteja bem próximo do limite. Na minha máquina, não estou.

public class CodeGolf26459 {

    public static void main(String[] args) {
        v3(16);
    }

    // Order of 2^(2n-1) * n ops
    private static void v3(int n) {
        long[] counts = new long[n+1];
        int mask = (1 << n) - 1;
        for (int f = 0; f < (1 << (n-1)); f++) {
            // Find adjacencies
            long[] subcounts = new long[1 << n];
            for (int g = 0; g < (1 << n); g++) {
                subcounts[g] = Integer.bitCount(f ^ g) == n/2 ? 2 : -1;
            }

            for (int round = 0; round <= n; round++) {
                long count = 0;
                // Extend one bit.
                long[] next = new long[1 << n];
                for (int i = 0; i < (1 << n); i++) {
                    long s = subcounts[i];
                    if (s == -1) next[i] = -1;
                    else {
                        count += s;
                        int j = (i << 1) & mask;
                        if (subcounts[j] >= 0) next[j] += s;
                        if (subcounts[j + 1] >= 0) next[j + 1] += s;
                    }
                }
                counts[round] += count << (n - round);
                subcounts = next;
            }
        }

        System.out.print("[");
        for (long count : counts) System.out.print(count+", ");
        System.out.println("]");
    }
}

No meu Core 2 de 2,5 GHz, recebo

$ javac CodeGolf26459.java && time java -server CodeGolf26459 
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600, ]

real    6m2.663s
user    6m4.631s
sys     0m1.580s

RPython, N = 22 ~ 3: 23

Multiencadeado, usando uma descida recursiva sem pilha. O programa aceita dois argumentos de linha de comando: N e o número de threads de trabalho.

from time import sleep

from rpython.rlib.rthread import start_new_thread, allocate_lock
from rpython.rlib.rarithmetic import r_int64, build_int, widen
from rpython.rlib.rbigint import rbigint

r_int8 = build_int('r_char', True, 8)

class ThreadEnv:
  __slots__ = ['n', 'counts', 'num_threads',
               'v_range', 'v_num', 'running', 'lock']

  def __init__(self):
    self.n = 0
    self.counts = [rbigint.fromint(0)]
    self.num_threads = 0
    self.v_range = [0]
    self.v_num = 0
    self.running = 0
    self.lock = None

env = ThreadEnv()

bt_bits = 12
bt_mask = (1<<bt_bits)-1
# computed compile time
bit_table = [r_int8(0)]
for i in xrange(1,1<<bt_bits):
  bit_table += [((i&1)<<1) + bit_table[i>>1]]

def main(argv):
  argc = len(argv)
  if argc < 2 or argc > 3:
    print 'Usage: %s N [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 3:
    env.num_threads = int(argv[2])
  else:
    env.num_threads = 2

  env.n = int(argv[1])
  env.counts = [rbigint.fromint(0)]*env.n
  env.lock = allocate_lock()

  v_range = []
  v_max = 1<<(env.n-1)
  v_num = 0
  v = (1<<(env.n>>1))-1
  while v < v_max:
    v_num += 1
    v_range += [v]
    if v&1:
      # special case odd v
      s = (v+1)&-v
      v ^= s|(s>>1)
    else:
      s = v&-v
      r = v+s
      # s is at least 2, skip two iterations
      i = 3
      s >>= 2
      while s:
        i += 1
        s >>= 1
      v = r|((v^r)>>i)
  env.v_range = v_range
  env.v_num = v_num

  for i in xrange(env.num_threads-1):
    start_new_thread(run,())

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.05)

  result = []
  for i in range(env.n):
    result += [env.counts[i].lshift(env.n-i+3).str()]
  result += [env.counts[env.n-1].lshift(3).str()]
  print result
  return 0

def run():
  with env.lock:
    v_start = env.running
    env.running += 1

  n = env.n
  counts = [r_int64(0)]*n
  mask = (1<<n)-1
  v_range = env.v_range
  v_num = env.v_num
  z_count = 1<<(n-2)

  for i in xrange(v_start, v_num, env.num_threads):
    v = v_range[i]
    counts[0] += z_count
    counts[1] += v_num
    r = v^(v<<1)
    for w in v_range:
      # unroll counts[2] for speed
      # ideally, we could loop over x directly,
      # rather than over all v, only to throw the majority away
      # there's a 2x-3x speed improvement to be had here...
      x = w^r
      if widen(bit_table[x>>bt_bits]) + widen(bit_table[x&bt_mask]) == n:
        counts[2] += 1
        x, y = v, x
        o, k = 2, 3
        while k < n:
          # x = F ^ S
          # y = F ^ (S<<1)
          o = k
          z = (((x^y)<<1)^y)&mask
          # z is now F ^ (S<<2), possibly xor 1
          # what S and F actually are is of no consequence

          # the compiler hint `widen` let's the translator know
          # to store the result as a native int, rather than a signed char
          bt_high = widen(bit_table[z>>bt_bits])
          if bt_high + widen(bit_table[z&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z
            k += 1
          elif bt_high + widen(bit_table[(z^1)&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z^1
            k += 1
          else: k = n

  with env.lock:
    for i in xrange(n):
      env.counts[i] = env.counts[i].add(rbigint.fromrarith_int(counts[i]))
    env.running -= 1

def target(*args):
  return main, None

Compilar

Crie um clone local do repositório PyPy usando mercurial, git ou o que você preferir. Digite o seguinte encantamento (assumindo que o script acima tenha o nome convolution-high.py):

$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution-high.py

onde %PYPY_REPO%representa uma variável de ambiente apontando para o repositório que você acabou de clonar. A compilação leva cerca de um minuto.

Exemplo de tempos

N = 16, 4 threads:

$ timeit convolution-high-c 16 4
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]
Elapsed Time:     0:00:00.109
Process Time:     0:00:00.390

N = 18, 4 threads:

$ timeit convolution-high-c 18 4
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]
Elapsed Time:     0:00:01.250
Process Time:     0:00:04.937

N = 20, 4 threads:

$ timeit convolution-high-c 20 4
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]
Elapsed Time:     0:00:15.531
Process Time:     0:01:01.328

N = 22, 4 threads:

$ timeit convolution-high-c 22 4
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
Elapsed Time:     0:03:23.156
Process Time:     0:13:25.437

Python 3.3, N = 20, 3.5min

Isenção de responsabilidade: minha intenção não é postar isso como minha própria resposta, pois o algoritmo que estou usando é apenas uma porta sem vergonha da solução RPython do primo . Meu objetivo aqui é apenas mostrar o que você pode fazer em Python se você combinar a mágica dos módulos Numpy e Numba .

Numba explicou resumidamente:

O Numba é um compilador especializado just-in-time que compila código Python e NumPy anotado no LLVM (através de decoradores). http://numba.pydata.org/

Atualização 1 : notei que, depois de lançar os números, podemos simplesmente pular alguns deles completamente. Então agora maxf torna-se (1 << n) // 2 e maxs torna-se maxf 2 **. Isso irá acelerar bastante o processo. n = 16 agora leva apenas ~ 48s (abaixo de 4,5min). Eu também tenho uma outra idéia que vou tentar e ver se consigo fazê-lo um pouco mais rápido.

Atualização 2: algoritmo alterado (solução do primo). Embora minha porta ainda não suporte multithreading, é bastante simples de adicionar. É ainda possível liberar o CPython GIL usando Numba e ctypes. Esta solução, no entanto, também é executada muito rapidamente em núcleo único!

import numpy as np
import numba as nb

bt_bits = 11
bt_mask = (1 << bt_bits) - 1
bit_table = np.zeros(1 << bt_bits, np.int32)

for i in range(0, 1 << bt_bits):
    bit_table[i] = ((i & 1) << 1) + bit_table[i >> 1]

@nb.njit("void(int32, int32, int32, int32, int64[:], int64[:])")
def run(n, m, start, re, counts, result):
    mask = (1 << n) - 1

    v_max = (1 << n) // 2
    rr = v_max // 2

    v = (1 << (n >> 1)) - 1
    while v < v_max:
        s = start

        while s < rr:
            f = v ^ s
            counts[0] += 8
            t = s << 1
            o, j = 0, 1

            while o < j and j < m:
                o = j
                w = (t ^ f) & mask
                bt_high = bit_table[w >> bt_bits]

                if bt_high + bit_table[w & bt_mask] == n:
                    counts[j] += 8
                    t <<= 1
                    j += 1
                elif bt_high + bit_table[(w ^ 1) & bt_mask] == n:
                    counts[j] += 8
                    t = (t | 1) << 1
                    j += 1
                    s += re

            s = v & -v
            r = v + s
            o = v ^ r
            o = (o >> 2) // s
            v = r | o

    for e in range(m):
        result[e] += counts[e] << (n - e)

E finalmente:

if __name__ == "__main__":
    n = 20
    m = n + 1

    result = np.zeros(m, np.int64)
    counts = np.zeros(m, np.int64)

    s1 = time.time() * 1000
    run(n, m, 0, 1, counts, result)
    s2 = time.time() * 1000

    print(result)
    print("{0}ms".format(s2 - s1))

Isso funciona na minha máquina em 212688ms ou ~ 3,5min.

C ++ N = 16

Estou testando em um EEEPC com um átomo .. meu tempo não faz muito sentido. : D
O átomo resolve n = 14 em 34 segundos. E n = 16 em 20 minutos. Quero testar n = 16 no OP pc. Eu sou otimista.

A idéia é que toda vez que encontramos uma solução para um dado F, encontramos uma solução 2 ^ i porque podemos alterar a parte inferior de S, levando ao mesmo resultado.

#include <stdio.h>
#include <cinttypes>
#include <cstring>

int main()
{
   const int n = 16;
   const int m = n + 1;
   const uint64_t maxS = 1ULL << (2*n);
   const uint64_t maxF = 1ULL << n;
   const uint64_t mask = (1ULL << n)-1;
   uint64_t out[m]={0};
   uint64_t temp[m] = {0};
   for( uint64_t F = 0; F < maxF; ++F )
   {
      for( uint64_t S = 0; S < maxS; ++S )
      {
         int numSolution = 1;
         for( int i = n; i >= 0; --i )
         {
            const uint64_t window = S >> i;
            if( __builtin_popcount( mask & (window ^ F) ) == (n / 2) )
            {
               temp[i] += 1;
            } else {
               numSolution = 1 << i;
               S += numSolution - 1;
               break;
            }
         }
         for( int i = n; i >= 0; --i )
         {
            out[i] += temp[i]*numSolution;
            temp[i] = 0;
         }
      }
   }
   for( int i = n; i >= 0; --i )
   {
      uint64_t x = out[i];
      printf( "%lu ", x );
   }
   return 0;
}

compilar:

gcc 26459.cpp -std = c ++ 11 -O3 -march = nativo-restrito-alias--ftree-vectorize -Wall -pedantic -o 26459

JAVASCRIPT n: 12

No meu computador, foram necessários 231,242 segundos. Na demonstração, estou usando trabalhadores da web para evitar o congelamento do navegador. Isso com certeza pode ser melhorado com trabalhadores paralelos. Eu sei que JS não tem chance nesse desafio, mas eu fiz isso por diversão!

Clique para executar a demonstração online

var n = 8;        
var m = n + 1;
var o = [];
var popCount = function(bits) {
  var SK5  = 0x55555555,
      SK3  = 0x33333333,
      SKF0 = 0x0f0f0f0f,
      SKFF = 0xff00ff;

  bits -= (bits >> 1) & SK5;
  bits  = (bits & SK3) + ((bits >> 2) & SK3);
  bits  = (bits & SKF0) + ((bits >> 4) & SKF0);
  bits += bits >> 8;

  return (bits + (bits >> 15)) & 63;
};
for(var S = 0; S < (1 << n + m - 1); S += 2){
  for(var F = 0; F < (1 << n - 1); F += 1){
    for (var i = 0; i < m; i++){
      var c = popCount(((S >> i) & ((1 << n) - 1)) ^ F);
      if(c == n >> 1){
        if(!o[i]) o[i] = 0;
        o[i] += 4;
      } else break;
    }
  }
}
return o;

Fortran: n = 12

Acabei de fazer uma versão rápida no Fortran, sem otimizações, exceto o OpenMP. Ele deve se espremer em pouco menos de 10 minutos para n = 12 na máquina OP, leva 10:39 na minha máquina, que é levemente mais lenta.

Inteiros de 64 bits têm um impacto negativo no desempenho; acho que eu teria que repensar todo o algoritmo para que isso seja muito mais rápido. Não sei se vou me incomodar, acho que prefiro passar algum tempo pensando em um bom desafio que seja mais do meu próprio gosto. Se alguém quiser pegar isso e continuar com isso, vá em frente :)

program golf
use iso_fortran_env
implicit none
integer, parameter ::  n=12
integer :: F(n), S(2*n)
integer(int64) :: leadingzerocounts(n+1)
integer :: k
integer(int64) :: i,j,bindec,enc

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,2**(2*n)-1
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=2*n,1,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j)=1
      enc=enc-bindec
    else
      S(j)=-1
    endif
  end do
  do j=0,2**(n)-1
    ! Convert j into the array F with -1s and 1s
    enc=j
    do k=n,1,-1
      bindec=2**(k-1)
      if (enc-bindec .ge. 0) then
        F(k)=1
        enc=enc-bindec
      else
        F(k)=-1
      endif
    end do
    ! Compute dot product   
    do k=1,n+1
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end

Lua: n = 16

Isenção de responsabilidade: minha intenção NÃO é postar isso como minha própria resposta, pois o algoritmo que estou usando é descaradamente roubado da resposta inteligente de Anna Jokela . que foi descaradamente roubado da resposta inteligente de ilmale .

Além disso, nem é válido - possui imprecisões causadas por números de ponto flutuante (seria melhor se Lua suportasse números inteiros de 64 bits). No entanto, ainda estou carregando, apenas para mostrar a rapidez com que esta solução é. É uma linguagem de programação dinâmica, e ainda assim eu posso calcular n = 16 em tempo razoável (1 minuto na CPU de 800 MHz).

Execute com LuaJIT, o intérprete padrão está muito lento.

local bit = require "bit"
local band = bit.band
local bor = bit.bor
local bxor = bit.bxor
local lshift = bit.lshift
local rshift = bit.rshift

-- http://stackoverflow.com/a/11283689/736054
local function pop_count(w)
    local b1 = 1431655765
    local b2 = 858993459
    local b3 = 252645135
    local b7 = 63

    w = band(rshift(w, 1), b1) + band(w, b1)
    w = band(rshift(w, 2), b2) + band(w, b2)
    w = band(w + rshift(w, 4), b3)
    return band(rshift(w, 24) + rshift(w, 16) + rshift(w, 8) + w, b7)
end

local function gen_array(n, value)
    value = value or 0
    array = {}
    for i = 1, n do
        array[i] = value
    end
    return array
end

local n = 16
local u = math.floor(n / 2)
local m = n + 1
local maxf = math.floor(lshift(1, n) / 2)
local maxs = maxf ^ 2
local mask = lshift(1, n) - 1

local out = gen_array(m, 0)
local temp = gen_array(m, 0)


for f = 0, maxf do
    local s = 0
    while s <= maxs do
        local num_solution = 1

        for i = n, 0, -1 do
            if pop_count(band(mask, bxor(rshift(s, i), f))) == u then
                temp[i + 1] = temp[i + 1] + 8
            else
                num_solution = lshift(1, i)
                s = s + num_solution - 1
                break
            end
        end

        for i = 1, m do
            out[i] = out[i] + temp[i] * num_solution
            temp[i] = 0
        end

        s = s + 1
    end
end

for i = m, 1, -1 do
    print(out[i])
end