Created
March 15, 2023 15:56
-
-
Save zzzz465/764f1879a262a2e97f20ba9d21226689 to your computer and use it in GitHub Desktop.
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
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