Skip to main content
Code Golf

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
added 19 characters in body
Source Link
miles
miles
  • 17k
  • 2
  • 30
  • 94
#define T(x) ((x)*((x)-1)/2)
#define S 1
#define J (1<<S)
#define TYPE int

#include <iostream>
#include <vector>
#include <string>
#include <pthread.h>
#include <x86intrin.h>

using namespace std;

struct H {
    int *b, s, *g, w, t;
    TYPE *b, *g;
};

void *solve(void *a);
void hafnian(intTYPE *b, int s, intTYPE *g, int w, int t);

int n, m, ti = 0,0;
TYPE r[J] = {0};
pthread_t pool[J];

int main(void) {
    vector<int> a;
    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0' || s[i] == '1')
            a.push_back((s[i-1] == '-' ? -1 : 1)*(s[i] - '0'));

    for (n = 1; 4*n*n < a.size(); n++);
    m = n+1;

    intTYPE z[T(2*n)*m] = {0}, g[m] = {0};

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k)*m] = a[j*2*n+k];
    g[0] = 1;

    hafnian(z, 2*n, g, 1, -1);

    intTYPE h = 0;
    for (int t = 0; t < ti; t++) {
        pthread_join(pool[t], NULL);
        h += r[t];
    }

    cout << h << endl;

    return 0;
}

void *solve(void *a) {
    H *p = reinterpret_cast<H*>(a);
    hafnian(p->b, p->s, p->g, p->w, p->t);
    delete[] p->b;
    delete[] p->g;
    delete p;
    return NULL;
}

void hafnian(intTYPE *b, int s, intTYPE *g, int w, int t) {
    if (t == -1 && (n < S || s/2 == n-S)) {
        H *p = new H;
        intTYPE *c = new int[TTYPE[T(s)*m], *e = new int[m];TYPE[m];
        copy(b, b+T(s)*m, c);
        copy(g, g+m, e);
        p->b = c;
        p->s = s;
        p->g = e;
        p->w = w;
        p->t = ti;
        pthread_create(pool+ti, NULL, solve, p);
        ti++;
    }
    else if (s > 0) {
        intTYPE c[T(s-2)*m], e[m];
        copy(b, b+T(s-2)*m, c);
        hafnian(c, s-2, g, -w, t);
        copy(g, g+m, e);

        for (int u = 0; u < n; u++) {
            intTYPE *d = e+u+1,
                  p = g[u], *x = b+(T(s)-1)*m;
            for (int v = 0; v < n-u; v++)
                d[v] += p*x[v];
        }

        for (int j = 1; j < s-2; j++)
            for (int k = 0; k < j; k++)
                for (int u = 0; u < n; u++) {
                    intTYPE *d = c+(T(j)+k)*m+u+1,
                          p = b[(T(s-2)+j)*m+u], *x = b+(T(s-1)+k)*m,
                          q = b[(T(s-2)+k)*m+u], *y = b+(T(s-1)+j)*m;
                    for (int v = 0; v < n-u; v++)
                        d[v] += p*x[v] + q*y[v];
                }

        hafnian(c, s-2, e, w, t);
    }
    else
        r[t] += w*g[n];
}

Try it online!Try it online! (13s for n = 24)

The splits the work in half, so the value of S should be log2(#threads). It uses a struct now so theThe types can easily be changed between int, long, float, and double by modifying the value of #define TYPE.

#define T(x) ((x)*((x)-1)/2)
#define S 1
#define J (1<<S)

#include <iostream>
#include <vector>
#include <string>
#include <pthread.h>
#include <x86intrin.h>

using namespace std;

struct H {
    int *b, s, *g, w, t;
};

void *solve(void *a);
void hafnian(int *b, int s, int *g, int w, int t);

int n, m, ti = 0, r[J] = {0};
pthread_t pool[J];

int main(void) {
    vector<int> a;
    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0' || s[i] == '1')
            a.push_back((s[i-1] == '-' ? -1 : 1)*(s[i] - '0'));

    for (n = 1; 4*n*n < a.size(); n++);
    m = n+1;

    int z[T(2*n)*m] = {0}, g[m] = {0};

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k)*m] = a[j*2*n+k];
    g[0] = 1;

    hafnian(z, 2*n, g, 1, -1);

    int h = 0;
    for (int t = 0; t < ti; t++) {
        pthread_join(pool[t], NULL);
        h += r[t];
    }

    cout << h << endl;

    return 0;
}

void *solve(void *a) {
    H *p = reinterpret_cast<H*>(a);
    hafnian(p->b, p->s, p->g, p->w, p->t);
    delete[] p->b;
    delete[] p->g;
    delete p;
    return NULL;
}

void hafnian(int *b, int s, int *g, int w, int t) {
    if (t == -1 && (n < S || s/2 == n-S)) {
        H *p = new H;
        int *c = new int[T(s)*m], *e = new int[m];
        copy(b, b+T(s)*m, c);
        copy(g, g+m, e);
        p->b = c;
        p->s = s;
        p->g = e;
        p->w = w;
        p->t = ti;
        pthread_create(pool+ti, NULL, solve, p);
        ti++;
    }
    else if (s > 0) {
        int c[T(s-2)*m], e[m];
        copy(b, b+T(s-2)*m, c);
        hafnian(c, s-2, g, -w, t);
        copy(g, g+m, e);

        for (int u = 0; u < n; u++) {
            int *d = e+u+1,
                 p = g[u], *x = b+(T(s)-1)*m;
            for (int v = 0; v < n-u; v++)
                d[v] += p*x[v];
        }

        for (int j = 1; j < s-2; j++)
            for (int k = 0; k < j; k++)
                for (int u = 0; u < n; u++) {
                    int *d = c+(T(j)+k)*m+u+1,
                         p = b[(T(s-2)+j)*m+u], *x = b+(T(s-1)+k)*m,
                         q = b[(T(s-2)+k)*m+u], *y = b+(T(s-1)+j)*m;
                    for (int v = 0; v < n-u; v++)
                        d[v] += p*x[v] + q*y[v];
                }

        hafnian(c, s-2, e, w, t);
    }
    else
        r[t] += w*g[n];
}

Try it online! (13s for n = 24)

The splits the work in half, so the value of S should be log2(#threads). It uses a struct now so the types can easily be changed between int, float, and double.

#define T(x) ((x)*((x)-1)/2)
#define S 1
#define J (1<<S)
#define TYPE int

#include <iostream>
#include <vector>
#include <string>
#include <pthread.h>

using namespace std;

struct H {
    int s, w, t;
    TYPE *b, *g;
};

void *solve(void *a);
void hafnian(TYPE *b, int s, TYPE *g, int w, int t);

int n, m, ti = 0;
TYPE r[J] = {0};
pthread_t pool[J];

int main(void) {
    vector<int> a;
    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0' || s[i] == '1')
            a.push_back((s[i-1] == '-' ? -1 : 1)*(s[i] - '0'));

    for (n = 1; 4*n*n < a.size(); n++);
    m = n+1;

    TYPE z[T(2*n)*m] = {0}, g[m] = {0};

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k)*m] = a[j*2*n+k];
    g[0] = 1;

    hafnian(z, 2*n, g, 1, -1);

    TYPE h = 0;
    for (int t = 0; t < ti; t++) {
        pthread_join(pool[t], NULL);
        h += r[t];
    }

    cout << h << endl;

    return 0;
}

void *solve(void *a) {
    H *p = reinterpret_cast<H*>(a);
    hafnian(p->b, p->s, p->g, p->w, p->t);
    delete[] p->b;
    delete[] p->g;
    delete p;
    return NULL;
}

void hafnian(TYPE *b, int s, TYPE *g, int w, int t) {
    if (t == -1 && (n < S || s/2 == n-S)) {
        H *p = new H;
        TYPE *c = new TYPE[T(s)*m], *e = new TYPE[m];
        copy(b, b+T(s)*m, c);
        copy(g, g+m, e);
        p->b = c;
        p->s = s;
        p->g = e;
        p->w = w;
        p->t = ti;
        pthread_create(pool+ti, NULL, solve, p);
        ti++;
    }
    else if (s > 0) {
        TYPE c[T(s-2)*m], e[m];
        copy(b, b+T(s-2)*m, c);
        hafnian(c, s-2, g, -w, t);
        copy(g, g+m, e);

        for (int u = 0; u < n; u++) {
            TYPE *d = e+u+1,
                  p = g[u], *x = b+(T(s)-1)*m;
            for (int v = 0; v < n-u; v++)
                d[v] += p*x[v];
        }

        for (int j = 1; j < s-2; j++)
            for (int k = 0; k < j; k++)
                for (int u = 0; u < n; u++) {
                    TYPE *d = c+(T(j)+k)*m+u+1,
                          p = b[(T(s-2)+j)*m+u], *x = b+(T(s-1)+k)*m,
                          q = b[(T(s-2)+k)*m+u], *y = b+(T(s-1)+j)*m;
                    for (int v = 0; v < n-u; v++)
                        d[v] += p*x[v] + q*y[v];
                }

        hafnian(c, s-2, e, w, t);
    }
    else
        r[t] += w*g[n];
}

Try it online! (13s for n = 24)

The splits the work in half, so the value of S should be log2(#threads). The types can easily be changed between int, long, float, and double by modifying the value of #define TYPE.

deleted 700 characters in body
Source Link
miles
miles
  • 17k
  • 2
  • 30
  • 94
#define T(x) ((x)*((x)-1)/2)
#define S 1 // set to lg2(#threads)
#define J (1 << S1<<S)

#include <iostream>
#include <algorithm><vector>
#include <string>
#include <vector><pthread.h>
#include <pthread<x86intrin.h>

using namespace std;

struct H {
    int *b, s, *g, w, t;
};

void *solve(void *a);
void hafnian(int *b, int s, int *g, int w, int t);

int n, tim, res[J]ti = 0, *pw[J];r[J] = {0};
pthread_t pool[J];

int main(void) {
    stringvector<int> s;a;
    vector<int>string a;
s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ' || s[i] == '[' || s[i] == ']''0' || s[i] == ',''1')
            continue;
        if a.push_back(s[i](s[i-1] == '-') {
           ? a.push_back(-1);
            i++;
        }
        else
           : a.push_back(1)*(s[i] ==- '0') ? 0 : 1);
    }

    for (n = 1; 4*n*n < a.size(); n++);
 
    intm z[(T(2*n)+1)*(n+1)+3];= n+1;

    fill(z,int z+(Tz[T(2*n)+1)*(n+1)+3*m] = {0}, g[m] = {0)};

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k+1)*(n+1+k)+3]*m] = a[j*2*n+k];

    z[0] = 2*n;
    z[1]g[0] = 1;
    z[2] = -1;
    z[3] = 1;
    fillhafnian(z+4z, z+n+42*n, 0);
    fill(resg, res+J1, 0);

    solve(z-1);

    int hafnianh = 0;
    for (int it = 0; it < ti; i++t++) {
        pthread_join(pool[i]pool[t], NULL);
        hafnianh += res[i];
        delete[] pw[i];r[t];
    }

    cout << hafnianh << endl;

    return 0;
}

void *solve(void *a) {
    intH *z*p = reinterpret_cast<int*>reinterpret_cast<H*>(a);
    int &s = z[0]hafnian(p->b, &w = z[1]p->s, &i = z[2]p->g, *g = z+3p->w, *bp->t);
 = z+n+4;

  delete[] p->b;
 if (s == 0)delete[] {p->g;
    delete p;
   res[i] +=return w*g[n];NULL;
}

  void hafnian(int *b, int s, int return*g, NULL;
int w, int t) }
{
    if (it == -1 && (n <=< S || s/2 == n-S)) {
        pw[ti]H *p = new int[(T(s)+1)*(n+1)+3];H;
        copy(z,int z+(T*c = new int[T(s)+1)*(n+1)+3*m], pw[ti]);*e = new int[m];
        pw[ti][2]copy(b, =b+T(s)*m, ti;c);
        pthread_createcopy(pool+ti, NULLg, solveg+m, pw[ti]e);
        ti++;
p->b = c;
        returnp->s NULL;
= s;
   }

    int m[(T(sp-2)+1)*(n+1)+3];>g = e;
    int &t = m[0], &op->w = m[1],w;
 &r = m[2], *e = m+3, *c p->t = m+n+4;
ti;
    t = s-2;
    copypthread_create(gpool+ti, g+n+1NULL, esolve, p);
    r = i;
  ti++;
    for}
 (int j = 1;else jif <(s t;> j++0) {
        for (int k = 0; k < j; k++c[T(s-2)
   *m], e[m];
        copy(b+(T(j+2)+k+2)*(n+1)b, b+(T(j+2)+k+3)*b+T(n+1s-2)*m, c+(T(j)+k)*(n+1)c);

    o = -w;
    solve(m);

    for hafnian(int u = 0;c, us-2, <g, n;-w, u++t) {;
        int *d = e+u+1copy(g, p =g+m, g[u];e);

        for (int vu = 0; v < (n-u)/4*4; v< +=n; 4u++) {
            d[v]   += p*b[v];
           int d[v+1]*d +== p*b[v+1];e+u+1,
            d[v+2] += p*b[v+2];
         p = g[u], d[v+3]*x +== p*b[v+3];b+(T(s)-1)*m;
        }
        for (int v = (n-u)/4*4;0; v < n-u; v++)
            d[v]    d[v] += p*b[v];p*x[v];
        }

        for (int j = 1; j < t;s-2; j++) {
            for (int k = 0; k < j; k++) {
                for (int u = 0; u < n; u++) {
                    int *d = c+(T(j)+k)*(n+1)+u+1*m+u+1,
                         p = b[Tb[(j+2)*T(n+1s-2)+u]+j)*m+u], *x = b+(T(k+2)+1s-1)*(n+1+k)*m,
                         q = b[Tb[(k+2)*T(n+1s-2)+u]+k)*m+u], *y = b+(T(j+2)+1s-1)*(n+1+j);*m;
                    for (int v = 0; v < (n-uu; v++)/4*4; 
 v += 4) {
                    d[v]   += p*x[v]   + q*y[v];
                    d[v+1] += p*x[v+1] + q*y[v+1];
                    d[v+2] += p*x[v+2] + q*y[v+2];
                    d[v+3] += p*x[v+3] + q*y[v+3];
                }
          
       for hafnian(int v =c, (ns-u)/4*4; v2, <e, n-u;w, v++t)
                    d[v]   += p*x[v]   + q*y[v];
            };
        }
    }
else
    o = w;
    solve(m);

   r[t] return+= NULL;w*g[n];
}

Try it online!Try it online! (15s13s for n = 24)

Based on the faster Python [implementation][py-imp]implementation in my other post. Edit the second line to #define S 3 on your 8-core machine and compile with g++ -pthread -march=native -O3O2 -pthreadftree-vectorize.

The splits the work in half, so the value of S should be log2(#threads). It uses a struct now so the types can easily be changed between int, float, and double.

#define T(x) ((x)*((x)-1)/2)
#define S 1 // set to lg2(#threads)
#define J (1 << S)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <pthread.h>

using namespace std;

void *solve(void *a);

int n, ti, res[J], *pw[J];
pthread_t pool[J];

int main(void) {
    string s;
    vector<int> a;

    getline(cin, s);

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ' || s[i] == '[' || s[i] == ']' || s[i] == ',')
            continue;
        if (s[i] == '-') {
            a.push_back(-1);
            i++;
        }
        else
            a.push_back((s[i] == '0') ? 0 : 1);
    }

    for (n = 1; 4*n*n < a.size(); n++);
 
    int z[(T(2*n)+1)*(n+1)+3];
    fill(z, z+(T(2*n)+1)*(n+1)+3, 0);

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k+1)*(n+1)+3] = a[j*2*n+k];

    z[0] = 2*n;
    z[1] = 1;
    z[2] = -1;
    z[3] = 1;
    fill(z+4, z+n+4, 0);
    fill(res, res+J, 0);

    solve(z);

    int hafnian = 0;
    for (int i = 0; i < ti; i++) {
        pthread_join(pool[i], NULL);
        hafnian += res[i];
        delete[] pw[i];
    }

    cout << hafnian << endl;

    return 0;
}

void *solve(void *a) {
    int *z = reinterpret_cast<int*>(a);
    int &s = z[0], &w = z[1], &i = z[2], *g = z+3, *b = z+n+4;

    if (s == 0) {
        res[i] += w*g[n];

        return NULL;
    }

    if (i == -1 && (n <= S || s/2 == n-S)) {
        pw[ti] = new int[(T(s)+1)*(n+1)+3];
        copy(z, z+(T(s)+1)*(n+1)+3, pw[ti]);
        pw[ti][2] = ti;
        pthread_create(pool+ti, NULL, solve, pw[ti]);
        ti++;

        return NULL;
    }

    int m[(T(s-2)+1)*(n+1)+3];
    int &t = m[0], &o = m[1], &r = m[2], *e = m+3, *c = m+n+4;

    t = s-2;
    copy(g, g+n+1, e);
    r = i;

    for (int j = 1; j < t; j++)
        for (int k = 0; k < j; k++)
            copy(b+(T(j+2)+k+2)*(n+1), b+(T(j+2)+k+3)*(n+1), c+(T(j)+k)*(n+1));

    o = -w;
    solve(m);

    for (int u = 0; u < n; u++) {
        int *d = e+u+1, p = g[u];
        for (int v = 0; v < (n-u)/4*4; v += 4) {
            d[v]   += p*b[v];
            d[v+1] += p*b[v+1];
            d[v+2] += p*b[v+2];
            d[v+3] += p*b[v+3];
        }
        for (int v = (n-u)/4*4; v < n-u; v++)
            d[v]   += p*b[v];
    }

    for (int j = 1; j < t; j++) {
        for (int k = 0; k < j; k++) {
            for (int u = 0; u < n; u++) {
                int *d = c+(T(j)+k)*(n+1)+u+1,
                     p = b[T(j+2)*(n+1)+u], *x = b+(T(k+2)+1)*(n+1),
                     q = b[T(k+2)*(n+1)+u], *y = b+(T(j+2)+1)*(n+1);
                for (int v = 0; v < (n-u)/4*4; v += 4) {
                    d[v]   += p*x[v]   + q*y[v];
                    d[v+1] += p*x[v+1] + q*y[v+1];
                    d[v+2] += p*x[v+2] + q*y[v+2];
                    d[v+3] += p*x[v+3] + q*y[v+3];
                }
                for (int v = (n-u)/4*4; v < n-u; v++)
                    d[v]   += p*x[v]   + q*y[v];
            }
        }
    }

    o = w;
    solve(m);

    return NULL;
}

Try it online! (15s for n = 24)

Based on the faster Python [implementation][py-imp] in my other post. Edit the second line to #define S 3 on your 8-core machine and compile with g++ -march=native -O3 -pthread.

#define T(x) ((x)*((x)-1)/2)
#define S 1
#define J (1<<S)

#include <iostream>
#include <vector>
#include <string>
#include <pthread.h>
#include <x86intrin.h>

using namespace std;

struct H {
    int *b, s, *g, w, t;
};

void *solve(void *a);
void hafnian(int *b, int s, int *g, int w, int t);

int n, m, ti = 0, r[J] = {0};
pthread_t pool[J];

int main(void) {
    vector<int> a;
    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0' || s[i] == '1')
            a.push_back((s[i-1] == '-' ? -1 : 1)*(s[i] - '0'));

    for (n = 1; 4*n*n < a.size(); n++);
    m = n+1;

    int z[T(2*n)*m] = {0}, g[m] = {0};

    for (int j = 1; j < 2*n; j++)
        for (int k = 0; k < j; k++)
            z[(T(j)+k)*m] = a[j*2*n+k];
    g[0] = 1;

    hafnian(z, 2*n, g, 1, -1);

    int h = 0;
    for (int t = 0; t < ti; t++) {
        pthread_join(pool[t], NULL);
        h += r[t];
    }

    cout << h << endl;

    return 0;
}

void *solve(void *a) {
    H *p = reinterpret_cast<H*>(a);
    hafnian(p->b, p->s, p->g, p->w, p->t);
    delete[] p->b;
    delete[] p->g;
    delete p;
    return NULL;
}

void hafnian(int *b, int s, int *g, int w, int t) {
    if (t == -1 && (n < S || s/2 == n-S)) {
        H *p = new H;
        int *c = new int[T(s)*m], *e = new int[m];
        copy(b, b+T(s)*m, c);
        copy(g, g+m, e);
        p->b = c;
        p->s = s;
        p->g = e;
        p->w = w;
        p->t = ti;
        pthread_create(pool+ti, NULL, solve, p);
        ti++;
    }
    else if (s > 0) {
        int c[T(s-2)*m], e[m];
        copy(b, b+T(s-2)*m, c);
        hafnian(c, s-2, g, -w, t);
        copy(g, g+m, e);

        for (int u = 0; u < n; u++) {
            int *d = e+u+1,
                 p = g[u], *x = b+(T(s)-1)*m;
            for (int v = 0; v < n-u; v++)
                d[v] += p*x[v];
        }

        for (int j = 1; j < s-2; j++)
            for (int k = 0; k < j; k++)
                for (int u = 0; u < n; u++) {
                    int *d = c+(T(j)+k)*m+u+1,
                         p = b[(T(s-2)+j)*m+u], *x = b+(T(s-1)+k)*m,
                         q = b[(T(s-2)+k)*m+u], *y = b+(T(s-1)+j)*m;
                    for (int v = 0; v < n-u; v++) 
                        d[v] += p*x[v] + q*y[v];
                }
 
        hafnian(c, s-2, e, w, t);
    }
    else
        r[t] += w*g[n];
}

Try it online! (13s for n = 24)

Based on the faster Python implementation in my other post. Edit the second line to #define S 3 on your 8-core machine and compile with g++ -pthread -march=native -O2 -ftree-vectorize.

The splits the work in half, so the value of S should be log2(#threads). It uses a struct now so the types can easily be changed between int, float, and double.

added 100 characters in body
Source Link
miles
miles
  • 17k
  • 2
  • 30
  • 94
Source Link
miles
miles
  • 17k
  • 2
  • 30
  • 94