■ 카라츠바(Karatsuba) 알고리즘을 사용해 큰 수를 곱하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def multiplyWthKaratsubaAlgorithm(x, y): xString = str(x) yString = str(y) maximumLength = max(len(xString), len(yString)) if maximumLength == 1: return x * y middleIndex = maximumLength // 2 if middleIndex == 1: return x * y firstX = int(xString[:-middleIndex]) lastX = int(xString[-middleIndex:]) firstY = int(yString[:-middleIndex]) lastY = int(yString[-middleIndex:]) firstXY = multiplyWthKaratsubaAlgorithm(firstX, firstY) lastXY = multiplyWthKaratsubaAlgorithm(lastX, lastY) xy = multiplyWthKaratsubaAlgorithm((firstX + lastX), (firstY + lastY)) - firstXY - lastXY targetValue = firstXY * 10 ** (2 * middleIndex) + xy * 10 ** middleIndex + lastXY return targetValue x = 123456789012345678901234567890 y = 987654321098765432109876543210 targetValue = multiplyWthKaratsubaAlgorithm(x, y) print(targetValue) """ 121932631137021795226185032733622923332237463801111263526900 """ |