/** Testează dacă algoritmul naiv de ridicare la pătrat este mai eficient decât cel al lui Karatsuba **/
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_DIGITS 5000
#define TRIALS 1000

typedef unsigned long long u64;
typedef struct {
  int nd;
  int d[2 * MAX_DIGITS];
} big;

void write(big *a) {
  for (int i = a->nd - 1; i >= 0; i--) {
    putchar(a->d[i] + '0');
  }
  putchar('\n');
}

// Adaugă b în a. Presupune că a are cel puțin la fel de multe cifre ca b.
void sum(big *a, big *b) {
  int carry = 0;
  for (int i = 0; i < a->nd; i++) {
    a->d[i] += carry + ((i < b->nd) ? b->d[i] : 0);
    carry = (a->d[i] > 9);
    a->d[i] -= 10 * carry;
  }
  if (carry) {
    a->d[a->nd++] = 1;
  }
}

// Scade b din a.
void diff(big *a, big *b) {
  int borrow = 0;
  for (int i = 0; i < a->nd; i++) {
    a->d[i] -= borrow + ((i < b->nd) ? b->d[i] : 0);
    borrow = (a->d[i] < 0);
    a->d[i] += 10 * borrow;
  }
  while (a->nd && !a->d[a->nd - 1]) {
    a->nd--;
  }
}

void copy(big *dest, big *src, int from, int to) {
  dest->nd = to - from;
  for (int i = 0; i < dest->nd; i++) {
    dest->d[i] = src->d[from + i];
  }
}

// Înmulțește a cu 10^k
void shift(big *a, int k) {
  for (int i = a->nd - 1; i >= 0; i--) {
    a->d[i + k] = a->d[i];
  }
  for (int i = k - 1; i >= 0; i--) {
    a->d[i] = 0;
  }
  a->nd += k;
}

u64 toU64(big *a) {
  u64 result = 0;
  for (int i = a->nd - 1; i >= 0; i--) {
    result = 10 * result + a->d[i];
  }
  return result;
}

void fromU64(big *a, u64 d) {
  a->nd = 0;
  while (d) {
    a->d[a->nd++] = d % 10;
    d /= 10;
  }
}

// Pune în b numărul a^2.
void square(big *a, big *b) {
  b->nd = 2 * a->nd;
  for (int i = 0; i < b->nd; i++) {
    b->d[i] = 0;
  }
  for (int i = 0; i < a->nd; i++) {
    for (int j = 0; j < a->nd; j++) {
      b->d[i + j] += a->d[i] * a->d[j];
    }
  }

  int carry = 0;
  for (int i = 0; i < b->nd; i++) {
    b->d[i] += carry;
    carry = b->d[i] / 10;
    b->d[i] %= 10;
  }

  if (b->nd && !b->d[b->nd - 1]) {
    b->nd--;
  }
}

// Pune în b numărul a^2. Scrie a = xy și aplică algoritmul lui Karatsuba.
void squareKaratsuba(big *a, big *b) {
  big p, q, r;

  if (a->nd <= 9) {
    u64 d = toU64(a);
    d *= d;
    fromU64(b, d);
    return;
  }

  int n = (a->nd + 1) / 2; // Dacă numărul de cifre este impar, păstrăm mai multe în dreapta
  copy(&p, a, n, a->nd);   // p = x
  copy(&q, a, 0, n);       // q = y
  square(&p, b);           // b = x^2
  square(&q, &r);          // r = y^2
  sum(&q, &p);             // q = x + y
  square(&q, &p);          // p = (x + y)^2
  diff(&p, b);             // p = (x + y)^2 - x^2
  diff(&p, &r);            // p = (x + y)^2 - x^2 - y^2 = 2xy
  shift(b, 2 * n);         // b = x^2 * 10^(2n)
  shift(&p, n);            // p = 2xy * 10^n
  sum(b, &p);              // b = x^2 * 10^(2n) + 2xy * 10^n
  sum(b, &r);              // b = x^2 * 10^(2n) + 2xy * 10^n + y^2
}

int main(int argc, char **argv) {
  if (argc != 3) {
    fprintf(stderr, "Sintaxă: benchmark <nr. cifre> <strategie>\n");
    fprintf(stderr, "  unde strategie = 0 pentru naiv, 1 pentru Karatsuba\n");
    exit(1);
  }
  int numDigits = atoi(argv[1]);
  int strategy = atoi(argv[2]);
  srand(time(NULL));

  big n, n2;
  n.nd = numDigits;
  for (int i = 0; i < n.nd - 1; i++) {
    n.d[i] = rand() % 10;
  }
  n.d[n.nd - 1] = 1 + rand() % 9;

  for (int i = 0; i < TRIALS; i++) {
    if (strategy) {
      squareKaratsuba(&n, &n2);
    } else {
      square(&n, &n2);
    }
  }

  // write(&n);
  // write(&n2);
}