| 108 | |
| 109 | # multiply the DFTs of A and B and find A*B |
| 110 | def __multiply(self): |
| 111 | dft_a = self.__dft("A") |
| 112 | dft_b = self.__dft("B") |
| 113 | inverce_c = [[dft_a[i] * dft_b[i] for i in range(self.c_max_length)]] |
| 114 | del dft_a |
| 115 | del dft_b |
| 116 | |
| 117 | # Corner Case |
| 118 | if len(inverce_c[0]) <= 1: |
| 119 | return inverce_c[0] |
| 120 | # Inverse DFT |
| 121 | next_ncol = 2 |
| 122 | while next_ncol <= self.c_max_length: |
| 123 | new_inverse_c = [[] for i in range(next_ncol)] |
| 124 | root = self.root ** (next_ncol // 2) |
| 125 | current_root = 1 |
| 126 | # First half of next step |
| 127 | for j in range(self.c_max_length // next_ncol): |
| 128 | for i in range(next_ncol // 2): |
| 129 | # Even positions |
| 130 | new_inverse_c[i].append( |
| 131 | ( |
| 132 | inverce_c[i][j] |
| 133 | + inverce_c[i][j + self.c_max_length // next_ncol] |
| 134 | ) |
| 135 | / 2 |
| 136 | ) |
| 137 | # Odd positions |
| 138 | new_inverse_c[i + next_ncol // 2].append( |
| 139 | ( |
| 140 | inverce_c[i][j] |
| 141 | - inverce_c[i][j + self.c_max_length // next_ncol] |
| 142 | ) |
| 143 | / (2 * current_root) |
| 144 | ) |
| 145 | current_root *= root |
| 146 | # Update |
| 147 | inverce_c = new_inverse_c |
| 148 | next_ncol *= 2 |
| 149 | # Unpack |
| 150 | inverce_c = [ |
| 151 | complex(round(x[0].real, 8), round(x[0].imag, 8)) for x in inverce_c |
| 152 | ] |
| 153 | |
| 154 | # Remove leading 0's |
| 155 | while inverce_c[-1] == 0: |
| 156 | inverce_c.pop() |
| 157 | return inverce_c |
| 158 | |
| 159 | # Overwrite __str__ for print(); Shows A, B and A*B |
| 160 | def __str__(self): |