由于 JS
最大整数为 2 ^ 53 - 1
,最大长度也就是 16
位,当进行一些高精度计算时,容易造成精度丢失的问题。平常对于一些大数值的数据,一般都用 String
类型存储。而使用 String
类型,当进行四则运算时,就需要进行特殊处理,本篇就来实现一下两个大数的相乘。
两个整数的大数相乘,这是一道经典的算法题了,参考力扣 43. 字符串相乘。而这里需要考虑小数的场景,思路其实很简单,就是先记录两个数字的小数位数,然后当作整数字符串去做乘法运算,最后再将小数点复原。
第一步,记录小数位数。比如,对于一串数字 123456.789
,需要得到小数的位数(bit
)-> 3
和移除小数点后的结果 (integer
)-> 123456789
。
/**
* 解析字符串
* @param {string} numStr
* @returns
*/
function parse(numStr) {
let bit
let integer
const potIdx = numStr.indexOf(".")
if (potIdx > -1) {
// 去除末尾无效的 0
numStr = numStr.replace(/0+$/g, "")
// 记录小数位数
bit = numStr.length - potIdx - 1
// 移除首位 0、小数点以及后面跟随的 0
integer = numStr.replace(/^0\.0*|\./, "")
} else {
bit = 0
integer = numStr
}
return { bit, integer }
}
测试一下:
parse("1.000800") // { bit: 4, integer: '10008' }
parse("100.0008") // { bit: 4, integer: '1000008' }
可以看到,bit
和 integer
都不包含末尾的无效 0
。
第二步,将两个整数字符串相乘,借鉴了力扣的官方题解 43. 字符串相乘 - 方法二:做乘法。
/**
* 整型字符串相乘
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function multiply(num1, num2) {
if (num1 === "0" || num2 == "0") {
return "0"
}
const n1 = num1.length
const n2 = num2.length
const res = new Array(n1 + n2).fill(0)
for (let i = n1 - 1; i >= 0; i--) {
for (let j = n2 - 1; j >= 0; j--) {
const k = Number(num1[i]) * Number(num2[j])
let m = i + j + 1
res[m] += k
while (res[m] >= 10) {
res[m - 1] += Math.floor(res[m] / 10)
res[m] = res[m] % 10
m--
}
}
}
// 移除前导 0
while (res[0] === 0) {
res.shift()
}
return res.join("")
}
第三步,将解析后的结果相乘。
/**
* 字符串相乘
* @param {string} num1
* @param {string} num2
* @returns {string}
*/
function calculate(num1, num2) {
const { bit: bit1, integer: integer1 } = parse(num1)
const { bit: bit2, integer: integer2 } = parse(num2)
// 得到两个整型字符串相乘的结果
const res = multiply(integer1, integer2)
// 需要复原的小数总位数
const bit = bit1 + bit2
// 如果小数位数小于结果的长度,说明实际结果大于 0,
// 直接在结果字符串的倒数第 bit 位插入小数点(这里用了正则去实现)
if (bit < res.length) {
return res.replace(new RegExp(`\\d{${bit}}$`), ".$&")
} else {
// 如果小数位数大于等于结果的长度,说明实际结果小于 1,
// 除了结果要以 "0." 开头外,还需要额外在小数点后补 0
return `0.${"0".repeat(bit - res.length)}${res}`
}
}
测试一下:
calculate("1", "0.8") // 0.8
calculate("100", "0.8") // 80.0
calculate("1312.123", "12312.12300") // 16155019.767129
calculate("0.001312", "12312.0012300") // 16.15334561376
calculate("0.0000000001312", "12312.12300") // 0.0000016153505376
完美!最后汇总到一个方法里,整体代码如下:
/**
* 字符串相乘
* @param {string} num1
* @param {string} num2
* @returns {string}
*/
function stringMultiple(num1, num2) {
const { bit: bit1, integer: integer1 } = parse(num1)
const { bit: bit2, integer: integer2 } = parse(num2)
const res = multiply(integer1, integer2)
const bit = bit1 + bit2
if (bit < res.length) {
return res.replace(new RegExp(`\\d{${bit}}$`), ".$&")
} else {
return `0.${"0".repeat(bit - res.length)}${res}`
}
/**
* 解析字符串
* @param {string} numStr
* @returns
*/
function parse(numStr) {
let bit
let integer
const potIdx = numStr.indexOf(".")
if (potIdx > -1) {
// 去除末尾无效的 0
numStr = numStr.replace(/0+$/g, "")
// 记录小数位数
bit = numStr.length - potIdx - 1
// 移除首位 0、小数点以及后面跟随的 0
integer = numStr.replace(/^0\.0*|\./, "")
} else {
bit = 0
integer = numStr
}
return { bit, integer }
}
/**
* 整型字符串相乘
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function multiply(num1, num2) {
if (num1 === "0" || num2 == "0") {
return "0"
}
const n1 = num1.length
const n2 = num2.length
const res = new Array(n1 + n2).fill(0)
for (let i = n1 - 1; i >= 0; i--) {
for (let j = n2 - 1; j >= 0; j--) {
const k = Number(num1[i]) * Number(num2[j])
let m = i + j + 1
res[m] += k
while (res[m] >= 10) {
res[m - 1] += Math.floor(res[m] / 10)
res[m] = res[m] % 10
m--
}
}
}
// 移除前导 0
while (res[0] === 0) {
res.shift()
}
return res.join("")
}
}