| 1 | #include "intx.cpp" |
| 2 | #include "fft.cpp" |
| 3 | intx fastmul(const intx &an, const intx &bn) { |
| 4 | string as = an.to_string(), bs = bn.to_string(); |
| 5 | int n = size(as), m = size(bs), l = 1, |
| 6 | len = 5, radix = 100000, |
| 7 | *a = new int[n], alen = 0, |
| 8 | *b = new int[m], blen = 0; |
| 9 | memset(a, 0, n << 2); |
| 10 | memset(b, 0, m << 2); |
| 11 | for (int i = n - 1; i >= 0; i -= len, alen++) |
| 12 | for (int j = min(len - 1, i); j >= 0; j--) |
| 13 | a[alen] = a[alen] * 10 + as[i - j] - '0'; |
| 14 | for (int i = m - 1; i >= 0; i -= len, blen++) |
| 15 | for (int j = min(len - 1, i); j >= 0; j--) |
| 16 | b[blen] = b[blen] * 10 + bs[i - j] - '0'; |
| 17 | while (l < 2*max(alen,blen)) l <<= 1; |
| 18 | cpx *A = new cpx[l], *B = new cpx[l]; |
| 19 | rep(i,0,l) A[i] = cpx(i < alen ? a[i] : 0, 0); |
| 20 | rep(i,0,l) B[i] = cpx(i < blen ? b[i] : 0, 0); |
| 21 | fft(A, l); fft(B, l); |
| 22 | rep(i,0,l) A[i] *= B[i]; |
| 23 | fft(A, l, true); |
| 24 | ull *data = new ull[l]; |
| 25 | rep(i,0,l) data[i] = (ull)(round(real(A[i]))); |
| 26 | rep(i,0,l-1) |
| 27 | if (data[i] >= (unsigned int)(radix)) { |
| 28 | data[i+1] += data[i] / radix; |
| 29 | data[i] %= radix; } |
| 30 | int stop = l-1; |
| 31 | while (stop > 0 && data[stop] == 0) stop--; |
| 32 | stringstream ss; |
| 33 | ss << data[stop]; |
| 34 | for (int i = stop - 1; i >= 0; i--) |
| 35 | ss << setfill('0') << setw(len) << data[i]; |
| 36 | delete[] A; delete[] B; |
| 37 | delete[] a; delete[] b; |
| 38 | delete[] data; |
| 39 | return intx(ss.str()); } |
| 40 | // vim: cc=60 ts=2 sts=2 sw=2: |