Last active
November 30, 2021 05:24
-
-
Save wsams/12723fc953e7f745deafba7f45b6a7b1 to your computer and use it in GitHub Desktop.
Multiply two large integers (1000s of digits - or more given enough time) with Python, and Node.JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Usage: node multiply.js <positive integer a> <positive integer b> | |
*/ | |
function mult(aArr, bArr) { | |
const as = aArr.reverse().join(''); | |
const bs = bArr.reverse().join(''); | |
let rowa = []; | |
let remainder = 0; | |
let rows = []; | |
for (let bx = 0; bx < bs.length; bx++) { | |
const bval = bs[bx]; | |
rowa = bx > 0 ? Array(bx).fill(0) : []; | |
for (let ax = 0; ax < as.length; ax++) { | |
const aval = as[ax]; | |
const c = bval * aval; | |
const cs = c.toString(); | |
const cl = cs.length; | |
if (cl === 2) { | |
const save = parseInt(cs[1]); | |
rowa.unshift(save + remainder); | |
remainder = parseInt(cs[0]); | |
} else if (cl === 1) { | |
const save = parseInt(cs[0]); | |
rowa.unshift(save + remainder); | |
remainder = 0; | |
} | |
if (ax === (as.length - 1)) { | |
if (remainder > 0) { | |
rowa.unshift(remainder); | |
remainder = 0; | |
} | |
} | |
} | |
rows.push(rowa); | |
} | |
const sortedRows = rows.sort(function(a, b) { | |
return b.length - a.length; | |
}); | |
const maxCol = sortedRows[0].length; | |
remainder = 0; | |
const sum = []; | |
for (let col = (maxCol - 1); col >= 0; col--) { | |
let tmp = 0; | |
for (let row = 0; row < sortedRows.length; row++) { | |
const rowForVal = sortedRows[row]; | |
const rowLen = rowForVal.length; | |
for (let t = rowLen; t < maxCol; t++) { | |
rowForVal.unshift(0); | |
} | |
tmp += rowForVal[col]; | |
} | |
tmp += remainder; | |
const tmps = tmp.toString().split(''); | |
const tmpsl = tmps.length; | |
sum.unshift(tmps.pop()); | |
if (tmpsl > 1) { | |
remainder = parseInt(tmps.join('')); | |
} else { | |
remainder = 0; | |
} | |
} | |
if (remainder > 0) { | |
sum.unshift(remainder.toString()); | |
} | |
return sum.map(n => parseInt(n)); | |
} | |
const a = process.argv[2]; | |
const b = process.argv[3]; | |
console.log(mult(a.split(''), b.split('')).map(n => n.toString()).join('')); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Usage: python multiply.py <integer a> <integer b> | |
""" | |
import sys | |
a = sys.argv[1] | |
b = sys.argv[2] | |
def mult(a, b): | |
a_arr = list(str(a)) | |
b_arr = list(str(b)) | |
a_f = a_arr.pop(0) if a_arr[0] == "-" else None | |
b_f = b_arr.pop(0) if b_arr[0] == "-" else None | |
f = "-" if (a_f == "-") ^ (b_f == "-") else "" | |
a_s = "".join(a_arr[::-1]) | |
b_s = "".join(b_arr[::-1]) | |
rowa = [] | |
remainder = 0 | |
rows = [] | |
for bx in range(len(b_arr)): | |
bval = int(b_s[bx]) | |
rowa = [0] * bx if bx > 0 else [] | |
for ax in range(len(a_arr)): | |
aval = int(a_s[ax]) | |
c = bval * aval | |
cs = str(c) | |
cl = len(cs) | |
if cl == 2: | |
save = int(cs[1]) | |
rowa.insert(0, save+remainder) | |
remainder = int(cs[0]) | |
elif cl == 1: | |
save = int(cs[0]) | |
rowa.insert(0, save+remainder) | |
remainder = 0 | |
if ax == (len(a_arr)-1): | |
if remainder > 0: | |
rowa.insert(0, remainder) | |
remainder = 0 | |
rows.append(rowa) | |
sorted_rows = sorted(rows, key=lambda i: len(i), reverse=True) | |
max_col = len(sorted_rows[0]) | |
remainder = 0 | |
sum = [] | |
for col in range(max_col-1, -1, -1): | |
tmp = 0 | |
for row in range(len(sorted_rows)): | |
row_for_val = sorted_rows[row] | |
row_len = len(row_for_val) | |
for t in range(row_len, max_col): | |
row_for_val.insert(0, 0) | |
tmp += row_for_val[col] | |
tmp += remainder | |
tmps = list(str(tmp)) | |
tmpsl = len(tmps) | |
sum.insert(0, tmps.pop()) | |
remainder = int("".join(tmps)) if tmpsl > 1 else 0 | |
if remainder > 0: | |
sum.insert(0, str(remainder)) | |
return f+"".join(sum) | |
print(mult(a, b)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This Python function is a port of my original JavaScript implementation. Here's an example of performance multiplying two 2428 digit integers. Node.JS is the clear winner.
versus