# Tag Info

133

C, 0.026119s (Mar 12 2016) #include <math.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define cache_size 16384 #define Phi_prec_max (47 * a) #define bit(k) (1ULL << ((k) & 63)) #define word(k) sieve[(k) >> 6] #define sbit(k) ((word(k >> 1) >...

84

Algebra, graph theory, Möbius inversion, research, and Java The symmetry group of the hexagon is the dihedral group of order 12, and is generated by a 60 degree rotation and a mirror flip across a diameter. It has 16 subgroups, but some of them are in non-trivial conjugacy groups (the ones which only have reflections have 3 choices of axis), so there are 10 ...

76

Python2.7 + Numpy 1.8.1: 10.242 s Fortran 90+: 0.029 s 0.003 s 0.022 s 0.010 s Damn straight you lost your bet! Not a drop of parallelization here too, just straight Fortran 90+. EDIT I've taken Guy Sirton's algorithm for permuting the array S (good find :D). I apparently also had the -g -traceback compiler flags active which were slowing this code down ...

69

Python 2.7 - 0.882s 0.283s (OP's original: 6.404s) Edit: Steven Rumbalski's optimization by precomputing F values. With this optimization cpython beats pypy's 0.365s. import itertools import operator import random n=6 iters = 1000 firstzero = 0 bothzero = 0 choicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n)) for S in itertools.product([-...

67

C++ bit magic 0.84ms with simple RNG, 1.67ms with c++11 std::knuth 0.16ms with slight algorithmic modification (see edit below) The python implementation runs in 7.97 seconds on my rig. So this is 9488 to 4772 times faster depending on what RNG you choose. #include <iostream> #include <bitset> #include <random> #include <chrono> #...

45

Rust: 0.011s Original Python: 8.3 A straight translation of the original Python. extern crate rand; use rand::Rng; static N: uint = 6; static ITERS: uint = 1000; fn convolve<T: Num>(into: &mut [T], a: &[T], b: &[T]) { // we want a to be the longest array if a.len() < b.len() { convolve(into, b, a); return ...

41

C, 112 bytes, 28 TB/s, score ≈ 0.008 long b[9<<21];main(){for(b=write(*b=1,wmemset(b+8,'\ny\ny',1<<25),1<<27)/2;b=b*=2;ioctl(1,'@ ”\r',b));} (If you’re having trouble copying and pasting this, replace the multicharacter constant '@ ”\r' with '@ \x94\r' or 1075876877.) This writes 128 MiB of y\ns to stdout, and then ...

39

C++ (VS 2012) - 0.026s 0.015s Python 2.7.6/Numpy 1.8.1 - 12s Speedup ~x800. The gap would be a lot smaller if the convolved arrays were very large... #include <vector> #include <iostream> #include <ctime> using namespace std; static unsigned int seed = 35; int my_random() { seed = seed*1664525UL + 1013904223UL; // numerical ...

39

After much trial and error, with the goal of not resorting to Assembly while achieving the best single-threaded performance, this is my entry: #include <unistd.h> #define unlikely(e) __builtin_expect((e), 0) #define mcpy(d, s, n) __builtin_memcpy((d), (s), (n)) #define CACHELINE 64 #define PGSIZE 4096 #define ALIGNED_BUF 65536 #define FIZZ &...

35

Mini-Flak, 6851113 cycles The program (literally) I know most people aren't likely expecting a Mini-Flak quine to be using unprintable characters and even multi-byte characters (making the encoding relevant). However, this quine does, and the unprintables, combined with the size of the quine (93919 characters encoded as 102646 bytes of UTF-8), make it ...

33

Bash, 3 bytes, 1.9 GB/s yes Try it online! Admittedly this is a troll solution, but the rules do not explicitly forbid it, and it should get you a value close to 3, which is not bad.

25

C99/C++, 8.9208s (28 Feb 2016) #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> uint64_t popcount( uint64_t v ) { v = (v & 0x5555555555555555ULL) + ((v>>1) & 0x5555555555555555ULL); v = (v & 0x3333333333333333ULL) + ((v>>2) & ...

24

Python A closed-form formula of p(n) is An exponential generating function of p(n) is where I_0(x) is the modified Bessel function of the first kind. Edit on 2015-06-11: - updated the Python code. Edit on 2015-06-13: - added a proof of the above formula. - fixed the time_limit. - added a PARI/GP code. Python def solve(): # straightforward ...

22

I was struggling to get more than 2.75GB/s on my rig but then I realised I wasn't compiling with -O3 which bumped me up to 6.75GB/s. #include <stdio.h> #include <string.h> #include <unistd.h> char buf; char out[65536 + 4096] = "1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\n"; int main(int argc, char **argv) { const int o = { 4,...

21

C Takes 0.015s on my machine, with OP's original code taking ~ 7.7s. Tried to optimize by generating the random array and convolving in the same loop, but it doesn't seem to make a lot of difference. The first array is generated by taking an integer, write it out in binary, and change all 1 to -1 and all 0 to 1. The rest should be very straightforward. ...

21

Python 2.7 on PyPy, {2404}3{1596} (~10^4000) ...

20

Nimrod (N=22) import math, locks const N = 20 M = N + 1 FSize = (1 shl N) FMax = FSize - 1 SStep = 1 shl (N-1) numThreads = 16 type ZeroCounter = array[0..M-1, int] ComputeThread = TThread[int] var leadingZeros: ZeroCounter lock: TLock innerProductTable: array[0..FMax, int8] proc initInnerProductTable = for i in 0..FMax: ...

20

Python, n≈108 def magic_sequences(n): if n==4: return (1, 2, 1, 0),(2, 0, 2, 0) elif n==5: return (2, 1, 2, 0, 0), elif n>=7: return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0), else: return () This uses the fact, which I'll prove, that the only Magic sequences of length n are: [1, 2, 1, 0] and [2, 0, 2, 0] for n=4 [...

17

J I don't expect to beat out any compiled languages, and something tells me it'd take a miraculous machine to get less than 0.09 s with this, but I'd like to submit this J anyway, because it's pretty slick. NB. constants num =: 6 iters =: 1000 NB. convolve NB. take the multiplication table */ NB. then sum along the NE-SW diagonals ...

17

Perl - 9.3X faster...830% improvement On my ancient netbook, the OP's code takes 53 seconds to run; Alistair Buxton's version takes about 6.5 seconds, and the following Perl version takes about 5.7 seconds. use v5.10; use strict; use warnings; use Algorithm::Combinatorics qw( variations_with_repetition ); use List::Util qw( any sum ); use List::MoreUtils ...

16

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; 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 ...

16

C99 - 3x3 board in 0.084s 2020 edit/disclaimer: See comments section. It looks like there may have been errors in the original code. Proceed to the remainder of this answer with some skepticism until it is fixed. Edit: I refactored my code and did some deeper analysis on the results. Further Edits: Added pruning by symmetries. This makes 4 algorithm ...

16

128,673,515 cycles Try it online Explanation The reason that Miniflak quines are destined to be slow is Miniflak's lack of random access. To get around this I create a block of code that takes in a number and returns a datum. Each datum represents a single character like before and the main code simply queries this block for each one at a time. This ...

15

C Introduction As commented by David Carraher, the simplest way of analysing the hexagon tiling seemed to be to take advantage of its isomorphism with the 3 dimensional Young Diagram, essentially an x,y square filled with integer height bars whose z heights must stay the same or increase as the z axis is approached. I started with an algorithm for finding ...

15

Python 2 (PyPy 4.0), 2.36961s (Feb 29 2016) def Phi(m, b): if not b: return m if not m: return 0 if m >= 800: return Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1) t = b * 800 + m if not Phi_memo[t]: Phi_memo[t] = Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1) return Phi_memo[t] x = int(input()) ...

15

C++ No more naive approach. Only evaluate inside the ellipsoid. Uses the armadillo, ntl, gsl and pthread libraries. Install using apt-get install libarmadillo-dev libntl-dev libgsl-dev Compile the program using something like: g++ -Wall -std=c++11 -O3 -fno-math-errno -funsafe-math-optimizations -ffast-math -fno-signed-zeros -fno-trapping-math -fomit-...

14

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 ...

14

Nimrod: ~38,667 (580,000,000/15,000) This answer uses a pretty simple approach. The code employs a simple prime number sieve that stores the prime of the smallest prime power in each slot for composite numbers (zero for primes), then uses dynamic programming to construct the totient function over the same range, then sums the results. The program spends ...

14

gcc C++ n ≈ 36 (57 seconds on my system) Uses Glynn formula with a Gray code for updates if all column sums are even, otherwise uses Ryser's method. Threaded and vectorized. Optimized for AVX, so don't expect much on older processors. Don't bother with n>=35 for a matrix with only +1's even if your system is fast enough since the signed 128 bit ...

14

Haskell import Control.Parallel.Strategies import qualified Data.Vector.Unboxed as V import qualified Data.Vector as VB type Poly = V.Vector Int type Matrix = VB.Vector ( VB.Vector Poly ) constpoly :: Int -> Int -> Poly constpoly n c = V.generate (n+1) (\i -> if i==0 then c else 0) add :: Poly -> Poly -> Poly add = V.zipWith (+) ...

Only top voted, non community-wiki answers of a minimum length are eligible