text:
How Slow Is Python Really (Part II)?
This is a follow up to How slow is Python really? (Or how fast is your language?).
It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the challenge but want something harder where they can really use their low level skills, here is part II.  The challenge is to get a x100 speedup for the following python code as tested on my computer.
To make it more difficult I am using pypy this time. The current timing for me is 1 minute and 7 seconds using pypy 2.2.1.
Rules

The first person to submit code which I can run, is correct and is x100 times faster on my machine will be awarded a bounty of 50 points.
I will award the win to the fastest code after a week.

import itertools
import operator
import random

n = 8
m  = 8
iters = 1000

# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m

# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
#   itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
#   itertools.product("AB", repeat=5) --> [
#    ('A', 'A', 'A', 'A', 'A'),
#    ('A', 'A', 'A', 'A', 'B'),
#    ('A', 'A', 'A', 'B', 'A'),
#    ('A', 'A', 'A', 'B', 'B'),
#    etc.
#   ]
for S in itertools.product([-1,1], repeat = n+m-1):
    for i in xrange(iters):
        F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        # if the array is made up of only zeros keep recreating it until
        # there is at least one nonzero value.
        while not any(F):
            F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        j = 0
        while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
            leadingzerocounts[j] +=1
            j += 1
print leadingzerocounts

The output should be similar to
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]

You must use a random seed in your code and any random number generator that is good enough to give answers close to the above will be accepted.
My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.
Explanation of code
This code iterates over all arrays S of length n+m-1 that are made up for -1s and 1s. For each array S it samples 1000 non-zero random arrays F of length n made up of -1,0 or 1 with probability of 1/4, 1/2,/14 of taking each values. It then computes the inner products between F and each window of S of length n until it finds a non-zero inner product. It adds 1 to leadingzerocounts at each position it found a zero inner product.
Status

Perl. 2.7 times slowdown by @tobyink. (Compared to pypy not cpython.)
J. 39 times speedup by @Eelvex.
C. 59 times speed up  by @ace.
Julia. 197 times faster not including start up time by @one-more-minute. 8.5 times speed up including start up time (it's faster using 4 processors in this case than 8).
Fortran. 438 times speed up by @semi-extrinsic.
Rpython. 258 times speed up by @primo.
C++. 508 times speed up by @ilmale.

(I stopped timing the new improvements because they are too fast and iters was too small.)

It was pointed out that timings below a second are unreliable and also some languages have a start-up cost. The argument is that if you are to include that you should also include the compilation time of C/C++ etc. Here are the timings for the fastest code with the number of iterations increased to 100,000.

Julia. 42 seconds by @one-more-minute.
C++. 14 seconds by @GuySirton.
Fortran. 14s by @semi-extrinsic.
C++. 12s by @ilmale.
Rpython. 18s by @primo.
C++. 5s by @Stefan.

The winner is.. Stefan!
Follow-up challenge posted. How high can you go? (A coding+algorithms challenge) . This one is  harder.

an explanation of what the code is suppose to achieve would be nice, so we can rewrite it and not simply port it

@Einacio Does the explanation I just added help?

Are you sure that the while loop is right? I'm not proficient in python, but it looks to me that the code would not increment i if the inner product is non-zero.

@KyleKanos That's right. It stops at the first non-zero inner product. Oh I should change the variable name!

"The first person to submit code which I can run, is correct and is x100 times faster on my machine wins immediately and the competition closes." What is the purpose of closing the competition like that? Why not use a date deadline like most others, so we can see it furthered reduced in other languages?

@grovesNL It was just to try to make it more interesting! I also think it's going to be very hard so there is a good chance no one will get over that particular hurdle.

@Lembik to make it interesting you could set up a bounty to be granted at the end of the first week, but still change the accepted answers after that if it is beaten

@Einacio That is a nice idea. I changed the rules which I hope no one will mind.

Perhaps I'm misunderstanding what is supposed to happen when it finds a non-zero inner product, but why are the values in the array decreasing? Shouldn't each value in leadingzerocounts be similar?

@grovesNL leadingzerocounts counts the number of times you can get that far before seeing a non-zero inner product basically. So you expect it to be less likely to get further.

Come to think of it... I think there might be significant mileage in noticing that it is very wasteful to produce all these arrays of length n+m-1 when most of the time the right hand ends of them are never used.

Are "slight" algorithmic changes allowed?

@Eelvex If it's computing exactly the same thing mathematically you can change the algorithm any way you like.

Take the fastest C compatible solution, 2. wrap it as a CPython C extension, 3. profit?

I think the OP should clarify two things:

should timings include everything for JIT languages? Compare the Julia answers below.
I think "any RNG that is good enough to give answers close to the above" is a very poor metric for specifying RNG quality. Could you be more specific? Is the xorshift one, used in some answers, allowed? Wikipedia notes "The xorshift generators have been shown to be fast but not reliable."

I will also add these two comments from Nick Maclaren at the Cambridge Centre for Scientific Computing:
"Nobody should EVER use 32-bit random number generators for more than about ten
million numbers in a row without careful analysis"
"No Xorshift generator is good enough to use on its own, because they have some evil properties."

@semi-extrinsic I think it is too late for me to change the rules wrt the RNG. I will compare the outputs for different values of n to that the python code gives. If it is very close I will accept the code.  The timings should include everything for JIT languages.  I will post another competition in a couple of days where the timings won't be <1 second which will help Julia people.

Yes, timings of below 1 second is another issue, they are usually not very reliable. Random numbers are hard to get right though, it's a common problem in computational physics that people use RNGs with poor properties. The "trick" of using one 32 bit random int to give many random bits is also very much frowned upon.

@semi-extrinsic I can assure you my next puzzle will not be solved in <1 second :)

@Lembik Startup time and performance are separate issues, and should be considered separately. I encourage you to either reconsider excluding boot time, or rename this question to "How quickly does your language boot up?". For the faster solutions that's all you're measuring.

@one-more-minute There is no boot-up time with compiled languages. The performance difference between the C++ solution and the one I just posted in Fortran is not due to start-up time (zero in both cases) but because in C++ he can easily compute just one random integer and convert this to 15 instances of (-1, 0 or +1). I have to create 15 random integers. I tried doing it his way, but couldn't find a solution with low enough overhead :(

@semi-extrinsic Exactly, so including boot time means  restricting the competition to precompiled languages for no real reason. I'm not saying startup time is never important, but in this case it's obscuring what's actually interesting – run time performance and techniques to improve it.

Why do you declare firstzero and bothzero? They don't seem to be used

@one-more-minute I completely agree that a problem should be set where even the fastest solutions take more than a minute. Even C++ and Fortran timings are starting to be a little dubious at below 1 second.

@Lembik perhaps faster solutions should use 10,000 iterations, so that times are back in the minute range? Then you'd just divide them by 10.

@Lembik I gave up, I was trying this in Go but the missing bits and pieces were just too many and things became confusing when I tried to implement them myself:S. Having done work in python NLTK I honestly miss the existing tools in the language :(

@one-more-minute Basically having timings under a second makes everything unsatisfactory. This is something I have learned. You can't just repeat 10,000 times as a smart compiler will just eliminate those repeats. You have to actually output something different in each iteration and that needs a carefully thought through spec.

@Lembik I'm not sure I understand – if you set iters=10,000 in your original code, that will fairly straightforwardly make it run 10x longer, no? There's no compiler that could or would optimise those loops away.

Oh I misunderstood! Yes that would work.

@Lembik Would you mind timing mine again?  Make sure you're compiling with optimizations on.  There was also an additional flag needed to get the threads going on Linux (and check to see your 8 cores aren't busy)...

@GuySirton Done.  I must be losing track of which code has which compiler flags.  Thanks.

@Lembik I've improved my Fortran version, making it 2x faster again on my machine. Could you time it again? :)

@semi-extrinsic Done.

If you are counting C / C++ compilation times, you should also count Java compilation times. Also this is about the fastest code, not about the fastest compiler...

@JeroenBollen Actually I didn't count either but you would be right had I done so.

It has been very interesting to follow. It is a pity that this coding challenge included random numbers (PRNGs) and moreover without any rules about their quality. This is more a library issue than of programming languages and this has made the results much less comparable and interesting.

C++ bit magic
~16ms multithreaded, 56ms singlethreaded. ~4000 speedup.
(speedup is based on multithreaded code on my i7-2820QM and the 1 min 9 seconds mentioned in the question. Since the OP's system has worse single threaded performance than my CPU but better multi threaded perfiormance i expect this number to be accurate)
The multithreaded part is quite inefficient due to the spawning of threads. I could probably do better by leveraging my custom job library but that one has bugs under unix systems.. For an explanation and almost identical code without threading refer to https://codegolf.stackexchange.com/a/26485/20965.
edit
I gave each thread it's own RNG and cut down the bit length to 32 which reduced the runtime by a few ms.
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <array>
#include <tuple>
#include <memory>
#include <thread>
#include <future>
#include <string.h>

#ifdef _MSC_VER
uint32_t popcnt( uint32_t x ){ return _mm_popcnt_u32(x); }
#else
uint32_t popcnt( uint32_t x ){ return __builtin_popcount(x); }
#endif

void convolve()
{
    static const unsigned threadCount = 32;
    static const unsigned n = 8;
    static const unsigned m = 8;
    static const unsigned totalIters = 1000;
    static_assert( n <= 16, "packing of F fails when n > 16.");
    static uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;

    std::array< uint32_t, m * threadCount > out;
    std::vector< std::future<void> > threads;

    for( int threadId = 0; threadId < threadCount; threadId++)
    {
        threads.emplace_back( std::async( [&, threadId]
        {
            std::random_device rd;
            std::knuth_b gen(rd());
            uint32_t nextRandomNumber = gen();

            const unsigned iters = totalIters / threadCount;

            std::array< uint32_t, m > leadingZeros;
            for( auto& x : leadingZeros )
                x = 0;

            for( unsigned i = 0; i < iters; i++ )
            {
                // generate random bit mess
                uint32_t F;
                do {
                    // this funky looking construction shortens the dependancy chain of F
                    F = nextRandomNumber & fmask;
                    nextRandomNumber = gen();
                } while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );

                // Assume F is an array with interleaved elements such that F[0] || F[16] is one element
                // here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
                // and  ~MSB(F) & LSB(F) returns 1 for all elements that are negative
                // this results in the distribution ( -1, 0, 0, 1 )
                // to ease calculations we generate r = LSB(F) and l = MSB(F)

                uint32_t r = F % ( 1 << n );
                // modulo is required because the behaviour of the leftmost bit is implementation defined
                uint32_t l = ( F >> 16 ) % ( 1 << n );

                uint32_t posBits = l & ~r;
                uint32_t negBits = ~l & r;
                assert( (posBits & negBits) == 0 );

                uint32_t mask = posBits | negBits;
                uint32_t totalBits = popcnt( mask );
                // if the amount of -1 and +1's is uneven, sum(S*F) cannot possibly evaluate to 0
                if ( totalBits & 1 )
                    continue;

                uint32_t adjF = posBits & ~negBits;
                uint32_t desiredBits = totalBits / 2;

                uint32_t S = (1 << (n + m -1));
                // generate all possible N+1 bit strings
                // 1 = +1
                // 0 = -1
                while ( S-- )
                {
                    for( int shift = 0; shift < m; shift++ )
                    {
                        uint32_t s = (S >> shift) % ( 1 << n );
                        auto firstBits = (s & mask) ^ adjF;

                        if ( desiredBits == popcnt( firstBits ) )
                        {
                            leadingZeros[shift] = leadingZeros[shift] + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }

            memcpy( out.data() + (threadId * m), leadingZeros.data(), sizeof( leadingZeros[0] ) * m );
        } ));

    };

    std::array< uint32_t, m > leadingZeros;
    for( auto& x : leadingZeros )
        x = 0;

    for( auto& thread : threads )
    {
        thread.wait();
    }

    for( int i = 0; i < (threadCount * m); i++ )
    {
        leadingZeros[i % m] += out[i];
    }

    for( auto x : leadingZeros )
        std::cout << x << ", ";

    std::cout << std::endl;
}

int main()
{
    typedef std::chrono::high_resolution_clock clock;
    int rounds = 100;

    // do some rounds to get the cpu up to speed..
    for( int i = 0; i < rounds / 10; i++ )
    {
        convolve();
    }

    auto start = clock::now();

    for( int i = 0; i < rounds; i++ )
        convolve();

    auto end = clock::now();
    double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;

    std::cout << seconds/rounds*1000 << " msec/round" << std::endl;

    return 0;
}

Sample output:
   6317312, 2515072, 1034368, 434048, 190144, 85200, 39804, 19168,
   6226944, 2481408, 1031168, 438080, 192896, 86816, 40484, 19490,
   6321152, 2524672, 1045376, 442880, 195680, 88464, 41656, 20212,
   6330624, 2517504, 1031104, 430208, 187696, 83976, 38976, 18708,
   6304768, 2510336, 1030720, 433056, 190880, 86824, 40940, 19840,
   6272512, 2494720, 1028160, 432352, 189168, 84752, 39540, 19052,
   6233600, 2507520, 1046912, 447008, 198224, 89984, 42092, 20292,

The output isn't right I think, maybe there is a bug? Compare to what is in the question. In particular the last column should be a number close to 19180.

@Lembik i can see what you mean. I think that the random output is not random enough which creates funky output sometimes. With the C++11 random generator it works fine. I'll fix the code later today.

I get Stefan.cpp:104:101: error: ‘memcpy’ was not declared in this scope
memcpy( out.data() + (threadId * m), leadingZeros.data(), sizeof( leadingZeros[0] ) * m );

I think that i need to include string.h. Try it again.

You compile this with g++ -O3 -std=c++0x -pthread -Wl,--no-as-needed Stefan.cpp -o Stefan

I tried it with totalIters=100,000 and surprisingly it took 13s. What do you get?

That is because without the -mpopcnt flag GCC generates an __popcountdi2 library call instead of the popcntl SSE4 instruction, which does exactly the same thing except in 1 clock cycle instead of 20. On my (not too fast) linx server i get around 4 seconds with one core as soon as i add -mpopcnt with 100.000 iters and 60ms with 1000 iters. I'm not sure about the crash, it works fine on all my systems. On a side note, i find your previous challenge much more interesting than this and the next one. Try to think of something new next time :)

g++ -O3 -std=c++0x -pthread -Wl,--no-as-needed -mpopcnt Stefan.cpp -o Stefan  now gives 5 seconds. Thanks. The crash was before I understood the right compile options.

"
The multithreaded part is quite inefficient due to the spawning of threads. I could probably do better by leveraging my custom just library but that one has bugs under unix systems" -- Can you post some info about your library? I'd love to see some threading stuff for Windows

@over i meant to say job library... i used https://github.com/id-Software/DOOM-3-BFG/blob/master/neo/idlib/ParallelJobList.h as an example. It's possible to make it almost lock free, which leads to good performance even when the individual jobs are small.

C++ x150 x450 x530
Instead of array I used bits (and dark magic).
Thanks @ace for the faster random function.
How does it work:
the first 15th bits of the integer s represent the array S[15]; the zeroes represent -1, the ones represent +1.
The array F is build in a similar way. But with two bit for each symbol.

00 represent -1
01 and 10 represent 0
11 represent 1

Cause S and F have a different representation I have to interleave S with itself to be comparable with F.

0 (-1) became 00 (-1 in the representation of F)
1 (+1) became 11 (+1 in the representation of F)

Now we can simply use Carnot to compute the inner product.
Remember that one variable can only assume value 00 or 11
0 . 00 = 11 (-1 * -1 = +1)
0 . 01 = 10 (-1 *  0 =  0)
0 . 10 = 01 (-1 *  0 =  0)
0 . 11 = 00 (-1 * +1 = -1)
1 . 00 = 00 (+1 * -1 = -1)
1 . 10 = 10 (+1 *  0 =  0)
1 . 01 = 01 (+1 *  0 =  0)
1 . 11 = 11 (+1 * +1 = +1)
Looks like a not xor to me. :)
Sum the ones is just a game of shift and mask, nothing really complex.
#include <array>
#include <ctime>

// From standford bithacks
// http://graphics.stanford.edu/~seander/bithacks.html
inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   static int b[] = { 1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

inline int32_t sumArray(int32_t v)
{
   static int b[] = { -1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

uint32_t x, y = 24252, z=57768, w=1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x<<1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   std::array<int, 8> leadingZero{0};
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for(int s = 0; s < maxS; ++s)
   {
      const int32_t x = interleaveBit(s);
      for(int i = 0; i < 1000; ++i)
      {
         int32_t random;
         do
         {
            random = 0xFFFF & myRand();
         }while(sumOnes(random) == 0);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j*2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if(sumArray(l) == 0)
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }

      }
   }
   for(int i = 7; i >= 0; --i)
   {
      printf("%d ", leadingZero[i]);
   }
   printf("\n");
   return 0;
}

Here a sample output:
6332350 2525218 1041716 438741 192917 87159 41023 19908

real 0m0.372s
user 0m0.371s
sys  0m0.001s

The program has been compiled with:
gcc -std=c++11 -O3 -msse4.2 -Wall -lstdc++ 26371.cpp -o fastPy

on Fedora 20 with gcc 4.8.2
The Cpu is a i7 8core.
Probably I can gain some ms tweaking compiler parameters.
While this is the OP solution time on my machine:
time pypy 26371.py
[6330609, 2523914, 1040885, 439303, 192708, 86987, 40710, 19498]

real 0m53.061s
user 0m53.016s
sys  0m0.022s

Edit:
Just adding openmp and change the order of the for I have a x3 gain, leading to a x450 performance improvement against OP code. :D
In this case the leadingZero array must be atomic. The random global... are random, they will be more random.
 #pragma omp parallel for
 for(int i = 0; i < 1000; ++i)
 {
    int32_t random;
    do
    {
       random = 0xFFFF & myRand();
    }while(sumOnes(random) == 0);
    for(int s = 0; s < maxS; ++s)
    {
       const int32_t x = interleaveBit(s);
       int j = 7;
       while( j >= 0 )
       {
          const int32_t h = (x >> (j*2));
          const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
          if( sumArray(l) == 0 )
          {
             leadingZero[j]++;
          } else
          {
             break;
          }
          j--;
       }
    }
 }

need to add -fopenmp to the compiler flag

Edit:2
As suggester by user71404 I changed the sumOnes and sumArray functions and now it's uber fast.
real  0m0.101s
user  0m0.101s
sys   0m0.000s

With openmp is slower, cause the atomics add too much overhead.
real  0m0.253s
user  0m1.870s
sys   0m0.001s

Without atomics is even faster, but I get wrong result.
2137992 1147218 619297 321243 155815 70946 32919 15579
real   0m0.048s
user   0m0.338s
sys    0m0.001s

To understand sumArray consider that 16 bit represent and array of 8 numbers.
00 have no 1 and represent -1
01 and 10 have one 1 and represent 0
11 have two 1s and represent 1
So that built-in count the number of bit set to 1 [http://en.wikipedia.org/wiki/Hamming_weight] and to each group we remove 1. Cool.
sumOnes is just black magic.
Here the latest compile flags and code.
gcc -std=c++11 -mfpmath=sse -O3 -flto -march=native -funroll-loops -Wall -lstdc++
#include <cstdint>
#include <cstdio>
#include <ctime>

inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   /* 0xAAAA == 0b1010 1010 1010 1010 */
   return !!(0xAAAA & (v ^ ~(v << 1)));
}

inline int32_t sumArray(int32_t v)
{
   return __builtin_popcount(v) - 8;
}

uint32_t x, y = 24252, z = 57768, w = 1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x << 1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   int leadingZero[8] = { 0 };
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for( int i = 0; i < 1000; ++i )
   {
      int32_t random;
      do
      {
         random = 0xFFFF & myRand();
      } while(sumOnes(random) == 0 );
      for( int s = 0; s < maxS; ++s )
      {
         const int32_t x = interleaveBit(s);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j * 2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if( sumArray(l) == 0 )
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }
      }
   }
   printf("[%d, %d, %d, %d, %d, %d, %d, %d]\n",
      leadingZero[7], leadingZero[6],
      leadingZero[5], leadingZero[4],
      leadingZero[3], leadingZero[2],
      leadingZero[1], leadingZero[0]);
   return 0;
}

Now I can't wait to test this! Sadly this won't be for a few hours.

The following was in a suggested edit, but I think that it may fit better as a comment.  You can replace your sumOnes, sumArray with the following (seems to give me a 2x speed up over the openmp version).
`inline int32_t sumOnes(int32_t v)
{
/* 0xAAAA == 0b1010 1010 1010 1010 */
return !! (0xAAAA & (v ^ ~(v << 1)));
}
inline int32_t sumArray(int32_t v)
{
return __builtin_popcount(v) - 8;
}` this was suggested by @user71404

@user71404: profiler said that the program spent all it's time in those two functions, but I was really tired yesterday think something better that that. I'll try this evening (UTC). Thanks.

Would you mind changing the second code snippet to be the full copy and pastable code? I must be doing something wrong in my attempts to get your openmp code working so this would help a lot.

Nice.  I thought this could be done with bit operations.

I understood sumOnes. If the group have same bit (11 or 00) they will set to zero.

Just to add a note: if I remove the final printf it take 0.001s to run. :D

@ilmale Is that because everything is optimized away? That won't count ;-)

Maybe this should be submitted in the C category? ;-)

I started with C++ in mind.. then I found that I can solve with bit trick. bitset didn't seems a good solution for really high speed. That's why I like C++, you can use really low level stuff when you need them.

Julia: 0.7s, 120x faster
As user20768 demonstrated, a straightforward port of the code to Julia is about twice as fast as PyPy. But we can do a lot better than that.
function pleadingzerocounts(; n = 8,
                              m = 8,
                              iters = 1000)
  @parallel (+) for S = 1:2^(8+8-1)
    leading_counts = zeros(Int, m)
    F = Array(Int, n)
    for i = 1:iters
      flag = 0
      while flag == 0
        for i = 1:n
          v = (1-(rand(Int8)&3))%2
          @inbounds F[i] = v
          flag += v & 1
        end
      end
      for j = 1:m
        sum = 0
        for i = 1:n
          @inbounds sum += S & (1 << (j + i - 2)) > 0 ? F[i] : -F[i]
        end
        sum == 0 ?
          (leading_counts[j] += 1) :
          break
      end
    end
    leading_counts
  end
end

function main()
  # Warm up the JIT
  pleadingzerocounts()
  # Then go for real
  println(@time pleadingzerocounts())
end

You can run this using julia -p 8 -e 'require("golf.jl");main()' (the 8 is the number of processes, you might want to play around with it). On the latest Julia prerelease this takes 0.7s vs. 1m22s for PyPy.
If you have enough cores on your computer, and perhaps spin up a few AWS instances, you should be able to shave off some more :)

I'm quite sure you're measuring the timing wrong. Python with Pypy is also a JIT-based language, but the timings made by the OP include the JIT compilation time. You are excluding it.
I installed the latest Julia git version and tested your code, and on my machine your command with 8 processes takes 6.6 seconds to finish, but it prints "elapsed time 0.588.. seconds".

The Python timing does include PyPy startup and JIT warmup, but that takes seconds at most – the difference over a minute of runtime is negligible.
I'm happy if the OP changes the way the Python is timed (it won't make any difference), but including Julia's startup time wouldn't be reasonable.

I asked the OP in the comments to the original question, and he said "The timings should include everything for JIT languages." He also stated he will create a new challenge where the solutions will take much longer than 1 second, leaving Julia in the competition.

In that case the optimal solution is to use a serial algorithm – that takes about 2s. I'd publish the code but this competition is now somewhat redundant, since everyone already knows that C++ boots faster than everything else.

I just posted my Fortran solution, so I don't see why you shouldn't post the fastest Julia one (if you already have the code).

I get julia -p 8 -e 'require("one-more-minute.jl");main()'
ERROR: @simd not defined
in include at boot.jl:238
at /home/user/one-more-minute.jl:0 . This is on julia version 0.2.1

Ah, that's a new feature then. It will work on a prerelease, otherwise you can just remove the @simd completely.

I've updated the code to work on 0.2.1, but note that 0.3 will boot much more quickly (and will probably run faster overall, too).

Any why the time reported is so inaccurate? I increased the number of iterations 100,000 and posted the result in the question.

I was running the code twice to make the timing more reliable – if you get rid of the first pleadingzerocounts()  line in main() the total time should halve. Thanks!

As you will see from my latest tests, it is very impressively fast. Thank you!

I've tried it on Julia 1.0 with the proper changes: with distributed instead of parallel, and with F = Array{Int}(undef, n).  Using addprocs(8) on an old i7 930 computer it needs 613ms to complete, measure with btime.

C, 1.210s
With OP's code running 1m45.729s on my machine.
Compilation:
gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall ./test2.c -o ./test2

Special thanks: @dyp for compilation flags and ideas for optimisations.
#include <stdio.h>
#include <time.h>

#define n (8)
#define m (8)
#define iters (1000)
int leadingzerocounts[m]; // declared as global so initialised to 0
unsigned int x,y=34353,z=57768,w=1564; //PRNG seeds

/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
int myRand() {
    unsigned int t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

int dotproduct(int*F, int*S) {
    unsigned int i;
    int sum=0;
    for(i=0; i<n; i++) {
        sum+=F[i]*S[i];
    }
    return sum;
}

int main() {
    unsigned int i, j, tmp;
    x=(int)time(NULL); //seed PRNG

    int S[n+m-1];
    for(i=0; i<(1<<(n+m-1)); i++) {
        tmp=i;
        for(j=0; j<n+m-1; j++) {
            S[j]=(tmp&1)*(-2)+1;
            tmp>>=1;
        }
        for(j=0; j<iters; j++) {
            int F[n];
            unsigned int k, flag=0;
            do {
                for(k=0; k<n; k++) {
                    F[k]=(1-(myRand()&3))%2;
                    flag+=(F[k]&1);
                }
            } while(!flag);
            for(k=0; k<m&&!dotproduct(F, S+k); k++) {
                leadingzerocounts[k]++;
            }
        }
    }
    for(i=0; i<m; i++) printf("%d ", leadingzerocounts[i]);
    return 0;
}

Sample output:
6334411 2527506 1042239 439328 192914 87005 40847 19728

That's a very nice starting point. 5.2s on my computer so a speedup of around 13.

It seems you can speed up your program by using rand()&3 instead of rand()%4 (although I'm not quite sure it produces the same distribution); replacing the branching for F[k] by using something like F[k] -= F[k]&2; also helped a lot. Using some additional optimizations switches, runtime went from 9.3 s down to 6.4 s on my VM. I suspect calling rand() less often could further improve performance.

@dyp interestingly, on my machine, with the gcc -O3 flag, rand()%4 is faster than rand()&3 by about 0.025s, but using no optimization flags, rand()&3 is faster by ~0.45s.

Interesting indeed, I can make similar observations when dropping all those optimization flags. Try -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize Btw. I got down to < 4 s by using some C++11 including a MT19937 plus a uniform_int_distribution.

@dyp thanks for your flags. I managed to get it down to < 4 without C++11, thanks to you suggesting to reduce the conditional branching after the rand() call.

3.365s or a speedup of about 20 :)

Yeah, but you started with 5 s; I started with 9 s. IIRC, the generator classes can store unused "randomness" and therefore doesn't need to invoke the generator algorithm every time.

At the risk of trying to solve my own problem.. :) ... I think the real benefit will come from not actually creating all 2^(n+m-1)*1000 pairs.  The vast majority of those pairs will never look at the right hand end of S so you should only need to create something much closer to 2^(n)*1000 pairs. How exactly to get this to work is another question :)

@dyp Since I am not very familiar with C++ and my knnowledge of C++11 is almost non-existent I don't think I will plan on writing a C++11 version. I did however switch to a PRNG using xorshift, which greatly reduced my runtime.

1.119s making a speedup of roughly 59!

@ace Yes, I just wanted to point this out. It was simpler for me just to try some of the standard library PRNGs in C++. Note that you can use one 32-bit integer result from a PRNG to produce 8 entries for F.

Since n is equal to 8, you can probably use AVX (or 2*SSE) to compute the dotproduct with a proper S storage.

SSE version, small speed-up : https://gist.github.com/anonymous/11394210 (dont forget to include smmintrin.h)

@Michael I am no SSE expert but my processor seems to support all kinds of SSE versions http://www.cpu-world.com/CPUs/Bulldozer/AMD-FX-Series%20FX-8350.html .

@Lembik, yes it also supports AVX (sadly, not mine)

@Michael Is http://stackoverflow.com/questions/10454150/intel-avx-256-bits-version-of-dot-product-for-double-precision-floating-point relevant? Sorry I really don't know anything about AVX/SSE so I may be way off.

@Lembik, no that's floating-point dot product, not usable for integers. Anyway, I think we can use improve SSE using short instead of int and do math on 8 numbers simultaneously.

Yes, even better using short and 16-bits intrinsics ! https://gist.github.com/anonymous/11395262

Ah OK, great. Did you get your original suggestion from http://stackoverflow.com/questions/23186348/integer-dot-product-using-sse-avx ?

@Lembik, absolutely.

@Lembik My original algorithm did not depend on n. Is it acceptable if it does? I.e. it will only work if n is 8, it won't work if it is some other number, even if you redefine n. Since Michael's SSE suggestion and dyp's PRNG suggestion both actually depend on this.

@ace I would prefer it if it worked for any even n to be honest.

@ace Are you available in chat? I would like to ask about your code.

@Lembik okay I'm on chat

You can still do it for any n with SSE, you have to treat arrays elements 8 by 8. You can also use char instead of short and treat elements 16 by 16 since numbers are very smalls.

Perl
This is nowhere near as fast as the C solution, but is pretty fast for a high-level interpreted language I think. It shaves about 40% off the running time of the Python implementation.
#!/usr/bin/env perl

use v5.10;
use strict;
use warnings;
use Algorithm::Combinatorics qw( variations_with_repetition );
use List::Util qw( any sum );

use constant {
  N        => 8,
  M        => 8,
  ITERS    => 1000,
};

my @leadingzerocounts;

my $variations = variations_with_repetition([-1, 1], N + M - 1);
while (my $S = $variations->next)
{
  for my $i (1 .. ITERS)
  {
    my @F;
    until (@F and any { $_ } @F)
    {
      @F = map +((-1,0,0,1)[rand 4]), 1..N;
    }

    my $j = 0;
    while ($j < M)
    {
      last if sum map $F[$_]*$S->[$j+$_], 0..N-1;
      $leadingzerocounts[$j++]++;
    }
  }
}

say join ", ", @leadingzerocounts;

The Algorithm::Combinatorics is available in Ubuntu (sudo apt-get install libalgorithm-combinatorics-perl). The other modules used are core Perl modules, so should already be installed as part of the base Ubuntu installation.

It won't affect speed, but it's 0..N-1 range in the last map, right? Did you forget to use warnings? :-) Though logic in OP is confusing, sliding window never gets to the last element of S.

Ah. I just figured that the arrays were of mismatched sizes, so I disabled warnings allowing the missing elements to be treated as zero. N-1 improves this. And it does actually improve the speed very slightly — it's now about 40% faster than the Python implementation.

I think your code requires a very modern version of List::Util. On ubuntu 14.04 I get "any" is not exported by the List::Util module

Oh yes, that's true - you'll probably need to install List::Util off CPAN. any can alternatively be found in List::MoreUtils, which although not a core module is one of the most commonly used CPAN modules.

Julia: 1 min 21.4s (2.2x faster) (modification of Arman's code)
Op's code in PyPy: 3 min 1.4 s
Both done in the REPL, not including time to load packages.
function foo()
    n = 8
    m = 8
    iters = 1000
    bothzero = 0
    leadingzerocounts = zeros(Int,m)
    P=[-1,0,0,1]

    for S in Iterators.product(fill([-1,1], n+m-1)...)
        Sm=[S...]
        for i = 1:iters
            F = P[rand(1:4,n)]
            while all(F==0)
                F = P[rand(1:4,n)]
            end
            j = 1

            while j <= m && dot(F,Sm[j:j+n-1]) == 0
                leadingzerocounts[j] += 1
                j += 1
            end
        end
    end

    println(leadingzerocounts)
end

There are some problems with Arman's code making it very slow: It uses a lot of anonymous functions and higher order functions unnecessarily.  To test if all of a vector F is zero, why not just write all(F==0) instead of all(x->x==0,F)? It is shorter, and a literally a thousand times faster.
It also uses sum(map(*,x,y)) as the dot product instead of simply dot(x,y). The first version 650 times slower for a vector of 10k doubles. And the dot product function is implemented as a for loop in pure Julia.
Also, array comprehensions are slow. It is better to write [0,1,0,-1][rand(1:4,n)] instead of [[-1 0 0 1][rand(1:4)] for j = 1:n].
Finally, global variables are bad juju in Julia. Julia is only fast if you write code in such a way that allows the JIT and type inference to work. A big part of this is type stability: The compiler must be able to be sure that a variable's type will not change while inside a loop, for example.

Thanks! I see that I still have quite a bit to learn about the Julia Language before I can go making claims about its speed :) Really glad to see that a few trivial fixes to my code increase its execution time several fold.

RPython 0.187s (258x faster)
Original Source w/ PyPy2.2.1: 1m 6.718s
Now with threading, back-support for standard Python has been dropped. The number of worker threads can be specified as a command line parameter, default is two.
from time import time, sleep
from math import fmod

from rpython.rlib.rthread import start_new_thread, allocate_lock, get_ident
class Random:
  __slots__ = ['s']

  def __init__(self, s=1):
    self.s = s

  def init_genrand(self, seed):
    self.s = seed

  def genrand32(self):
    # xorshift PRNG with period 2^32-1
    # see http://core.kmi.open.ac.uk/download/pdf/6250138.pdf
    self.s ^= (self.s << 13)
    self.s ^= (self.s >> 17)
    self.s ^= (self.s << 5)
    return self.s

class ThreadEnv:
  __slots__ = ['n', 'm', 'iters', 'counts', 'running', 'lock']

  def __init__(self):
    self.n = 8
    self.m = 8
    self.iters = 1000
    self.counts = [0]*8
    self.running = 0
    self.lock = None

env = ThreadEnv()
truth = [-1,0,0,1]

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

  if argc == 5:
    num_threads = int(argv[4])
  else:
    num_threads = 2

  env.n = int(argv[1])
  env.m = int(argv[2])
  env.iters = int(argv[3]) // num_threads
  env.counts = [0]*env.m
  env.lock = allocate_lock()

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

  env.running += 1

  # use the main process as a worker
  run()

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

  print env.counts
  return 0

def run():
  n, m, iters = env.n, env.m, env.iters
  counts = [0]*m
  sbits = [0]*(n+m-1)

  random = Random()
  seed = int(fmod(time(), 2147483.648)*1000) ^ get_ident()
  random.init_genrand(seed)

  for S in xrange(1<<n+m-1):
    i = 0
    sbit = 0
    while not sbit:
      sbits[i] ^= 3
      sbit = sbits[i]
      i += 1

    for i in xrange(iters):
      f = 0
      while not f:
        F = random.genrand32()

        G, x = F, 0
        for k in xrange(n):
          x += truth[(G&3)^sbits[k]]
          f |= x
          G >>= 2

      if not x:
        counts[0] += 1
        for j in xrange(1, m):
          G, x = F, 0
          for k in xrange(j, n+j):
            x += truth[(G&3)^sbits[k]]
            G >>= 2
          if x: break
          counts[j] += 1

  # passing True stalls until a lock can be obtained
  env.lock.acquire(True)

  for i in xrange(m):
    env.counts[i] += counts[i]
  env.running -= 1

  env.lock.release()

def target(*args):
  return main, None

RPython is a restricted subset of Python, which can be translated to C and then compiled using the RPython Toolchain. Its expressed purpose is to aid in the creation of language interpreters, but it can also be used to compile simple programs like the one above. Most of the 'fancier' features of Python, such as itertools or even map are not available.
To compile, make a local clone of the current pypy repository, and run the following:
$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution.py

The resulting executable will be named convolution-c or similar in the current working directory.
I've parameterized the input variables, so the program should be run as:
convolution-c 8 8 1000

to match the sample code.

Implementation Notes
S in itertools.product([-1,1], repeat = n+m-1) becomes S in xrange(1<<n+m-1), interpreting S as a bit map: [0, 1] → [-1, 1]
Likewise, F is also a bit map, with each two bits representing a single value:
[00, 01, 10, 11] → [-1, 0, 0, 1]
A truth table is used to lookup the product, rather than performing a mulitplication.
Because 32-bit signed integers are used, n may be no larger than 15, and n+m no larger than 31. Arbitrary integer support can be achieved with the rpython.rlib.rbigint module, if necessary.
The first iteration of the dot-product loop is unrolled, and combined with the nullity test of F.
A homebrew PRNG is used, source listed. The author of the paper demonstrates a period of 232-1, and claims that it passes all Diehard tests save one, although I haven't personally confirmed this.
The random seed changes every millisecond, which is as about as good using a timestamp will allow. Additionally, each worker thread xors their process id with this value, to ensure that they each have a different seed.

Sample Timings
2 worker threads:
$ timeit convolution-c 8 8 1000 2
[6331845, 2526161, 1042330, 440018, 193724, 87147, 40943, 19603]

Elapsed Time:     0:00:00.375
Process Time:     0:00:00.687
System Calls:     6927

4 worker threads:
$ timeit convolution-c 8 8 1000 4
[6334565, 2527684, 1043502, 440216, 193225, 87398, 40799, 19338]

Elapsed Time:     0:00:00.218
Process Time:     0:00:00.796
System Calls:     3417

8 worker threads:
$ timeit convolution-c 8 8 1000 8
[6327639, 2522483, 1039869, 437884, 192460, 86771, 40420, 19403]

Elapsed Time:     0:00:00.187
Process Time:     0:00:00.734
System Calls:     3165

OP's original source:
$ timeit pypy convolution-orig.py
[6330610, 2525644, 1041481, 438980, 193001, 86622, 40598, 19449]

Elapsed Time:     0:01:06.718
Process Time:     0:01:06.718
System Calls:     11599808

Timing for 100000 iterations:
$ timeit convolution-c 8 8 100000 8
[633156171, 252540679, 104129386, 43903716, 19307215, 8709157, 4072133, 1959124]

Elapsed Time:     0:00:16.625
Process Time:     0:01:02.406
System Calls:     171341

I have never seen an rpython program before. This is great. Now is there an equivalent pure python program that pypy can run in 1.03s?

@Lembik I'd like to see one. I thought 4.7s was pretty good, considering my first attempt at pure python was ~15s.

Yes, sorry for the delay. I haven't got the code running yet but will as soon as possible.

You should try adding a JIT. Now THAT would be fast!

@Lembik thanks for the mention ;) Out of curiousity, did it run fastest with 4 worker threads, or 8?

@kirbyfan64sos I'm not sure what you'd want to JIT compile. The only thing that could possibly define an execution frame would be [S, F], but the code shouldn't ever see the same combination twice.

You can just use a value that you know stays the same for the red and all the rest as greens. Then, put a can_enter_loop at the end of every iteration. I wrote an RPython version of the "tree" program with a JIT for fun using that technique. It actually worked!

Julia: 4.66x slower!
I am really beginning to doubt the statistics on their website...
Note that the following Julia code is effectively a direct transcription of the OP's Python code without any optimisations. I use the time() function to exclude Julia's slow startup time...
srand(27182818284590)
t = time()

require("Iterators")

n = 8
m = 8
iters = 1000
bothzero = 0
leadingzerocounts = zeros(m)

for S in Iterators.product(fill([-1,1], n+m-1)...)
    for i = 1:iters
        F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        while all((x) -> x == 0, F)
            F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        end
        j = 1
        while j <= m && sum(map(*, F, S[j:j+n-1])) == 0
            leadingzerocounts[j] += 1
            j += 1
        end
    end
end

println(leadingzerocounts)

t = time() - t
println("$t seconds")

Julia: 5 m 32.912 s
OP's code in PyPy: 1 m 11.506 s
Julia output:
6332170
2525472
1041522
438761
193119
86873
40705
19662

+1 for your shamelessness sportsmanship.

Global variables, imports, and array comprehensions are slow. This isn't how one would typically write a Julia program for performance.

Nimrod
import times, locks, strutils, unsigned

const
  N = 8
  M = 8
  iters = 1000
  numThreads = 8

type
  SVec = array[0..N+M-1, int]
  FVec = array[0..N-1, int]
  ComputeThread = TThread[int]

var
  rngSeed = int(epochTime()*1000)
  totalLeadingZeros: array[0..M-1, int]
  lock: TLock

type
  RNGState = object
    x, y, z, w: uint32

proc newRNG(seed: int): RNGState =
  result.x = uint32(seed)

proc random(rng: var RNGState): int =
  let t = rng.x xor (rng.x shl 11)
  rng.x = rng.y; rng.y = rng.z; rng.z = rng.w
  rng.w = rng.w xor (rng.w shr 19) xor t xor (t shr 8)
  result = int(rng.w)

proc initVecRand(v: var FVec, rng: var RNGState) =
  const values = [ -1, 0, 0, 1 ]
  var rnd = rng.random
  var bitAcc = 0
  for i in 0 .. <len(v):
    let val = values[rnd and 3]
    rnd = rnd shr 2
    v[i] = val
    bitAcc = bitAcc or val
  if bitAcc == 0:
    initVecRand(v, rng)

proc convolve(s: SVec, f: FVec, offset: int): int =
  for i in 0 .. <len(f):
    result += s[i+offset]*f[i]

proc iterate(v: var SVec) =
  for i in 0 .. <len(v):
    if v[i] == -1:
      v[i] = 1
      return
    v[i] = -1

proc mainThread(id: int) {.thread.} =
  const numS = 1 shl (N+M-1)
  var
    s: SVec
    f: FVec
    leadingZeros: array[0..M-1, int]
    rng = newRNG(rngSeed + id)
  for k in 0 .. <len(s):
    s[k] = -1
  for i in 1..numS:
    for j in countUp(id, iters, numThreads):
      initVecRand(f, rng)
      if convolve(s, f, 0) == 0:
        leadingZeros[0] += 1
        for k in 1 .. <M:
          if convolve(s, f, k) == 0:
            leadingZeros[k] += 1
          else:
            break
    iterate(s)
  acquire(lock)
  for i in 0 .. <M:
    totalLeadingZeros[i] += leadingZeros[i]
  release(lock)

proc main =
  let startTime = epochTime()
  var threads: array[1..numThreads, ComputeThread]
  initLock(lock)
  for i in 1..numThreads:
    createThread(threads[i], mainThread, i)
  for i in 1..numThreads:
    joinThread(threads[i])
  echo("Leading zeros: ", @totalLeadingZeros)
  let endTime = epochTime()
  echo("Time taken:    ", formatFloat(endTime - startTime, ffDecimal, 3),
       " seconds")

main()

Example output:
Leading zeros: @[6333025, 2525808, 1042466, 439138, 192391, 86751, 40671, 19525]
Time taken:    0.145 seconds

Nimrod compiles to C, therefore the choice of C compiler for the backend matters, too.
Using clang, compile with:
nimrod cc --threads:on --cc=clang --passc:-flto -d:release conv.nim

Using gcc, compile with:
nimrod cc --threads:on --cc=gcc --passc:-flto -d:release conv.nim

Omit --passc:-flto if you have an older C compiler that doesn't support LTO. Omit the --cc=... option if you are fine with the default choice for the C compiler. The code requires Nimrod 0.9.4 or 0.9.5.
On my quadcore iMac (2.66 GHz core i5), the code runs in about .15 seconds with gcc 4.9, .16 seconds with clang, compared to 88 seconds for PyPy 2.2.1 (i.e. a 500+ times speedup). Unfortunately, I don't have access to a machine with more than four cores that also has PyPy installed or where I could easily install PyPy, though I get about .1 seconds (with a lot of measurement noise) on a 64-core AMD Opteron 6376 1.4 GHz (according to /proc/cpuinfo) with gcc 4.4.6.
The implementation tries to be faithful to the original rather than optimizing code at the cost of readability, while not forgoing obvious optimizations. Interestingly enough, tail recursion in initVecRand() is a bit faster than a loop with a break instruction with both gcc and clang. Manually unrolling one iteration of the convolve test loop inside the main loop also produced a speedup, presumably due to better branch prediction.

How do you get nimrod for ubuntu?

@Lembik A quick Google search would give you http://nimrod-lang.org/download.html

@ace I had also included the link in my post (though it's hard to see with blue on black now that I look at it).

You could speed this up even more by increasing the seed size to 128 bits: http://xorshift.di.unimi.it/

Java
I translated the above C++ solution to Java:
import java.util.Random;
import java.util.Arrays;

public class Bench2 {
  public static int[] bits = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
  public static int[] oneValues = { 1, 0, 0, 1 };
  public static int[] values = { -1, 0, 0, 1 };
  public static int n = 8;
  public static int m = 8;
  public static int iters = 1000;

  private static int x,y=34353,z=57768,w=1564;

  public static void main( String[] args ) {
    x = (int) (System.currentTimeMillis()/1000l);

    int[] leadingzerocounts = new int[ m ];
    Arrays.fill( leadingzerocounts, 0 );

    int maxS = 1 << 15;

    for( int s = 0; s < maxS; s++ ) {
      int x = interleaveBit( s );

      for( int i=0; i<iters; i++ ) {
        int random;

        do {
          random = 0xFFFF & fastRandom( );
        } while( sumOnes( random ) == 0 );

        int j = 7;

        while( j >= 0 ) {
          int h = ( x >> (j*2) );
          int l = 0xFFFF & (~(random ^ h));

          if( sumArray( l ) == 0 ) {
            leadingzerocounts[ j ]++;
          } else {
            break;
          }

          j--;
        }
      }
    }

    for( int i = 7; i >= 0; --i ) {
      System.out.print( leadingzerocounts[ i ] + " " );
    }

    System.out.println( );
  }

  public static int interleaveBit( int x ) {
    x = (x | ( x << 8)) & bits[3];
    x = (x | ( x << 4)) & bits[2];
    x = (x | ( x << 2)) & bits[1];
    x = (x | ( x << 1)) & bits[0];
    return x | (x << 1);
  }

  public static int sumOnes( int v ) {
    return (0xAAAA & (v ^ ~(v << 1)));
    // int s = 0;

    // for( int i = 0; i < 8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += oneValues[ a ];
    // }

    // return s;
  }

  public static int sumArray( int v ) {
    return Integer.bitCount( v ) - 8;
    // int s = 0;

    // for( int i=0; i<8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += values[ a ];
    // }

    // return s;
  }

  public static int fastRandom( ) {
    long t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (int)( w ^ (w >> 19) ^ t ^ (t >> 8));
  }
}

On my machine I get following output for the java program:
time java Bench2
6330616 2524569 1040372 439615 193290 87131 40651 19607
java Bench2  0.36s user 0.02s system 102% cpu 0.371 total

The OPs program runs about 53 seconds on my machine:
time pypy start.py
[6330944, 2524897, 1040621, 439317, 192731, 86850, 40830, 19555]
pypy start.py  52.96s user 0.06s system 99% cpu 53.271 total

The c++ program executed only about 0.15 seconds:
time ./benchcc
[6112256, 2461184, 1025152, 435584, 193376, 87400, 40924, 19700]
./benchcc  0.15s user 0.00s system 99% cpu 0.151 total

That is about 2.5x faster than the corresponding java solution (I didn't exclude VM startup). This java solutions is about 142x faster than the program executed with PyPy.
Since I was personally interested, I set iters to 100_000 for Java and C++ but the factor of 2.5 didn't decrease in favor of Java if anything got bigger.
EDIT: I ran the programs on a 64bit Arch Linux PC.
EDIT2: I want to add that I started with a rough translation of the python code:
import java.util.Random;
import java.util.Arrays;

public class Bench {
    public static int[] values = { -1, 0, 0, 1 };
    public static int n = 8;
    public static int m = 8;
    public static int iters = 1000;

    private static int x,y=34353,z=57768,w=1564;

    public static void main( String[] args ) {
        x = (int) (System.currentTimeMillis()/1000l);

        int[] leadingzerocounts = new int[ m ];
        Arrays.fill( leadingzerocounts, 0 );

        int[] S = new int[ n+m-1 ];
        Arrays.fill( S, -1 );

        do {
            for( int i=0; i<iters; i++ ) {
                int[] F = new int[ n ];

                do {
                    randomArray( F );
                } while( containsOnlyZeros( F ) );

                for( int j=0; j < m && check( F, S, j ); j++ ) {
                    leadingzerocounts[ j ] += 1;
                }
            }
        } while( next( S ) );

        System.out.println( Arrays.toString( leadingzerocounts ) );
    }

    public static void randomArray( int[] F ) {
        for( int i = 0; i<F.length; i++ ) {
            F[ i ] = (1-(fastRandom()&3))%2;
        }
    }

    public static boolean containsOnlyZeros( int[] F ) {
        for( int x : F ) {
            if( x != 0 ) {
                return false;
            }
        }

        return true;
    }

    public static boolean next( int[] S ) {
        for( int i=0; i<S.length; i++ ) {
            if( ( S[ i ] = -S[ i ] ) == 1 ) {
                return true;
            }
        }

        return false;
    }

    public static boolean check( int[] F, int[] S, int j ) {
      int sum = 0;

      for( int i=0; i<n; i++ ) {
          sum += F[ i ] * S[ j + i ];
      }

      return sum == 0;
    }

    public static int fastRandom( ) {
        long t;
        t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (int)( w ^ (w >> 19) ^ t ^ (t >> 8));
    }
}

This program ran about 3.6 seconds:
time java Bench
[6330034, 2524369, 1040723, 439261, 193673, 87338, 40840, 19567]
java Bench  3.64s user 0.01s system 101% cpu 3.600 total

Which is about 14 times faster than the PyPy solution. (Choosing the standard random function over the fastRandom function leads to an execution time of 5 seconds)

Python 3.5 + numpy 1.10.1, 3.76 seconds
The tests were run on my Macbook Pro. OP's code took ~6 mins on the same machine.
The reason I'm answering this question in fact is because I don't have 10 reputations and can't answer Part I :-p
For the past few days, I have been trying to figure out how to perform massive convolutions efficiently with numpy (without relying on a third-party package, even scipy). As I came across this series of challenges during my research, I decided to give it a try. I may have come to this game to late, but here is my attempt using Python 3.5 and numpy 1.10.1.
def test_convolv():
    n = 8
    m  = 8
    iters = 1000
    ilow = np.ceil(0+n/2).astype(int)
    ihigh = np.ceil(m+n/2).astype(int)

    leadingzerocounts = np.zeros(m)

    # Pre-compute S & F
    S = np.array(list(itertools.product([-1,1], repeat = n+m-1)))
    choicesF = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*iters).reshape(iters,n)
    imask = ~np.any(choicesF, axis=1)
    while np.any(imask):
        imasksize = np.count_nonzero(imask)
        choicesF[imask,:] = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*imasksize).reshape(imasksize, n)
        imask = ~np.any(choicesF, axis=1)

    for i in np.arange(iters):
        F = choicesF[i, :]
        # This is where the magic is: by flattening the S array,
        # I try to take advantage of speed of the np.convolve
        # (really numpy.multiarray.correlate).
        FS = (np.convolve(S.reshape(-1), F, 'same').reshape(S.shape))[:, ilow:ihigh]
        jmask_not = (FS[:, 0] != 0)
        leadingzerocounts[0] = leadingzerocounts[0]+np.count_nonzero(~jmask_not)
        for j in np.arange(n-1)+1:
            jmask = (FS[jmask_not, j] != 0)
            leadingzerocounts[j] = leadingzerocounts[j] + np.count_nonzero(~jmask)
            jmask_not[(jmask_not.nonzero()[0])[jmask]] = False

    print(leadingzerocounts)

I pre-computed the S and F arrays, and flattened the S array while performing the convolution, which (based on my experiments) could take advantage of the speed of np.convolve. In other words, as I didn't find a vectorized convolution routine, I fake-vectorized the code by flattening the whole array and hoped np.convolved would do the vectorization under the hood for me, which seemed to be working. Note I used mode='same' and trimmed the leading and trailing elements that were useless.
On my Macbook Pro, the test results give 3.76 seconds. When I ran OP's code (modified to Python 3.5), I got about 6 minutes. The speedup is about 100 times.
One drawback is that because the S and F arrays are to be stored, the memory requirement can be a problem if the sizes are too big.
I used the same method for Part I and I got a ~ 60-100x speedup on my laptop.
As I did everything on my Macbook Pro, if someone could test my code and let me know how it goes on your machine, I would appreciate it very much!

Fortran: 316x
Okay, Fortran: I've got it up to 106x 155x 160x 316x speedup when using an Xorshift RNG and OpenMP on a 4 core i7 CPU. Other than that, there are no big tricks. For the iterator to construct S, I just use the binary representation of the 16-bit integer i. You'll note that apart from the inline RNG and the "iterator"/mapping from i to S, the code is just as high-level as the Python code.
Edit: removed the "if" in the Xorshift, now using "r = abs(w/...)" instead of "r=w/...". Goes from 106x to 155x.
Edit2: This generates 15x as many random numbers as the C++ solution. If someone has a zero-overhead solution for converting a random int into an array of 0s and 1s in Fortran, I'm all ears. Then we could beat C++ :)
Edit3: The first edit introduced a bug, as Lembik pointed out. This is fixed now, with a tiny improvement in speedup. I will try to use the suggestion by Eelvex to get more speedup.
Edit4: Profiling indicated that converting to real and back to integer with nint() was slow. I replaced this with one integer division doing both scaling and rounding, going from 160x to 316x speedup.
Compile with:

gfortran -O3 -march=native -fopenmp golf.f90

program golf
implicit none
integer, parameter :: m=8, n=8
integer :: F(n), S(m+n-1), leadingzerocounts(m)
integer :: j,k,bindec,enc,tmp,x=123456789,y=362436069,z=521288629,w=88675123
integer*2 :: i
real :: r

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k,tmp,x,y,z,w,r) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,32766
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=16,2,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j-1)=1
      enc=enc-bindec
    else
      S(j-1)=-1
    endif
  end do
  do j=1,1000
    F=0
    do while (.not. any(F /= 0))
      do k=1,n
        ! Start Xorshift RNG
        tmp = ieor(x,ishft(x,11))
        x = y
        y = z
        z = w
        w = ieor(ieor(w,ishft(w,-19)),ieor(tmp,ishft(tmp,-8)))
        ! End Xorshift RNG
        ! Just scale it inside the nint:
        !F(k)=nint(w/2147483648.0)
        ! Scaling by integer division is faster, but then we need the random
        ! number to be in (-2,2) instead of [-1,1]:
        F(k)=w/1073741824

      end do
    end do
    do k=1,m
      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

Example output:

$ time ./a.out
       6329624     2524831     1039787      438809      193044       6860       40486       19517
  ./a.out  1.45s user 0.00s system 746% cpu 0.192 total

OP's code:

$ time pypy golf.py
  pypy golf.py  60.68s user 0.04s system 99% cpu 1:00.74 total

What I used in J was a prebuild list of 4^n numbers in base-4, then converted to triadic and excluding 0. The RNG just chooses from this list.

I am not sure your code is correct. For 100,000 iterations I get 633140285   271390368   118307997    52751245    23725837    10744292     4944464     2388125 but I think it should be closer to 633170604 252560981 104156146 43911426 19316309 8713324 4073378 1959440. This is a consistent difference between runs.

Ah, thanks, @Lembik, my edit to speedup (removing the if-statement) was indeed a bug. I've updated my code so it should be correct now. I will try to post a version using the suggestion by Eelvex later.

That also sped it up it seems!

Yes, slight speedup I guess. I realized I was adding 1.0 and then subtracting 1.0 inside a tight loop.

C++: x200 (4-core i7, should scale to x400 on 8-core)
Trying for a more straightforward C++11 (Tested with VS 2012, gcc and clang) solution with parallelization.
To get this to compile and run under Linux with gcc 4.8.1:

g++ -O3 -msse -msse2 -msse3 -march=native -std=c++11 -pthread
  -Wl,--no-as-needed golf.cpp

Under Linux we also need std::launch::async to force multiple threads.  I was missing that in an earlier version.
In Visual Studio (2012+) this should just work but make a release build for timing...
On my oldish dual core i3 this runs in ~0.9 seconds. On my i7 quad core this is 0.319s vs. pypy 66 seconds.
On an 8-core i7 this should in the x400 speedup range.  Switching to C style arrays would speed  it up but I was interested in staying with C++ containers.  For me it's interesting to see the speedup you can get while staying relatively close to the problem domain and at a relatively high level, something I think C++ is really good at.  Also of note is the relative ease of paralleization using C++11 constructs.
@ilmale's bit solution is very cool and works for -1/1/0.  One could also throw SSE at this and maybe get a significant speedup.
Beyond the parallelization there's another "trick" in there which is reducing the number of summations.  Sample results:
6332947
2525357
1041957
438353
193024
87331
40902
19649
#include <vector>
#include <iostream>
#include <thread>
#include <future>
#include <time.h>
#include <ctime>
#include <algorithm>

using namespace std;

// Bring some of these constants out to share
const size_t m = 8;
const int nthreads = 16;
const size_t cn = 15;
const int two_to_cn = 32768;

static unsigned int seed = 35;

int my_random() // not thread safe but let's call that more random!
{
   seed = seed*1664525UL + 1013904223UL; // numberical recipes, 32 bit
   return ((seed>>30)&1)-!!((seed>>30)&2); // Credit to Dave!
}

bool allzero(const vector<int>& T)
{
   for(auto x : T)
   {
      if(x!=0)
      {
         return false;
      }
   }
   return true;
}

// Return the position of the first non-zero element
size_t convolve_until_nonzero(size_t max_n, const vector<int>& v1, const vector<int>& v2)
{
   for(size_t i = 0; i<max_n; ++i)
   {
      int result = 0;
      for(size_t j = 0; j<v2.size(); ++j)
      {
         result += v1[i+j]*v2[j];
      }
      if(result!=0)
      {
         return i;
      }
   }
   return max_n;
}

void advance(vector<int>& v)
{
   for(auto &x : v)
   {
      if(x==-1)
      {
         x = 1;
         return;
      }
      x = -1;
   }
}

vector<int> convolve_random_arrays(vector<int> S, int range)
{
   const int iters = 1000;
   int bothzero = 0;
   int firstzero = 0;

   time_t current_time;
   time(&current_time);
   seed = current_time;

   vector<int> F(m);
   vector<int> leadingzerocounts(m+1);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   for(int i=0; i<range; ++i)
   {
      for(int j=0; j<iters; ++j)
      {
         do
         {
            for(auto &x : F)
            {
               x = my_random();
            }
         } while(allzero(F));
         leadingzerocounts[convolve_until_nonzero(m, S, F)]++;
      }
      advance(S);
   }

   // Finish adding things up...
   for(int i=m-1; i>0; --i)
   {
      leadingzerocounts[i] += leadingzerocounts[i+1];
   }

   vector<int> withoutfirst(leadingzerocounts.begin()+1, leadingzerocounts.end());
   return withoutfirst;
}

int main(int argc, char* argv[])
{

   vector<int> leadingzerocounts(m);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   clock_t start = clock();

   vector<int> S(cn);
   for(auto &x : S)
   {
      x = -1;
   }

   vector< future< vector< int > > > fs; // The future results of the threads

   // Go make threads to work on parts of the problem
   for(int i=0; i<nthreads; ++i)
   {
      vector<int> S_reversed = S; // S counts using LSBs but we want the thread start to be in MSBs
      reverse(S_reversed.begin(), S_reversed.end());
      fs.push_back(async(std::launch::async, convolve_random_arrays, S_reversed, two_to_cn/nthreads));
      advance(S);
   }
   // And now collect the data
   for(auto &f : fs)
   {
      vector<int> result = f.get();
      for(int i=0; i<result.size(); ++i)
      {
         leadingzerocounts[i] += result[i];
      }
   }

   for(auto count : leadingzerocounts)
   {
      cout << count << endl;
   }

   return 0;
}

J, 130x~50x speedup?
n =: m =: 8
len =: 1000
S =: (] - 0 = ])S0=: #:i.2^<:+/n,m
k =: (n#0) -.~ (_1 0 0 1) {~ (n#4) #: i.4^n
sn =: (]-0=])#:i.2^n
ku =: ~. k
M =: 0=+/"1 sn *"1/ ku
fs =: (ku&i.)"1 k
snum =: n #.\"1 S0

run =: 3 : 0
 r =: n#0
 for_t. (snum) do.
   rn =: fs{~? len # #k
   r =: r + +/"1*/\rn{"1 t{M
 end.
 r
)
echo run 0
exit''

Times on a random debian:
u#>time j slowpy.ijs
6334123 2526955 1041600 440039 193567 87321 40754 19714

real    0m2.453s
user    0m2.368s
sys     0m0.084s

u#>time python slow_pyth.py
[6331017, 2524166, 1041731, 438731, 193599, 87578, 40919, 19705]

real    5m25.541s
user    5m25.548s
sys     0m0.012s

I think there is room for improvement.

The Python script is supposed to be executed using pypy, not python, which is why your script seems to be giving 130x speed-up.

@ace yes I noticed but I can't install pypy :-/ I think the order of magnitude will remain though.

Not necessarily... http://i.imgur.com/n566hzw.png

Indeed, not necessarily.

What problem do you have installing pypy?

@Lembik I'm not sure; something is not quite right with this debian installation. 'sid/main puppy ... 404 Not Found'

@ace, it seems on par with the C version, no?

Just grab https://bitbucket.org/squeaky/portable-pypy/downloads/pypy-2.2.1-linux_x86_64-portable.tar.bz2 if you are on 64 bit debian.

@Lembik why don't you just grab a J interpreter and time it on your machine? I'm sure Eelvex can provide a download link or something like that...

@Lembik thanks I'll try that. You can get J here if you like.

source: Stack Exchange

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

sort: votes


text:
Avoid the evil integers!
You are developing some code to generate ID numbers. Policy requires that no ID numbers include the digit sequence 666.
Create a function (or your language's equivalent) which takes a positive integer parameter and returns the next integer that does not include 666 when that integer is expressed in decimal. (60606 is fine, 66600 is not.)
Your code must not use a loop that adds one until it finds a result that fits the rules.
f(1) returns 2.
f(665) returns 667.
f(665999999) returns 667000000 without having looped a million times.
(Following examples added since the question was first posed.)
f(666666666) also returns 667000000.
f(66600) returns 66700.
f(456667) returns 456670.

UPDATE:
Replacing 666 with 667 won't work if there's more than one 666 in the input.

What about something like 456667? Should that return 456670, or are we only worried about a leading 666?

@KyleKanos - Yes. The returned value can't contain 666 anywhere. I'll add a few more examples including yours.

I think this would be better as [tag:code-golf] than [tag:popularity-contest] since there are such straightforward solutions.

Replacing 666 with 667 won't work if there's more than one 666 in the input. I don't see why not, as long as all instances are replaced left-to-right, e.g. 66666 -> 66766.

@nyuszika7h but the result should be 66700.

@m.buettner Oh, right.

What should 6660666 evaluate to? 6670000?

@GreenstoneWalker Yes, I think thats right.  6670000 is the lowest number greater than 6660666 that has no consecutive 666 digits

Actually you just add 1 once, then search first occurrence of "666", replace it with "667" and substitute all digits after that with 0-s;

you can replace "666" with "667" and add zeros, which I did in the Julia example

as a real challenge, there should've also been a requirement to not have "666" anywhere in the code

@DLeh 665 + 1

right, try using 665 + 1 in regex.

@DLeh Highest voted answer doesn't use regex. But in any case "regexbefore" + "66" + "6" + "regexafter" still works. Or str(665+1)

Depending on your regex implementation, you could use '6{3}' to detect 666.

You want to make 'Your code must not use a loop that adds one until it finds a result that fits the rules' more bulletproof. I could simply add 3 (you never said the numbers had to be consecutive). I could add 2 and subtract 1. I could add 10 and count down, rejecting the first 8 numbers. etc. I could add 1.6 (float) and convert back to integer. This alone (workaround 'adding one') would make a lawyerly code-golf puzzle in itself...

As the evil integers should be avoided, shouldn't that also apply to source code + computer memory? That would make the challenge significantly harder.

Your specification looks weird. I wouldn’t call something an ID unless it were unique. And uniqueness (possibly asking that ID are increasing wrt ales, and that they are always as small as possible) seems to me like a more interesting challenge. Not that I would compete.

Python, no string manipulation
def f(n):
    n += 1
    p = 1
    m = n
    while m:
        if m % 1000 == 666:
            n += p - n % p
        p *= 10
        m /= 10
    return n

Works by finding powers of 10, p, where 666 appears, and adding p - n % p to n which replaces 666xxxxx with 66700000.

I like this in that if this was actually a real customer requirement, this implementation is non-hacky, sensible and efficient.

Will this work with numbers that contain multiple instances of 666?

Yes.  The leftmost 666 is the only one that actually matters, and this algorithm fixes that one last.

@romkyns Post an actual real customer requirement to codegolf to trick other people into doing their work for them? That's evil! (hides)

For everyone who uses python 3: This code does not work on python 3+, to run this code on python 3 you have to change m /= 10 to m //= 10. If you don't then m will become a float and the condition m % 1000 == 666 will continously be false and other "666" in n are left unchanged.

JavaScript (updated to work with all test cases)
The little-known truth is that there are actually four 6s, but one of the betrayed the others and polymorphed into code form to eradicate them from the world digits of the numbers. Here is that traitorous six:
    x=prompt(''+
  'Enter number');
 alert(      ( (~x[
'ind'+
'exOf']('666')))?(x
.replace(/666(.*)$/,
function    (mat,g){
return       '667'+g
 ['re'+      'place'
 ](/./g,0)})):((+x+
    1+'').replace(
     666,667)));

Here is an explanation. First, beautify the code and remove useless stuff like ''+'string' and ((code)):
x = prompt('Enter number');
alert(
    ~x['indexOf']('666')
        ?
    x.replace(/666(.*)$/, function(mat,g) {
        return '667' + g['replace'](/./g,0)
    })
        :
    (+x+1+'').replace(666, 667)
);

Convert weird notations (like ~indexOf and ['replace']) into more common ones:
x = prompt('Enter number');
alert(
    x.indexOf('666') > -1
        ?
    x.replace(/666(.*)$/, function(mat, g) {
        return '667' + g.replace(/./g, 0)
    })
        :
    ((parseInt(x) + 1) + '').replace(666, 667)
);

And now simply understand that the algorithm goes like this:

If there is already a 666 in the input,

replace it with a 667.
replace every digit after that with a 0.

else,

add one to the number.
NOTE: we are now guaranteed to have either no 666, a 666 at the end of the string, or a 666 somewhere else that already has zeroes going to the end (think "carrying" when doing "manual" addition).
if there's a 666, replace it with a 667.

Old version (doesn't work for 666666666):
    s='Enter number';x
  =prompt(           ''+
 s);x=+x+
(-~![]);
x=(''+x).replace('666',
666+([][         +[]]+[])
[+[]]['l         ength'[
 'repla'+       'ce'](
  / /g,'')]);alert(x)

To understand this, let's first beautify it:
s = 'Enter number';
x = prompt('' + s);
x = +x + (-~![]);
x = ('' + x).replace('666',666+([][+[]]+[])[+[]]['l         ength'['repla'+'ce'](/ /g,'')]);
alert(x);

Now let's remove useless things like '' + string and 'str' + 'ing', remove the unnecessary s variable, and change weirdness like -~![] into 1:
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666+"undefined"[0]['l         ength'['replace'](/ /g,'')]);
alert(x);

'l         ength'['replace'](/ /g,'') is simply "length":
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666+"undefined"[0].length);
alert(x);

And "undefined"[0] is "u", and "u".length is 1:
x = prompt('Enter number');
x = +x + 1;
x = ('' + x).replace('666', 666 + 1);
alert(x);

Now we're done! It should be pretty easy to understand now.

I like your answer but it fails for 666666666

@Michael Added new version! Works for 666666666, and the font of the 6 is fancier ;)

Huh - using ~1 for != -1 is pretty cool.

@WChargin Too bad that doesn't work in LiveScript. I know this isn't code golf but I have a golfed version in my post for fun.

It does work in LiveScript :). ~a.indexOf('b') generates the correct JS, try it on livescript.net !

Applescript
This site doesn't have enough Applescript answers.  Lets banish some demons!
property demon : "666"
property trinity : 1

on exorcise above possessed
    set possessed to possessed as text
    set relic to AppleScript's text item delimiters
    set AppleScript's text item delimiters to demon
    set deliverance to possessed's first text item
    if possessed is deliverance then
        set deliverance to possessed + trinity
    else
        set AppleScript's text item delimiters to trinity
        set compellingPower to ¬
            (count of possessed's characters) - ¬
            (count of deliverance's characters) - ¬
            (count of demon's characters)
        set deliverance to ¬
            deliverance & ¬
            demon + trinity & ¬
            last text item of (((10 ^ compellingPower) as integer) as text)
    end if
    set AppleScript's text item delimiters to relic
    return deliverance
end exorcise

log (exorcise above 666)
log (exorcise above 66666666)
log (exorcise above 1266612)
log (exorcise above 1212)

Log output:

(*667*)
(*66700000*)
(*1266700*)
(*1213*)

I'd wanted to get some of the more powerful quotes from The Exorcist into this, but that would have made this posted decidedly NSFW.  You can read the IMDB page instead.

How do you run this without having OS X?

I think Applescript is pretty much dependent on OSX http://stackoverflow.com/questions/7642299/what-are-the-alternatives-to-applescript-in-linux-how-are-they-different - I'm not aware of any ports to other platforms.  OS 9 did have a version of Applescript, though no guarantees that this script would run there.

It would have made the post Not For Safe Work? Dammit, my job isn't dangerous

@Cruncher oops ;-)

+1 for the choice of variable names (and because apple script is cool).

@DigitalTrauma — AppleScript existed way before Mac OS X.

@NicolasBarbulesco Yep.  I think my previous comment alluded to that.

Perl
You said we must not increment in a loop. I'm not using any mathematical operators at all! Here is a pure regex-substitution approach (no guarantees it's safe for your sanity).
#!/usr/bin/perl

$_ = <>;

s/$/ ~0123456789/;
s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g;
s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g;
s/(?!^)\G\d|(666)\d/${1}0/g;
s/666/667/g;

print($_)

The first three substitutions increment the number by one. I did solve that problem myself once, but it included a substitution that had to be looped until no more substitutions were made, so I used Andrew Cheong's approach instead.
The fourth substitution turns all digits following a 666 into zeros. The final substitution turns the remaining 666 into a 667.
As a bonus this will work with multiple integers in the input as long as they are separated by non-digit characters.

LiveScript
This is bending the rules. You see, you said I must not use a loop that adds one until it finds a correct result. So I subtract minus one instead!
nextId = (id) ->
  while (id + 1).toString!indexOf('666') != -1
    id -= -1
  id + 1

A golfed version in 53 48 45 bytes for fun:
n=(i)->(while~(i+1+'')indexOf(\666)=>i-=-1);i+1

Thanks to user1737909 for helping golf it further.
Tests
Requires Node.js with the LiveScript npm module or a compatible assert library.
assert = require \assert

assert.equal nextId(1), 2
assert.equal nextId(665), 667
assert.equal nextId(665999999), 667000000
assert.equal nextId(66600), 66700
assert.equal nextId(456667), 456670

It is going to fail horribly when you get to 665999, as your stack will explode.

Very clever. You should be writing RFCs to spot loopholes like that.

@TimWolla That's interesting. How did you find that?

@nyuszika7h: If you think about it, 666000 through 666999 will all fail... you'll be recursing at least 1000 times.

Why would you use recursion instead of looping here?

I don't have a particular reason, I guess.

My thought when I read the restriction on looping was to do recursion instead. (The letter of the rules vs. the spirit of the rules.)

you can use (a)b instead of (a).b and => instead of then

You can also use ~ instead of !=-1

@user1737909 That doesn't work in LiveScript, it compiles into while (bind$((i + 1 + '').indexOf('666'), 1)), which looks like an infinite loop to me; it hangs on n 1.

Definitely works for LiveScript : while~(i+1+'')indexOf(\666)=> compiles to the correct javascript. I guess you LS was while(i+1+'')indexOf(\666)~1 which is indeed incorrect (infix ~ is bind operator)

I think this is invalid since the question says f(665999999) returns 667000000 without having looped a million times.

Ruby
This is (I think) the first answer that works for 666666666. (Except the cheaty subtracting -1 answer. ;) )
x = gets.chomp.to_i + 1
p (x..x.to_s.gsub('666', '667').to_i).select{|i| !(i.to_s.index '666') }.min

I'm in a hurry now; explanation will be added later.
Update: much more efficient version (almost constant runtime I believe):
x = gets.chomp
if x.index '666'
    # replace ex. 6661234 with 6670000
    puts x.sub(/666(.*)/){ "667#{"0" * $1.length}" }
else
    # old algorithm (guaranteed to result in
    # 0 or 1 666s now)
    puts (x.to_i+1).to_s.sub(/666/, "667")
end

Actually, my answer works fine for 666666666.

Constant runtime is impossible. Even checking if a "666" exists is a linear problem. This is a strictly harder problem than that.

J
Finally, a good use for E.!
(({.~ , '667' {.!.'0'~ #@[ - ]) '666'&E. i. 1:) @ ": @ >:

In essence, we find the first position in which the argument has a full 666, and we replace that substring and everything after with 66700000... until the end.
Explained in detail:

":@>: - Increment by one and convert to string.
'666'&E. - Make a vector of booleans, true in each place that '666' begins in the string.
i.1: - Find the index of the first true in the vector, else return the length of the vector.
#@[-] - Length of the string (which is also the length of the vector) minus the result of i..
'667'{.!.'0'~ - Take a substring of '667' with a length of that result, padding on the right with '0' if necessary.
{.~ - Take a substring with the length of the original result from i..
, - Append the two together.

In use:
   f =: (({.~,'667'{.!.'0'~#@[-])'666'&E.i.1:)@":@>:
   f 1              NB. this leaves okay numbers untouched
2
   f 665999999      NB. properly handles multiple increments
667000000
   f 16266366646666 NB. only takes effect at sets of 3 sixes
16266366700000

And since this isn't a code golf, this doesn't have to get golfed to hell with crazy optimizations. Everybody wins!

PowerShell
($args[0]+1 -replace '(?<=666.*).','0') -replace '666', '667'

C#
148 137 chars
Was able to shave off a few chars thanks to @recursive
public static int f(int b){b++;var z=new Regex("666\\d*");var q=z.Replace(b+"","667",1);return int.Parse(q.PadRight((b+"").Length,'0'));}

Ungolfed:
public static int f(int b)
{
    b++;
    var z = new Regex("666[\\d]*");
    var q = z.Replace(b+"", "667", 1);
    return Int32.Parse(q.PadRight((b+"").Length, '0'));
}

Fiddle:
http://dotnetfiddle.net/XB83bf

The square brackets in your regex are unnecessary, and there are also a lot of syntactically unnecessary spaces.

Oh, and Int32 can be replaced with int.

@recursive You are correct, thanks!

Note this is a [tag:popularity-contest] and not [tag:code-golf].  Having said that if you feel shaving off characters will make your answer more popular, then go for it!

First I have seen of dotnetfiddle.net =) AWESOME!

I'm not sure you need the "public static " on the function. The question says that you need to make a function, not one that's publicly accessible. There exists a context in which the function works.

Haskell (70 characters)
Here is a simple implementation in Haskell.
import Data.List
import Data.Char

nextid :: Integer -> Integer
nextid = foldl' ((+).(*10)) 0 . purge . map digitToInt . show . (+1)
  where purge (6:6:6:xs) = 6 : 6 : 7 : map (const 0) xs
        purge (x:xs)     = fromIntegral x : purge xs
        purge []         = []

Firstly, it uses map digitToInt . show to convert a possibly evil ID to a list of digits.
Next, purge matches the evil pattern and replaces it with its good equivalent.
Finally, foldl' ((+).(*10)) 0 reduces the list of digits to one Integer.

Let's see if it works!
ghci> nextid 1
2
ghci> nextid 665
667
ghci> nextid 665999999
667000000
ghci> nextid 666666666
667000000
ghci> nextid 66600
66700
ghci> nextid 456667
456670
ghci> nextid 6660239486660239466
6670000000000000000

Looks good. And just for fun a golfed version.
f=read.w.show.(+1);w('6':'6':'6':t)="667"++(t>>"0");w(h:t)=h:w t;w t=t

Python
def next_id(id_num):
  id_num_p1=str(id_num+1)
  pieces=id_num_p1.split('666')
  if len(pieces)==1:
    return id_num+1
  next_id_str=pieces[0]+'667'+'0'*(len(id_num_p1)-len(pieces[0])-3)
  return int(next_id_str)

Perl
$_++;$_.=$/;s:666(.*):667 .'0'x($+[1]-$-[1]):e

Inline code which changes the content inside $_, a pretty standard ideology in perl. Can be used in conjunction with -p flag like this:
$ perl -p % <<< 66666
66700

J
No strings, loops or conditionals:
   next =: 3 :'<.(y+1)(+-|~)10^<:666 i:~666,1000|<.(y+1)%10^i.<.10^.>:y'

   next 1
2
   next 665
667
   next 665999999
667000000
   next 666666666
667000000
   next 66600
66700

Similarly to cardboard_box's solution, this separates the number into groups of three digits by dividing by powers of ten. It uses the index of the first occurrence of 666 to round the number up appropriately.

3 Different JavaScript answers:
1. JavaScript (ECMAScript 6)
f=x=>(a=b=c=0,[c?'0':a+(a=b)+(b=i)==666?(c='7'):i for(i of ""+(x+1))].join('')*1)

Converts the number to a string then iterates over each character until it finds 666 then it changes that last 6 to a 7 and outputs 0 for all following characters.
2. JavaScript (ECMAScript 6 Draft)
Recursive function without string manipulation:
g=(x,y=x+1,p=1)=>y?g(y%1e3==666?y*p+p:y>x?y:x,y/10|0,p*10):x

Or more verbosely:
function g(x,y=x+1,p=1)
{
  if ( y == 0 )
    return x;
  else if ( y % 1000 == 666 )
    return g( y*p+p, Math.floor(y/10), p*10 );
  else
    return g( Math.max(y, x), Math.floor(y/10), p*10 );
}

Tests:
g(5) // 6
g(65) // 66
g(665) // 667
g(66599) // 66700
g(66666) // 66700
g(6656665665) // 6656670000

3. JavaScript
Using regular expressions:
function h(x)(""+(x+1)).replace( /^(.*?)(666)(.*)$/, function(a,b,c,d)(b+667+d.replace(/./g,0)) )*1

Or (the same but using ECMAScript 6)
h=x=>(""+(x+1)).replace(/^(.*?)(666)(.*)$/,(a,b,c,d)=>b+667+d.replace(/./g,0))*1

With your first version, if you enter 6 septillion, 666 sextillion you get a return value of 6.667 so technically it's still there. Don't think it can be helped though.

1e20 is about the largest order of magnitude that JavaScript (at least in FireFox) will print as an integer without resorting to scientific notation.

Java
Isn't it enough to do this?
private static int nextId(int currentId) {
    String currentIdStr = String.valueOf(currentId);
    return currentIdStr.contains("666") ? Integer.parseInt(currentIdStr.replace("666", "667")) : ++currentId;
}

Close, but that should be String.valueOf(currentId + 1).

Oh right, I forgot that +1 thingy! :D

That conditional is useless; the original solution slightly modified per my suggestion will work too: return Integer.parseInt(String.valueOf(currentId + 1).replace("666", "667"));

Not true... 66600 would be returned as 66701, which is 1 too high.

R
Replacing 666 with 667 works.
f <- function(x) {
  x <- as.integer(x + 1)
  if (grepl(666, x)) {
    k <- regexpr(666, x)
    cat(substring(x, 1, k + 1), 7, rep(0, nchar(x) - k - 2), sep = "")
  }
  else cat(x)
}

Results
> f(1)
2
> f(665)
667
> f(665999999)
667000000
> f(666666666)
667000000
> f(66600)
66700
> f(126660)
126670
> f(126661)
126670
> f(666666666)
667000000

AWK
awk '{i=index(++$0,"666")}
      i{a=substr($0,1,i-1)
       b=substr($0,i+3)
       gsub(/./,0,b)
       $0=a"667"b}
      1
' <<_INPUT_
1
665
665999999
666666666
66600
_INPUT_

gives
2
667
667000000
667000000
66700

edit: 2nd solution
awk -F666 -vOFS=667 '{++$0;$1=$1}
    NF-1{for(gsub(/./,0,$2);NF>2;--NF){$2=$2 0 0 0
               for(i=length($NF);i;--i)$2=$2 0}}1
' <<_INPUT_
1
665
665999999
666666666
66600
1236661
_INPUT_

yields
2
667
667000000
667000000
66700
1236670

which doesn't seem to be correct answers. 665 should give 667, 66600 should give 66700 etc

Your results contain a lot of "666" substrings.

That's embarrassing. I fixed the 2(!) fence-post-errors I made because I forgot that awk indexes strings 1-based.

@Cruncher As explicitly stated in the question, f(665) returns 667 as it is asking for "the next integer that does not include 666"

I added a 2nd way that is a) more awkish and b) minimizes the use of string functions.

Batch
Simple iterated string manipulation.
@echo off

setLocal enableDelayedExpansion
set /a inp=%1+1
for /f usebackq %%a in (`powershell "&{'%inp%'.length-1}"`) do (
    set a len=%%a-2
    set chars=%%a
)

for /l %%b in (0, 1, %len%) do (
    if "!inp:~%%b,3!"=="666" (
        set inp=!inp:~0,%%b!667
        set /a a=%%b+3
        for /l %%c in (!a!, 1, %chars%) do set inp=!inp!0
        goto :break
    )
)

:break

echo %inp%

It starts at the first three characters of the number (as a string), and works its way to the end until it finds 666, it then replaces that 666 with 667, and loops to the length of the string adding zeros.
The test cases all produce the correct results.

Python
import re
def exorcise(number):
    number = str(number+1)
    i = re.compile("^(\d*?)(666)(\d*)$")
    if re.match(i,number):
        n = re.match(i,number).groups()
        return int(n[0]+"667"+"".join(["0"*len(n[2])]))
    return int(number)

perl, 45 bytes
A single regex with the /e flag does all the work here:
$_=<>+1;s/666(.*)$/"667".0 x length$1/e;print

perl, 36 just a sub, no bytes
A shorter version than my last solution, using a mix of arithmetic and regex ops.
sub{($_[0]+1)=~s/666(.*)/667$1/r-$1}

print+(<>+1)=~s/666(.*)/667$1/r-$1 (saved you a byte)(two more if you use say) - although the request was for a function so remove print+ and use sub{ ... }

SQL
To be precise, SQL Server 2012 Transact-SQL.
create function dbo.GoodIntegers( @i bigint )
returns bigint
as begin
    declare @s varchar(20) = cast( @i+1 as varchar(20) ) ;
    declare @badindex int = charindex( '666', @s ) ;
    declare @rv bigint  = cast (
        iif( @badindex = 0 ,
            @s ,
            concat( left( @s, @badindex - 1 ), '667', replicate( '0', len( @s ) - @badindex - 2 ) )
        ) as bigint
    ) ;
    return @rv ;
end ; -- function dbo.GoodIntegers

Julia
function f(x::Int)
    y = string(x+1)
    n = length(y)
    z = string(^("0",n))
    ~ismatch(r"6{3}", y) ?
    int(y) :
    while ismatch(r"6{3}",y)
        m = match(r"6{3}", y)
        y = string(y[1:m.offset+1], '7', z[m.offset+3:n])
    end
    int(y)
end

REPL results
julia> f(1)
2

julia> f(665)
667

julia> f(665999999)
667000000

julia> f(666666666)
667000000

julia> f(66600)
66700

julia> f(456667)
456670

C#
Am I doing it right
static int F(int n)
{
    n++;

    int a = 666;
    int b = 1;

    while (n >= b)
    {
        if (((n - a) / b) % 1000 == 0)
        {
            n += b;
        }

        a *= 10;
        b *= 10;
    }

    return n;
}

vba
Function f(num As Long) As Long
Dim SixPos As Long
Dim s As String
s = CStr(num)
SixPos = InStr(s, "666")
If SixPos = 0 Then
    s = CStr(num + 1)
    SixPos = InStr(s, "666")
End If
If SixPos Then
    Mid(s, SixPos + 2, 1) = "7"
    If Len(s) > SixPos + 2 Then
        Mid(s, SixPos + 3, Len(s) - SixPos + 3) = String$(Len(s) - SixPos + 3, "0")
    End If
End If

f = CLng(s)

End Function

In action:
Sub demo()
Debug.Print f(1) 'returns 2.
Debug.Print f(665) 'returns 667.
Debug.Print f(665999999) 'returns 667000000 without having looped a million times.
'(Following examples added since the question was first posed.)
Debug.Print f(666666666) 'also returns 667000000.
Debug.Print f(66600) 'returns 66700.
Debug.Print f(456667) 'returns 456670.
End Sub

result:
2
667
667000000
667000000
66700
456670

C
#include <stdlib.h>
#include <stdio.h>

int next(int a)
{
    for(int b=a+1,c=0,d=0; b>665 ;b/=10, c++)
        if(b%1000==666) {d=c; a=b;}

    a++;
    while(d --> 0) a*=10;

    return a;
}

void main(int a, char *v[])
{
    int c = a>1?atoi(v[1]):0;

    printf("%d\n",next(c));
}

OK - no bounds checking and far too much whitespace but it's not golf.  Also a fun bit of formatting in "while (d --> 0)".

C++
I know this isn't code-golf, but (a) some people have suggested that it is a good golf challenge, and (b) this is my first challenge/golf answer, I thought it would be fun, and if I do this here I don't get shown up in an actual golf challenge for being a terrible golfer. X)
Basically, replaced '666' with '667' works if you do it for the first instance in the number and then write out trailing 0s.
Golfed (175 155 chars):
#include<sstream>
int f(int x){std::stringstream s,o;s<<++x;x=0;for(char c=s.get();!s.eof();c=s.get())o<<((x+=c=='6')++==3?'7':--x>3?'0':c);o>>x;return x;}

Ungolfed:
#include<sstream>
int f(int x){
    std::stringstream s,o;
    s<<++x;    // Increment to next int.
    x=0;       // Reusing this to count 6s
    for(char c=s.get();!s.eof();c=s.get()){    // For each digit
        if (c=='6'){
           ++x;    // Count sixes...
        }
        if(x==3) {  // Devil's number!
            c='7'; // Output 7 here.
            ++x;   // Increment once more.
        } else if (x > 3) {
            c='0';    // Already replaced 666 with 667, so write out 0s
        }
        o<<c;   // Append digit
    }
    o>>x; // Get int
    return x;
}

I think you don't need x+=c=='6'?1:0, you can get away with x+=c=='6'. Haven't tried it, though.

Also, you left out the std:: before stringstream. It doesn't compile without that.

Added std::, thanks for that @nyuszika7h. I made the mistake of using an IDE that autogenerated 'using namespace std;' to test it in. -_- I will try the x+=c=='6' reduction, as well as looking at doing this with int digits rather than sstream chars...

Ruby
n=(gets.chomp.to_i+1).to_s
i=n.index("666")
if i!=nil
    n=n[0..i+1]+"7"+"0"*(n.length-i-3)
end
puts n

Java
public static int f(int i) {
    i++;
    i += findAdjustment(i);
    return i;
}

private static int findAdjustment(int i) {
    if (i < 666) {
        return 0;
    }
    int adjustment = findAdjustment(i / 10);
    if (adjustment != 0) {
        // Leftmost 666 found, fix adjustment by current last digit
        return adjustment * 10 - i % 10;
    } else if (i % 1000 == 666) {
        return 1; // This is leftmost 666, need to be corrected by 1
    } else {
        return 0; // no adjustment needed
    }
}

Using recursive function to find leftmost 666 and calculation how much to adjust the number when popping the call stack again.

I don't think this code is correct. What result does it give for input 666666666?

You are right, didn't realise that the input already could contain Evil numbers. So f(666666666) -> 667667667?

f(666666666) -> 667000000

@djhurio Seems I can not generate tests for edge cases today. Believe I have it fixed now, but the code is not so short any more.

@RogerLindsjö This is a popularity-contest, not a code-golf.

Python:
def f(b):
    b = `b+1`
    while '666' in b: b = b.replace('666','667',1)
    return int(b)

Or:
 f=lambda b:int(`b+1`.replace('666','667'))

I don't see how that works. Wouldn't that turn 666666 into 667667 instead of 667000?

@m.buettner Good point, I think I already have an solution.

PHP, 115 characters
<?php
function n($n){$p=strpos(++$n,'666');return($p>=0?substr($n,0,$p). 667 .str_repeat(0,-strlen($n)+$p+3):$n);}
?>

ungolfed:
<?php
function n($n)
{
    $p = strpos(++$n, '666');

    return($p >= 0
    ?
        substr($n, 0, $p) . 667 . str_repeat(0, -strlen($n) + $p + 3)
    :
        $n
    );
}
?>

Javascript (E6) 47 64
Even if it's not golf
Assuming positive 32 bit integers. NB +a is string concat, -a is numeric sub
F=x=>-(~x+'').replace(/666(.*)/,(s,a)=>667+a-a)

Usage
;[
F(6666),
F(1),
F(665),
F(665999999),
F(666666666),
F(66600),
F(456667)
]
[6670, 2, 667, 667000000, 667000000, 66700, 456670]

PHP
echo preg_match('/666/', $n+1)?preg_replace('/666/', '667', $n+1):$n+1;

Given 123666123, won't this produce 123667123? It should produce 123667000 for that input.

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