Skip to content

Instantly share code, notes, and snippets.

@zzzz465
Created March 15, 2023 15:56
Show Gist options
  • Save zzzz465/764f1879a262a2e97f20ba9d21226689 to your computer and use it in GitHub Desktop.
Save zzzz465/764f1879a262a2e97f20ba9d21226689 to your computer and use it in GitHub Desktop.
function mul(vec0: number[], vec1: number[]): number[] {
if (vec0.length < vec1.length) {
const temp = vec0
vec0 = vec1
vec1 = temp
}
const results: number[][] = []
// numbers0.length >= numbers1
for (let i = 0; i < vec1.length; i++) {
results.push(mul_single(vec0, vec1[i], i))
}
return results.reduce((vec0, vec1) => _merge(vec0, vec1), [0])
}
// return new multiplied vector without modifing original
function mul_single(vec: number[], multiplier: number, exponent: number): number[] {
vec = [...vec]
for (let i = 0; i < vec.length; i++) {
vec[i] = vec[i] * multiplier
}
return new Array(exponent).map(() => 0).concat(vec)
}
// in-place merge vec1 into vec0, return vec0
function _merge(vec0: number[], vec1: number[]): number[] {
if (vec0.length < vec1.length) {
const temp = vec0
vec0 = vec1
vec1 = temp
}
// vec0.length >= vec1.length
for (let i = 0; i < vec1.length; i++) {
vec0[i] = vec0[i] + vec1[i]
}
_normalize(vec0)
return vec0
}
// in-place normalize vector
function _normalize(vec: number[]) {
for (let i = 0; i < vec.length; i++) {
if (vec[i] < 10) {
continue
}
if (i + 1 == vec.length) {
vec.push(0)
}
const value = vec[i]
vec[i] = vec[i] % 10
vec[i + 1] = Math.floor(value / 10)
}
}
function _int_to_vec(value: number): number[] {
const vec = []
while (value > 0) {
vec.push(Math.floor(value / 10))
value = Math.floor(value / 10)
}
return vec
}
function parse_input(input: string): [number[], number[]] {
const splitted = input.split(' ')
const vec0 = [...splitted[0]].map((v) => Number.parseInt(v))
const vec1 = [...splitted[1]].map((v) => Number.parseInt(v))
return [vec0, vec1]
}
const input = '893724358493284 238947328947329'
const [vec0, vec1] = parse_input(input)
const result = mul(vec0, vec1)
console.log(result.reverse().map(v => v.toString()).join(''))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment