基于字符串的数值之加减乘除JS算法研究

在我们的日常js项目中,我们不免会碰到需要进行前端计算的场景。而大家都知道,计算机进行计算时存在精度问题,且数值有值域,偶尔会碰到溢出问题。在最近的一个项目中,由于遇到了一个超过20位的数,因此,又不得不再来对js中数值的运算进行研究。

在js中,一旦遇到非常大的数,例如一个超过Number.MAX_SAFE_VALUE的值,在运算时就会出现问题,而且在展示时(toString)会出现把大数指数化后展示(12.3221124e18),最后导致展示问题。针对这些问题,我们目前已知ES标准已经将BigInt类型作为下一阶段标准的一个方案,基于BigInt,未来实现BigFloat也是可行的。但对于开发者而言,在不可知的未来,BigInt也可能遇到问题,例如,不可以和普通Number进行直接的混合运算。因此,在这些年的经验中,前端总结出来一套方案,就是以字符串的形式进行数值运算。

  • 解决数值溢出问题
  • 解决小数精度问题

字符串数值运算听上去很简单,但是,实际上在实现过程中,会遇到不少问题,一旦你开始去写代码,就会遇到这些坑。由于我自己实现了一套加减乘除算法,所以,现在把这个过程写下来,以为后来的同学借鉴。

竖式

在实现字符串数值的运算时,我们不能按照计算机语言的思维方式去做,我们要回归到数学的本质,什么是加?什么是减?什么是乘?什么是除?数学的奇妙,让我们即使笨拙,也可以找到门路。我所发现的实现方式,就是我们小学的时候学到的“竖式”。它是一种能让小学生理解的运算方式。让我们来看一个最简单的竖式:

   132
 +  79
------
    `1
   `1
   2
------
 = 211

这是一个加法竖式的例子。而且两个竖式可以串联,例如,上面的竖式结束之后,你需要继续计算211+64,还可以继续在下面进行下一轮运算。

基于竖立的理解,我实现了一套js的演算。其中加法和减法是完完全全按照竖式实现的,而乘法和除法则是在加法和减法基础上的继续叠加实现的。下面,我就会对每一个实现进行详细的讲解。

数的拆解

在真正开始进行算法讲解之前,我需要做一件事,就是讲清楚,我在每一个算法中,如何对待一个数值。因为我们用于运算的所有数值在js中的本质是一个字符串,因此,我们需要对数进行拆解,我们需要对算法进行叠加,对数的每一部分进行分析,然后综合得到最后的结果。

一个数,在表达中分为三个部分:整数部分,小数部分,正负。

对于字符串而言,这三部分都非常容易得到,不需要太多的处理和识别。

在算法中,我基本上遵循这样的规律:

  • 整数部分和小数部分分开运算,最后叠加起来
  • 创建一个完全正整数的元运算算法
  • 正负号影响处理方式,但不对运算本身造成影响,因此,一般在运算开始之前考虑正负号带来的影响
  • 某些特殊值具有快速响应能力,例如一个数乘以0,永远得到0,诸如此类的运算,都可以不用走复杂的运算流程,以此增加性能

对于字符串处理结果而言,我们还需要注意一个事实,就是,字符串不会自动处理数值前后的00,例如我们用两个数相减,得到-007.1200,我们应该在代码中自动把开头的00和末尾的00都去掉,以一个正确正常的值返回运算结果。

加法运算

两个数相加的竖式已经在上面的例子中提到了。我们现在来再研究一下。两个数相加,无论多少位,它的规则都是从末位开始,依次按位相加,最后将相加结果串联起来。但是,在这个过程中需要注意的是,当两个单位相加结果大于10时,需要向前进一位,也就是在下一位相加时,需要再加1.这个进位的规则使得整个运算难了很多。但是,我们还是可以通过各种手段,判断出在计算时是否应该进位。

加法元

所谓元运算,在本文中是指,对两个正整数进行的某项运算算法。加法的元运算相对比较简单,主要考虑的是进位规则:

// 创建一个整数相加函数
const plus = (x, y) => {
	let xr = x.split('').reverse()
	let yr = y.split('').reverse()
	let len = Math.max(xr.length, yr.length)
	let items = []
	for (let i = 0; i < len; i ++) {
		let xv = xr[i] || '0'
		let yv = yr[i] || '0'
		items[i] = ((+xv) + (+yv)) + ''
	}

	let sum = items.reduce((sum, item, index) => {
		let sumlen = sum.length
		// 如果之前相加进了一位
		if (sumlen > index) {
			let borrow = sum.substring(0, 1)
			let placed = sum.substring(1)
			let next = (+borrow + +item) + ''
			return next + placed
		}
		else {
			return item + sum
		}
	}, '')
	return sum
}

上边这个函数解决的是两个正整数相加的元运算。无论这两个正整数位数有多大,都能正常计算结果。

加法变形

本文中所谓运算变形,是指一些场景下,在元运算基础上进行的叠加处理。加法的运算变形包括:

  1. a, b任何一个值为0,则返回另外一个值,无需进行深入运算
  2. 如果a为正数,b为负数,相当于a-b,直接调用minusby(a, b.substring(1))
  3. 如果a为负数,b为正数,则反过来调用minusby(b, a.substring(1))
  4. 小数相加时,先补齐小数位数,再去掉小数点,元运算之后,再把小数点加回来
  5. a, b都是负数,相当于plusby(a.substring(1), b.substring(1))后,结果再取负

以上就是加法的运算变形。

基于这些变形,我们得到最终的加法运算如下:

/**
 * 基于字符串数值的a+b
 * @param {string} a
 * @param {string} b
 */
export function plusby(a, b) {
	a = numerify(a)
	b = numerify(b)

	if (a === '0') {
		return b
	}
	else if (b === '0') {
		return a
	}

	var [ ia, da = '0' ] = a.split('.')
	var [ ib, db = '0' ] = b.split('.')

	// 是否为负数
	var na = false
	var nb = false
	if (ia.indexOf('-') === 0) {
		ia = ia.substring(1)
		na = true
	}
	if (ib.indexOf('-') === 0) {
		ib = ib.substring(1)
		nb = true
	}

	// 一正一负相当于相减
	if (na && !nb) {
		return minusby(b, a.substring(1))
	}
	if (nb && !na) {
		return minusby(a, b.substring(1))
	}

	// 创建一个整数相加函数
	const plus = (x, y) => {
		let xr = x.split('').reverse()
		let yr = y.split('').reverse()
		let len = Math.max(xr.length, yr.length)
		let items = []
		for (let i = 0; i < len; i ++) {
			let xv = xr[i] || '0'
			let yv = yr[i] || '0'
			items[i] = ((+xv) + (+yv)) + ''
		}

		let sum = items.reduce((sum, item, index) => {
			let sumlen = sum.length
			// 如果之前相加进了一位
			if (sumlen > index) {
				let borrow = sum.substring(0, 1)
				let placed = sum.substring(1)
				let next = (+borrow + +item) + ''
				return next + placed
			}
			else {
				return item + sum
			}
		}, '')
		return sum
	}

	// 补齐位数用以相加
	const dalen = da.length
	const dblen = db.length
	const dlen = Math.max(dalen, dblen)
	if (dalen < dlen) {
		da = padRight(da, dlen, '0')
	}
	if (dblen < dlen) {
		db = padRight(db, dlen, '0')
	}

	const ta = ia + da
	const tb = ib + db

	var sum = plus(ta, tb)

	// 还原小数位数
	var sumr = sum.split('')
	var sumlen = sumr.length
	var index = sumlen - dlen
	sumr.splice(index, 0, '.')
	sum = sumr.join('')

	sum = clearNumberZero(sum)
	sum = sum === '' ? '0' : sum

	// 都是负数
	if (sum !== '0' && na && nb) {
		sum = '-' + sum
	}

	return sum
}

上面代码中有几个函数,他们的源码如下:

/**
 * 对字符串向右补位
 * @param {*} str
 * @param {*} len
 * @param {*} pad
 */
export function padRight(str, len, pad) {
	if (str.length >= len) {
		return str
	}

	let diff = len - str.length
	let letters = createArray(pad, diff)

	return str + letters.join('')
}
/**
 * 移除数字首尾的00
 * @param {*} input
 */
export function clearNumberZero(input) {
	input = input.toString()
	var [ integerPart, decimalPart = '' ] = input.split('.')
	var isNegative = false
	if (integerPart.indexOf('-') === 0) {
		isNegative = true
		integerPart = integerPart.substring(1)
	}
	integerPart = integerPart.replace(/^0+/, '') // 去除开头的000
	decimalPart = decimalPart.replace(/0+$/, '') // 去除末尾的000
	var value = (isNegative && (integerPart || decimalPart) ? '-' : '') + (integerPart ? integerPart : '0') + (decimalPart ? '.' + decimalPart : '')
	return value
}
/**
 * 创建一个特定位数,且每个元素值相同的数组
 * @param {*} count
 * @param {*} value
 */
export function createArray(value, count = 1) {
	return [].fill.call(new Array(count), value);
}
/**
 * 获取数字的字符串形式
 * @param {*} num
 */
export function numerify(num) {
	if (isString(num)) {
		if (!isNumeric(num)) {
			return ''
		}
		let value = clearNumberZero(num)
		return value
	}
	else if (isNumber(num)) {
		let value = num.toString()
		// num.toString()之后得到的指数有两种,一种是精确的小值指数形式,另一种是非精确的大值指数形式
		// 但无论哪一种,这里都是最终的办法,非精确的情况下,无法做到数值转化
		if (value.indexOf('e')) {
			return convertNumberWithExponential(value)
		}
		else {
			return value
		}
	}
	else {
		return ''
	}
}
/**
 * 判断是否为数字的字符串形式,支持小数点和负数
 * @param {*} value
 */
export function isNumeric(value) {
	return isString(value) && /^\-{0,1}[0-9]+(\.{0,1}[0-9]+){0,1}$/.test(value)
}
export function isNumber(value) {
	return typeof value === 'number' && !isNaN(value)
}
/**
 * 将一个指数型数字转化为普通数字
 * @param {number|string} input 指数型数字,可以是一个同等合法的字符串
 * @return {string} 转化后的普通数字字符串,因为大值会被自动转化为指数型数字,因此,这里必须返回字符串
 * @example
 * convertNumberWithExponential(1.2e3) => '1200'
 */
export function convertNumberWithExponential(input) {
	let num = parseFloat(input);
	if (isNaN(num)) {
		return '';
	}

	if (!input && input !== 0) {
		return '';
	}

	let str = input.toString();

	// 如果输入中根本不存在e
	// 当input为12.3e13的时候,str会直接由于.toString成为正常字符串
	if (str.indexOf('e') === -1) {
		return str;
	}

	// 假设input为一个合法的指数型数字或数字字符串,不考虑非法输入的情况
	let [base, exp] = str.split('e');
	let count = Number.parseInt(exp, 10);
	if (count >= 0) {
		let arr = base.split('');
		for (let i = 0; i < count; i ++) {
			let index = arr.indexOf('.');
			let next = index === arr.length - 1 ? '0' : arr[index + 1];
			arr[index] = next;
			arr[index + 1] = '.';
		}
		if (arr[arr.length - 1] === '.') {
			arr.pop();
		}
		let result = arr.join('');
		return result;
	}
	else {
		// 通过反转数字,把小数点往后移,最后反转过来的方法实现负数指数转化
		let arr = base.split('');
		let rarr = arr.reverse();
		for (let i = count; i < 0; i ++) {
			let index = rarr.indexOf('.');
			let next = index === rarr.length - 1 ? '0' : rarr[index + 1];
			rarr[index] = next;
			rarr[index + 1] = '.';
		}
		let rrarr = rarr.reverse();
		if (rrarr[0] === '.') {
			rrarr.unshift('0');
		}
		let result = rrarr.join('');
		return result;
	}
}

minusby则在下文中实现。

减法运算

减法运算比加法运算复杂那么一点点,在于加法运算,如果两个数正负相同,那么结果一定是对应的正负,而减法运算不同,当两个正数相减,减数比被减数更大时,得到的结果就是负数。除了这点之外,其他大部分规则和加法非常相似,我们在创建算法时,可以按照加法运算的思维去实现。

减法元

和加法元一样,元减法主要考虑到的也是借位问题,从个位开始减,当前位不够减时,向前借1使自己加10后再减,借1之后,下一位运算时需要多减1:

const minus = (x, y) => {
	let xr = x.split('').reverse()
	let yr = y.split('').reverse()
	let len = Math.max(xr.length, yr.length)
	let items = []
	for (let i = 0; i < len; i ++) {
		let xv = xr[i] || '0'
		let yv = yr[i] || '0'
		items[i] = {
			xv,
			yv,
		}
	}

	let isBorrowed = false
	let diff = items.reduce((diff, item, index) => {
		let { xv, yv } = item

		xv = +xv
		yv = +yv

		// 如果被借位,则一开始自己就要减1
		if (isBorrowed) {
			xv --
		}

		// 向前借位
		if (xv < yv) {
			isBorrowed = true
			xv += 10
		}
		else {
			isBorrowed = false
		}

		let v = xv - yv
		diff = v + diff

		return diff
	}, '')

	return diff
}

在代码中,我们增加了一个isBorrowed来记录是否向前一位借了1,如果isBorrowed是true,那么在下一个循环之前,先从x对应位上减掉1.

减法变形

在减法的算法中,比加法稍微复杂了一点点。

  1. b为0时,直接返回a
  2. a为0时,返回b的相反数
  3. a=b时,返回0
  4. 如果a为正数,b为负数,相当于a+(-b),直接调用plusby(a, b.substring(1))
  5. 如果a为负数,b为正数,相当于a+(-b),调用plusby(a, '-' + b)
  6. 小数相加时,先补齐小数位数,再去掉小数点,元运算之后,再把小数点加回来,和加法一样
/**
 * 基于字符串形式数值的a-b
 * @param {string} a
 * @param {string} b
 */
export function minusby(a, b) {
	a = numerify(a)
	b = numerify(b)

	if (b === '0') {
		return a
	}
	else if (a === '0') {
		if (b.indexOf('-') === 0) {
			return b.substring(1)
		}
		else {
			return '-' + b
		}
	}
	else if (a === b) {
		return '0'
	}

	var [ ia, da = '0' ] = a.split('.')
	var [ ib, db = '0' ] = b.split('.')

	// 是否为负数
	var na = false
	var nb = false
	if (ia.indexOf('-') === 0) {
		ia = ia.substring(1)
		na = true
	}
	if (ib.indexOf('-') === 0) {
		ib = ib.substring(1)
		nb = true
	}

	// 一正一负相当于相加
	if (na && !nb) {
		return plusby(a, '-' + b)
	}
	if (nb && !na) {
		return plusby(a, b.substring(1))
	}

	// 当b大于a的时候,先反过来计算,然后再取反
	if (compare(b, a) > 0) {
		let diff = minusby(b, a)
		return '-' + diff
	}

	const minus = (x, y) => {
		let xr = x.split('').reverse()
		let yr = y.split('').reverse()
		let len = Math.max(xr.length, yr.length)
		let items = []
		for (let i = 0; i < len; i ++) {
			let xv = xr[i] || '0'
			let yv = yr[i] || '0'
			items[i] = {
				xv,
				yv,
			}
		}

		let isBorrowed = false
		let diff = items.reduce((diff, item, index) => {
			let { xv, yv } = item

			xv = +xv
			yv = +yv

			// 如果被借位,则一开始自己就要减1
			if (isBorrowed) {
				xv --
			}

			// 向前借位
			if (xv < yv) {
				isBorrowed = true
				xv += 10
			}
			else {
				isBorrowed = false
			}

			let v = xv - yv
			diff = v + diff

			return diff
		}, '')

		return diff
	}

	// 补齐位数用以相减
	const dalen = da.length
	const dblen = db.length
	const dlen = Math.max(dalen, dblen)
	if (dalen < dlen) {
		da = padRight(da, dlen, '0')
	}
	if (dblen < dlen) {
		db = padRight(db, dlen, '0')
	}

	const ta = ia + da
	const tb = ib + db

	var diff = minus(ta, tb)

	// 还原小数位数
	var diffr = diff.split('')
	var difflen = diffr.length
	var index = difflen - dlen
	diffr.splice(index, 0, '.')
	diff = diffr.join('')

	diff = clearNumberZero(diff)
	diff = diff === '' ? '0' : diff

	return diff
}

乘法运算

乘法运算则比加减运算复杂很多,无法通过单纯的位加减来实现。那么乘法应该怎么做呢?从原理上,我们可以通过加法叠加来实现,即累加的算法。例如2x3=2+2+2,也就是3个2相加,乘数表示被乘数的相加个数。但是,这样会带来一个问题,如果乘数是一个极大的数,那么代表被乘数会被相加n次,字符串的运算性能本身是会受到限制的,如果一个超过百万次的相加,必然可能遇到页面卡顿问题。那么,有没有什么办法去优化呢?

乘法元

我们在进行乘法的元运算实现时,通过了一个变形的取巧方式去对各个位上的数值进行处理。我们通过下面的式子进行研究:

   128
x   24
-------
    32
    8
   4
-------
+  16
   4
  2
-------
= 3072

如果不考虑进位情况,两个数相乘,其结果基本上就是将每位上的数相乘(根据位进行放置),相乘后,再将各个位相加,相加后组合在一起即可。

上图解析了在竖式中如何去得到一个乘法的运算过程。result1和result2是两个中间变量,分别记录的是乘数个位和十位各自乘以被乘数得到的结果。为了方便记录位置,所以在记录时,数组中存放数字和我们习惯看到的数字的位是相反的,这样,我们可以获得一个比较有趣的规律,那就是当前的计算位的索引是被乘数计算位和乘数计算位的索引之和。举个例子,当乘数的1(计算位索引是1)乘以被乘数的2(计算索引是1),在结果中,它们的结果计算位索引位置应该是1+1=2,即百位。基于这样的规律,我们在运算过程中,可以模拟这种规律,只需要一个result即可,不需要中间的临时变量,每次遍历位相乘时,将结果放到数组中对应的位置,并和已经有的相加即可得到该位置的结果。

/**
 * 大数乘法
 * 思路:逐位相乘,不算进位;最后算进位并拼接字符串
 * @param {number} a 被乘数
 * @param {number} b 乘数
 */
const multiply = (a, b) => {
	const result = []
	const aArr = a.toString().split('').map(t => parseInt(t))
	const bArr = b.toString().split('').map(t => parseInt(t))
	const aLen = aArr.length
	const bLen = bArr.length

	// 逐位相乘,不算进位,与计算方向无关
	for (let bIndex = bLen-1; bIndex >= 0; bIndex--) {
		for (let aIndex = aLen-1; aIndex >= 0; aIndex--) {
			let index = bIndex + aIndex
			if (!result[index]) {
				result[index] = 0
			}
			result[index] += bArr[bIndex] * aArr[aIndex]
		}
	}

	// 因为是从左到右的计算顺序,所以进位要反向
	// (也方便最高位进位时,数组可扩)。
	result.reverse()
	// 最高位可能会进位,所以每次循环重新计算length。
	for (let i = 0; i < result.length; i ++) {
		if (!result[i]) {
			result[i] = 0
		}

		let more = parseInt(result[i] / 10)
		if (more > 0) {
			if (!result[i + 1]) {
				result[i + 1] = 0
			}
			result[i + 1] += more
		}
		result[i] = result[i] % 10
	}
	result.reverse()

	return result.join('')
}

上面代码中有一个for...for的嵌套循环,就是实现上述规律的逻辑。在本文的实现中,多次会用到反转数组,这是一个非常重要的步骤,因为我们常识中的数的位,和我们在程序中处理位的时候,是不一样的。我们反转数组之后,个位向百位千位,则和数组游标方向一致了。

乘法变形

乘法变形稍微简单一些,主要包括:

  1. 任何数和0相乘都得0
  2. 任何数和1相乘都得自己本身
  3. 任何数和-1相乘都得自己的相反数
  4. 当一个数乘以10n时,就是将小数点再往右移动n位,小数位数不够时,用0代替
  5. 对待小数部分,一个数相乘,需要将整数和小数分开各自相乘,小数部分结果位数为两个数小数位数的和,然后再将两部分连接起来即可
  6. 乘法的正负数没有复杂变形,正负相乘为负,正正、负负为正。
/**
 * 字符串形式数值a*b
 * @param {string} a
 * @param {string} b
 */
export function multiplyby(a, b) {
	a = numerify(a)
	b = numerify(b)

	// 0值快速返回
	if (a === '0' || b === '0') {
		return '0'
	}
	else if (a === '1') {
		return b
	}
	else if (b === '1') {
		return a
	}
	else if (a === '-1') {
		if (b.indexOf('-') === 0) {
			return b.substring(1)
		}
		else {
			return '-' + b
		}
	}
	else if (b === '-1') {
		if (a.indexOf('-') === 0) {
			return a.substring(1)
		}
		else {
			return '-' + a
		}
	}
	// 特殊处理那种整除100000的
	else if (/^10+/.test(b)) {
		let wei = Math.log10(b)
		let value = numerify(a)
		let [ integerPart, decimalPart = '' ] = value.split('.')
		let decimalLen = decimalPart.length
		// 移动小数点位置
		if (decimalLen <= wei) {
			value = integerPart + padRight(decimalPart, wei, '0')
		}
		else {
			value = integerPart + decimalPart.substring(0, wei) + '.' + decimalPart.substring(wei)
		}
		value = clearNumberZero(value)
		return value
	}

	/**
	 * 大数乘法
	 * 思路:逐位相乘,不算进位;最后算进位并拼接字符串
	 * @param {number} a 被乘数
	 * @param {number} b 乘数
	 */
	const multiply = (a, b) => {
		const result = []
		const aArr = a.toString().split('').map(t => parseInt(t))
		const bArr = b.toString().split('').map(t => parseInt(t))
		const aLen = aArr.length
		const bLen = bArr.length

		// 逐位相乘,不算进位,与计算方向无关
		for (let bIndex = bLen-1; bIndex >= 0; bIndex--) {
			for (let aIndex = aLen-1; aIndex >= 0; aIndex--) {
				let index = bIndex + aIndex
				if (!result[index]) {
					result[index] = 0
				}
				result[index] += bArr[bIndex] * aArr[aIndex]
			}
		}

		// 因为是从左到右的计算顺序,所以进位要反向
		// (也方便最高位进位时,数组可扩)。
		result.reverse()
		// 最高位可能会进位,所以每次循环重新计算length。
		for (let i = 0; i < result.length; i ++) {
			if (!result[i]) {
				result[i] = 0
			}

			let more = parseInt(result[i] / 10)
			if (more > 0) {
				if (!result[i + 1]) {
					result[i + 1] = 0
				}
				result[i + 1] += more
			}
			result[i] = result[i] % 10
		}
		result.reverse()

		return result.join('')
	}

	var [ ia, da = '0' ] = a.split('.')
	var [ ib, db = '0' ] = b.split('.')

	// 是否为负数
	var na = false
	var nb = false
	if (ia.indexOf('-') === 0) {
		ia = ia.substring(1)
		na = true
	}
	if (ib.indexOf('-') === 0) {
		ib = ib.substring(1)
		nb = true
	}

	// 负负为正
	var isNegative = false
	if ((na && !nb) || (!na && nb)) {
		isNegative = true
	}

	var iProd = multiply(ia, ib)
	var dProd = multiply(da, db)

	dProd = padLeft(dProd, da.length + db.length, '0') // 补全小数位数

	var value = iProd + '.' + dProd
	value = clearNumberZero(value)
	value = (isNegative ? '-' : '') + value
	value = value === '' ? '0' : value

	return value
}
/**
 * 对字符串向左补位
 * @param {*} str 原始字符串
 * @param {*} len 要求字符串应该为多长
 * @param {*} pad 被用来补位的字符,注意,仅支持一个字符
 */
export function padLeft(str, len, pad) {
	if (str.length >= len) {
		return str
	}

	let diff = len - str.length
	let letters = createArray(pad, diff)

	return letters.join('') + str
}

除法运算

除法是四种运算中最为复杂的,因为它不能像减法作为加法反运算一样,作为乘法的反运算。一开始的时候,我对除法毫无办法,因为我们的除法竖式是这样:

       13
   --------
12 )  156
      12
     -----
       36
       36
      ----
        0

这样的竖式和前面三种算法完全不同,因为在除法中存在另外一个值,叫“余数”。每一次相除,都会得到一个余数,除尽时余数为0,除不尽时,永远都会有余数。那么这么复杂的运算,怎么用代码去实现呢?

除法元

经过一番思考之后,我想到一个问题,除法的本质是什么?一个数除以一个数,实际上是想知道,被除数里面包含了多少个除数?这一下子就开朗了,因为乘法我们也可以看做一个数有多少个累加。除法的本质就是累减,只不过存在余数。

除法的运算比前面任何一个都复杂。因为除法是一个可以无限循环下去的,没有底的。但我们在考虑两个正整数相除时,不必除尽,相反,我们要保留余数。

// 两个正整数相除
const divide = (x, y) => {
	const uselen = y.length
	const result = []

	// 取出一组
	var waitforcompare = x.substr(0, uselen)
	var waittouse = x.substring(uselen)

	var stillhave = waitforcompare // 减去y之后剩下的值
	var inrange = 0

	do {
		let c
		while (c = compareby(stillhave, y) >= 0) {
			if (c > 0) {
				inrange ++
				stillhave = minusby(stillhave, y) // 减去1次
			}
			else if (c === 0) {
				inrange ++
				stillhave = ''
				break
			}
		}

		let stillhavelen = stillhave.length
		// 从x的头部取出需要的部分组成新的waitforcompare
		let nextlen = uselen - stillhavelen
		nextlen = nextlen > 0 ? nextlen : 1
		waitforcompare = stillhave + waittouse.substr(0, nextlen)
		waittouse = waittouse.substring(nextlen)

		result.push(inrange)
		stillhave = waitforcompare // 当stillhave=''时,会跳出循环
		inrange = 0
	} while (compareby(stillhave, y) >= 0)

	var remainder = stillhave || '0'
	var quotient = result.join('')

	remainder = clearNumberZero(remainder)
	quotient = clearNumberZero(quotient)

	return { remainder, quotient }
}

上面的算法,首先将被除数切割,取出和除数位数相同的值,然后使用了两个循环,主循环do...while是对原始值进行对比、重置和记录累减数,里面的while子循环用以计算累减的次数。最终得到了商和余数。

除法变形

除法非常复杂,因为有余数这个元素的存在,让后续的操作还要继续。当余数存在的时候,我们要在余数后面增加辅助位,用以计算一个新的商和余数,而这个商,会变成小数部分的值。而被除数本身就有小数存在的可能,因此,在带有小数除数的情况下,我们不用对除数也进行小数的拆分,而是将除数和被除数统一先乘以一定的10n,使除数为一个整数,被除数有小数作为余数的部分,等到除不尽时,通过移动小数点位置,获得商的小数部分。

对于除法的变形,主要包括:

  1. 除数不能为0
  2. 0除以任何不为0的数都为0
  3. 任何数除以1都为本身
  4. 任何数除以-1都为自己的相反数
  5. 当一个数除以10n时,就是将小数点再往左移动n位,小数位数不够时,用0代替
  6. 正负相除为负,正正、负负为正
/**
 * 字符串形式数值a/b
 * @param {*} a
 * @param {*} b
 * @param {*} decimal 小数位数,当除不尽时,保留多少位小数,默认15位
 */
export function divideby(a, b, decimal) {
	if (isUndefined(decimal)) {
		decimal = divideby.InfiniteDecimalLength
	}

	a = numerify(a)
	b = numerify(b)

	// 除数不能为0
	if (b === '0') {
		throw new Error('除数不能为0')
	}

	if (a === '0') {
		return '0'
	}
	else if (b === '1') {
		return a
	}
	else if (a === b) {
		return '1'
	}
	// 特殊处理那种整除100000的
	else if (/^10+/.test(b)) {
		let wei = Math.log10(b)
		let value = numerify(a)
		let [ integerPart, decimalPart = '' ] = value.split('.')
		let integerLen = integerPart.length
		// 移动小数点位置
		if (integerLen <= wei) {
			value = '0.' + padLeft(integerPart, wei, '0') + decimalPart
		}
		else {
			let pos = integerLen - wei
			let left = integerPart.substring(0, pos)
			let right = integerPart.substring(pos)
			value = left + '.' + right + decimalPart
		}
		value = clearNumberZero(value)
		return value
	}

	var [ ib, db = '' ] = b.split('.')

	// 除数被除数都同时扩大,使除数成为整数
	if (db.length) {
		let len = db.length
		let pow = Math.pow(10, len)
		a = multiplyby(a, pow)
		b = multiplyby(b, pow)
	}

	var [ ia, da = '' ] = a.split('.')

	// 是否为负数
	var na = false
	var nb = false
	if (ia.indexOf('-') === 0) {
		ia = ia.substring(1)
		na = true
	}
	if (b.indexOf('-') === 0) {
		b = b.substring(1)
		nb = true
	}

	// 两个正整数相除
	const divide = (x, y) => {
		const uselen = y.length
		const result = []

		// 取出一组
		var waitforcompare = x.substr(0, uselen)
		var waittouse = x.substring(uselen)

		var stillhave = waitforcompare // 减去y之后剩下的值
		var inrange = 0

		do {
			let c
			while (c = compareby(stillhave, y) >= 0) {
				if (c > 0) {
					inrange ++
					stillhave = minusby(stillhave, y) // 减去1次
				}
				else if (c === 0) {
					inrange ++
					stillhave = ''
					break
				}
			}

			let stillhavelen = stillhave.length
			// 从x的头部取出需要的部分组成新的waitforcompare
			let nextlen = uselen - stillhavelen
			nextlen = nextlen > 0 ? nextlen : 1
			waitforcompare = stillhave + waittouse.substr(0, nextlen)
			waittouse = waittouse.substring(nextlen)

			result.push(inrange)
			stillhave = waitforcompare // 当stillhave=''时,会跳出循环
			inrange = 0
		} while (compareby(stillhave, y) >= 0)

		var remainder = stillhave || '0'
		var quotient = result.join('')

		remainder = clearNumberZero(remainder)
		quotient = clearNumberZero(quotient)

		return { remainder, quotient }
	}

	var dvi = divide(ia, b) // 整数部分得到的结果
	var { remainder, quotient } = dvi
	var value = quotient

	if (da) {
		remainder = remainder === '0' ? da : remainder + da // 连接小数部分,准备计算小数部分的商
	}
	else {
		remainder = remainder + '0'
	}

	if (remainder && remainder !== '0') {
		var result = ''
		var nextto = remainder
		// console.log(value, nextto, b, /[1-9]/.test(nextto), divide(nextto, b))
		while (/[1-9]/.test(nextto)) {
			let dvd = divide(nextto, b)
			let { remainder, quotient } = dvd
			result += quotient

			if (remainder === '0') {
				break
			}

			nextto = remainder + '0'

			// 当小数位数超出规定的位数时,跳出
			if (result.length > decimal) {
				break
			}
		}
		value = quotient + '.' + result
	}

	value = clearNumberZero(value)

	if ((na && !nb) || (!na && nb)) {
		value = '-' + value
	}

	return value
}
divideby.InfiniteDecimalLength = 15 // 无限小数保留位数

上面的蓝色标记的compareby是一个基于字符串的大值比较函数。

另外,和其他函数不同,divideby函数有第三个参数,用以决定当一个除法除不尽时,最多精确到第几位小数,当运算得到这位小数之后,不会再进行下一轮运算。

大小比较运算

字符串本身是可以比较的,但是由于我们要面临数值的比较,比字符串比较复杂得多。大小比较的总体思路如下:

  1. 正负关系,正数永远大于负数
  2. 字符串长度(整数部分和小数部分分开比较),对于两个正整数而言,长度越长,值越大
  3. 当长度相同的情况下,从首位开始比较,比较每一个位置上的大小即可
  4. 整数部分相等,再比较小数部分,小数部分比较时,需要先补全小数位数为一样的位数,之后再按整数部分方法进行比较。
/**
 * 比较两个数的大小,返回1表示a>b,返回-1表示a<b,返回0表示a=b
 * @param {*} a
 * @param {*} b
 */
export function compare(a, b) {
	a = numerify(a)
	b = numerify(b)

	var [ ia, da = '' ] = a.split('.')
	var [ ib, db = '' ] = b.split('.')

	// n, m 都是正整数
	const compare2 = (n, m) => {
		if (n.length > m.length) {
			return 1
		}
		else if (n.length < m.length) {
			return -1
		}
		else {
			for (let i = 0, len = n.length; i < len; i ++) {
				let nv = n.charAt(i)
				let mv = m.charAt(i)
				if (+nv > +mv) {
					return 1
				}
				else if (+nv < +mv) {
					return -1
				}
			}
			return 0
		}
	}

	// x, y都是整数,但可正可负
	const compare = (x, y) => {
		let nx = x.indexOf('-') === 0
		let ny = y.indexOf('-') === 0

		// x > 0 > y
		if (!nx && ny) {
			return 1
		}
		// y > 0 > x
		else if (nx && !ny) {
			return -1
		}
		// x, y < 0
		else if (nx && ny) {
			x = x.substring(1)
			y = y.substring(1)
			let result = compare2(x, y)
			return -result
		}
		// x, y > 0
		else if (!nx && !ny) {
			return compare2(x, y)
		}
	}

	const ci = compare(ia, ib)
	if (ci) {
		return ci
	}

	// 小数部分长度补全相同长度来比较
	const dalen = da.length
	const dblen = db.length
	const dlen = Math.max(dalen, dblen)
	if (dalen < dlen) {
		da = padRight(da, dlen, '0')
	}
	if (dblen < dlen) {
		db = padRight(db, dlen, '0')
	}
	const cd = compare(da, db)
	if (cd) {
		return cd
	}

	return 0
}

算式运行

既然已经实现了加减乘除四个基本的算法,那么其他的计算都可以通过这四个基本算法进行叠加扩展出来,例如**表达平方,^表达次幂,都可以通过乘法运算得到结果。那么,有没有一个办法,我只传入一个数学算式,然后就把结果返回给我呢?显然,这是可以做到的,我们写一个函数来运行算式表达式:

/**
 * 字符串算式计算,仅支持加减乘除
 * @param {*} exp
 * @example
 * calculate('128+12*24-(132-87)')
 */
export function calculate(exp, decimal) {
  const contains = (str, items) => {
    for (let i = 0, len = items.length; i < len; i ++) {
      let item = items[i]
      if (str.indexOf(item) > -1) {
        return true
      }
    }
    return false
  }

  if (!/^[\(\-]?[0-9]+[0-9\+\-\*\/\(\)]*[0-9\)]$/.test(exp)) {
    throw new Error('算式中包含不允许的内容')
  }
  if (contains(exp, ['--', '++', '**', '//'])) {
    throw new Error('算式中包含重复的运算符')
  }
  if (exp.indexOf(')(') > -1) {
    throw new Error('算式中不允许包含连续括号')
  }
  if (exp.indexOf('()') > -1) {
    throw new Error('算式中不允许包含空括号')
  }
  if (/\)[0-9]/.test(exp)) {
    throw new Error('算式中,括号后面不能直接跟数字')
  }
  if (/[0-9]\(/.test(exp)) {
    throw new Error('算式中,括号不能直接跟在数字后面')
  }

  const parse = (exp) => {
    let inGroup = 0 // 数字代表括号层级,括号里面还能套括号
    let exparr = []
    let expstr = ''
    let groups = []
    let groupstr = ''
    // TODO: 目前仅支持一层括号
    for (let i = 0, len = exp.length; i < len; i ++) {
      let char = exp.charAt(i)
      if (char === '(') {
        // 子括号,在外面的括号内部,只需要将字符串原始连接给该组即可,放到后面处理
        if (inGroup) {
          groupstr += char
        }
        else {
          if (expstr) {
            exparr.push(expstr)
            expstr = ''
          }
        }
        inGroup ++
      }
      else if (char === ')') {
        if (!inGroup) {
          throw new Error('算式不正确,非法反括号,位置:' + groupstr + ')')
        }

        // 顶层括号结束
        if (inGroup === 1) {
          if (groupstr) {
            let index = groups.length
            exparr.push(index)
            groups.push(groupstr)
            groupstr = ''
          }
        }
        else {
          groupstr += char
        }
        inGroup --
      }
      else if (inGroup) {
        groupstr += char
      }
      else {
        if (/[\+\-\*\/]/.test(char)) {
          if (expstr) {
            exparr.push(expstr)
          }
          expstr = ''
          exparr.push(char)
        }
        else {
          expstr += char
        }
      }
    }

    if (inGroup) {
      throw new Error('括号没有正确关闭,请检查算式')
    }

    // 最后一个数
    if (expstr) {
      exparr.push(expstr)
    }

    // console.log(exp, exparr, groups)

    // 解析前面创建的括号组,并将该处用一个数组替换
    const expsrc = []
    exparr.forEach((item, i) => {
      if (isNumber(item)) {
        item = groups[item]
        item = parse(item)
      }
      expsrc.push(item)
    })

    // 最终用于运算的数组
    const expast = []
    for (let i = 0; i < expsrc.length; i ++) {
      let word = expsrc[i]
      if (word === '*' || word === '/') {
        let next = expsrc[i + 1]
        let latest = expast.pop()
        let item = [latest, word, next]

        expast.push(item)
        i ++ // 因为把后面的一个单词也弄进来了,所以下一个循环要往后推一个位置
      }
      else {
        expast.push(word)
      }
    }

    // expres是一个多维数组,到底多少层未知,主要看括号分组情况
    // 这个数组的最顶层是整个算式的解析结果,模式如下:
    // [ '1', '+', '2' ]
    // [ '1', '+', [ '2', '*', '3' ], '+', [ '4', '/', '2' ] ]
    // 内部的数组代表一个小括号,会在运算时先执行
    return expast
  }

  // 运算元,从左往右依次进行计算
  const execute = (expast) => {
    // 先计算出优先级高的部分
    let exparr = []
    expast.forEach((item) => {
      if (isArray(item)) {
        item = execute(item)
      }
      exparr.push(item)
    })

    let result = ''
    for (let i = 0, len = exparr.length; i < len; i ++) {
      let current = exparr[i]
      if (i === 0) {
        result = current === '-' ? '0' : current
      }
      if (/[\+\-\*\/]/.test(current)) {
        let next = exparr[i + 1]
        if (current === '+') {
          result = plusby(result, next)
        }
        else if (current === '-') {
          result = minusby(result, next)
        }
        else if (current === '*') {
          result = multiplyby(result, next)
        }
        else if (current === '/') {
          result = divideby(result, next, decimal)
        }
        i ++ // next被消费掉了,要从下一位开始继续计算
      }
    }
    return result
  }

  const expast = parse(exp)
  const result = execute(expast)
  return result
}

上面的函数可以让我们直接运行算式,得到结果,它支持括号分组。但是,它的限制在于,仅支持加减乘除。

结语

本文主要对数值的加减乘除进行了运算原理的规律摸底,从而建立了一套基于js的数值运算。在我们对一个日常习以为常的真理进行代码翻译时,我们会遇到这样那样的问题,看上去非常简单的一个逻辑,到了代码层面,会衍生出复杂的问题。但是,只要我们通过对现象的分析,找到一条可行的办法(例如本文中提到的竖式),然后理清楚每一种情况,并用函数式的思维去代码实现,就可以慢慢发现,原来写代码是一件非常有意思的事情。

2019-04-08 192

为价值买单

本文价值1.92RMB