前言
这是一篇偏综合性的总结, 根据笔者的 routine 整理好的, 并对代码进行了改进. 以下内容出处均已在 参考资料 中列出, 如有侵权, 联系笔者删除.
思维导图
[图片上传失败...(image-29c229-1586171075473)]
<a name="9hn0G"></a>
前置知识
<a name="oM17p"></a>
本质原因
计算机是二进制的, 无法直接表示正负数, 另外在计算机内部直接实现减法, 也会影响计算机效率, 所以人们希望要找到一种既能使用二进制表示 10 进制正负数的编码格式, 同时这种编码格式又能满足将减法转换成加法进行运算.<br />
<a name="crcuw"></a>
原码, 反码和补码
<a name="FHWGr"></a>
原码
image.PNG
<a name="nx3FJ"></a>
反码
image.PNG
<a name="Q1D58"></a>
补码
image.PNG
<a name="YIcky"></a>
总结
要想弄清楚补码, 必须要弄清楚补码要解决的问题, 计算机是二进制的, 无法直接表示正负数, 另外在计算机内部直接实现减法, 也会影响计算机效率, 所以人们希望要找到一种既能使用二进制表示 10 进制正负数的编码格式, 同时这种编码格式又能满足将减法转换成加法进行运算, 同时满足这两个条件有反码和补码, 但由于反码中的 0 有两个编码格式, 另外反码加法运算也比较复杂, 慢慢地反码被淘汰了. 补码刚好解决了反码的两个缺点, 所以补码成了现代计算机的通用编码.<br />
<a name="Bsieu"></a>
IEEE 754 标准
<a name="wekxi"></a>
背景
随着技术的更新, 在 1978 年的时候, Intel 公司推出了首枚 16bit 微处理器 (CPU)8086. 这台 x86 的老祖宗虽然自身无法处理小数的运算, 但是在编译器层面可以通过用整数指令模拟出小数的运算, 不过这种运算的方式效率是非常低的.<br />
- <br />
- 为了解决这类问题, 1980 年 Intel 公司推出了首款 x87 浮点协处理器运算单元 (FPU)8087, 通过主板上额外的协处理器插槽,
- 安装后不仅可以解决小数的运算问题, 并且对于不同的应用, 性能提升了 20%~500%.
- <br />
- <br />
- 对于计算机发展来说, 8087 是款非常棒的 FPU, 但是它的意义真正体现在这款 FPU 的设计师之一的 William Kahan 教授设计了
- IEEE-754 标准的雏形, 而正是因为这套标准, 我们计算机才能精准的处理小数.
- <br />
- <br />
- 1985 年时, IEEE 推出了 IEEE 754-1985 标准, 随着大佬们的努力, IEEE 还推出了目前的版本 --IEEE 754-2008.
- <br />
- <br />
- 而我们使用的高级语言中浮点数的运算, 如 C,C++,JavaScript,Java 都是基于这个标准而定.
- <br />
- <a name="MzWgK">
- </a>
概念
image.PNG
<br />
image.PNG
<br /> 或 < br />
image.PNG
<br /> 也叫 < br />
image.PNG
<a name="RH8nK"></a>
概念
JavaScript 的数字类型的本质就是一个基于 IEEE 754 标准的双精度 64 位的浮点数.
<a name="yGXlK"></a>
小数运算 (为什么 0.2 + 0.1 !== 0.3?)
<a name="I3R1e"></a>
概述
0.1 和 0.2 按照 IEEE 754 存储后都有精度损失
运算后进行规格化时的舍入操作也有精度损失
- **
- <a name="A9NP0"></a>
详解
关于浮点数的运算, 一般由以下五个步骤完成: 对阶, 尾数运算, 规格化, 舍入处理, 溢出判断.<br />
image.PNG
- <br />
- 将它转换为 10 进制数就得到 0.30000000000000004440892098500626
- <br />
- 因为两次存储时的精度丢失加上一次运算时的精度丢失, 最终导致了 0.1 + 0.2 !== 0.3
- <a name="BZ9e6">
- </a>
解决方案
number-precision<br /> 全面总结 JS 中浮点数运算问题 - 掘金
<a name="sXlqN"></a>
大数运算如何处理?
<a name="uyCRz"></a>
现成方案
1.bignumber.JS<br />2.true-JSON-bigint.JS<br />3.BigInt - JavaScript | MDN<br />
image.PNG
<a name="DsN8Z"></a>
大数运算
<a name="fdEoq"></a>
核心思想
既然数字类型会有精度问题, 那就统统转用字符串来处理.
<a name="KMWlE"></a>
大数相加
- <br /> 普通版本
- /**
- * @param {string} a
- * @param {string} b
- * @return {number}
- */
- function add(a, b) {
- // 首先检查传来的大数是否是字符串类型, 如果传 Number 类型的大数, 在传入的时候已经丢失精度了,
- // 就如 如果传入 11111111111111111, 处理的时候已经是丢失精度的 11111111111111112 了, 则需要传入
- // 字符串类型的数字 '11111111111111111'
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- // 格式化数字
- const formatNum = num => (isNaN(+num) ? 0 : +num)
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- const result = []
- a = a.split("").reverse()
- b = b.split("").reverse()
- const length = Math.max(a.length, b.length)
- let carry = 0
- // 以较长的数字为基准进行从前往后逐个加和, 为避免两个数相加最高位进位后, 导
- // 致结果长度大于两个数字中的长度, for 循环加和长度为最长数字长度加一
- for (let i = 0; i <= length; i++) {
- const tempResult = formatNum(a[i]) + formatNum(b[i]) + carry
- result[i] = tempResult % 10
- // 当加和的数字大于 10 的情况下, 进行进位操作, 将要进位的数字赋值给 temp, 在下一轮使用
- carry = Math.trunc(tempResult / 10)
- }
- // 计算完成, 反转回来
- result.reverse()
- // 将数组 for 中多加的一位进行处理, 如果最高位没有进位则结果第一个数位 0,
- // 结果第一个数位 1, 则发生了进位. 如 99+3, 最大数字长度位 2, 结果数长度位 3
- // 此时结果的第一位为 1, 发生了进位, 第一位保留, 如果是 2+94, 第一位为 0, 则不保留第一位
- return result.join('').replace(/^0+/,"")
- }
- <br /> 奇技淫巧版
- /**
- * @param {string} a
- * @param {string} b
- * @return {number}
- */
- function add(a, b) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- let result = ""
- let c = 0
- a = a.split("")
- b = b.split("")
- while (a.length || b.length || c) {
- // ~ 取反操作符,~0 === -1, ~~0 === 0, ~~null === 0, ~~undefined === 0, ~~'0' === 0
- // 用 + 也能实现字符转成数字, 不过~~ 能处理 null 的情况
- c = ~~a.pop() + ~~b.pop() + c
- result += c % 10
- // c>0 会返回一个布尔值, 布尔值转换成数字的时候 true 为 1,false 为 0
- c = c> 9
- }
- return result.replace(/^0+/, "")
- }
- <br /> 优化版
- /**
- * @param {string} a
- * @param {string} b
- * @return {number}
- */
- function add(a, b) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- // 主要思想是分开一段段加, 这样既能保证精度且不溢出, 也能提高速度
- // 如果索引超范围, 或者长度小于 1 那么返回空字符串
- const MAX_PERCISION = Number.MAX_SAFE_INTEGER.toString().length - 1
- const arr = []
- while (a.length || b.length) {
- arr.push(
- parseInt(a.substring(a.length - MAX_PERCISION) || 0, 10) +
- parseInt(b.substring(b.length - MAX_PERCISION) || 0, 10)
- )
- a = a.substring(0, a.length - MAX_PERCISION)
- b = b.substring(0, b.length - MAX_PERCISION)
- }
- let carry = 0
- let result = ""
- while (arr.length) {
- const temp = (arr.shift() + carry).toString()
- result = temp.substring(temp.length - MAX_PERCISION) + result
- carry = parseInt(
- temp.substring(0, temp.length - MAX_PERCISION) || 0,
- 10
- )
- }
- return result
- }
- // 简化 =>
- /**
- * @param {string} a
- * @param {string} b
- * @return {number}
- */
- function add(a, b) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- const MAX_PERCISION = Number.MAX_SAFE_INTEGER.toString().length - 1
- let result = ""
- let carry = 0
- while (a.length || b.length) {
- const temp = (
- parseInt(a.substring(a.length - MAX_PERCISION) || 0, 10) +
- parseInt(b.substring(b.length - MAX_PERCISION) || 0, 10) +
- carry
- ).toString()
- result = temp.substring(temp.length - MAX_PERCISION) + result
- carry = parseInt(
- temp.substring(0, temp.length - MAX_PERCISION) || 0,
- 10
- )
- a = a.substring(0, a.length - MAX_PERCISION)
- b = b.substring(0, b.length - MAX_PERCISION)
- }
- return result
- }
- <a name="sWeXq"></a>
大数相减
- <br /> 奇技淫巧版
- /**
- * @param {string} a
- * @param {string} b
- * @return {number}
- */
- function minus(a, b) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- while (a.length <b.length) {
- a = "0" + a
- }
- while (b.length < a.length) {
- b = "0" + b
- }
- let result = ""
- let borrow = false
- a = a.split("")
- b = b.split("")
- while (a.length) {
- const minuend = ~~a.pop()
- const subtrahend = ~~b.pop() + borrow
- if (minuend>= subtrahend) {
- borrow = minuend - subtrahend
- result = borrow + result
- borrow = false
- } else {
- borrow = minuend + 10 - subtrahend
- result = borrow + result
- borrow = true
- }
- // 判断最高位有无借位, 若有借位, 则说明结果为负数
- if (a.length === 0 && borrow) {
- result = "-" + result
- }
- }
- result = result.replace(/^0+/, "")
- // 判断最后的结果是否为 0
- if (result === "") {
- result = 0
- }
- return result
- }
- <a name="KR1tt"></a>
大数相乘
目前大数乘法算法主要有以下几种思路:
模拟小学乘法: 最简单的乘法竖式手算的累加型;
分治乘法: 最简单的是 Karatsuba 乘法, 一般化以后有 Toom-Cook 乘法;
快速傅里叶变换 FFT:(为了避免精度问题, 可以改用快速数论变换 FNTT), 时间复杂度 O(N lgN lglgN). 具体可参照 Schönhage-Strassen algorithm;
中国剩余定理: 把每个数分解到一些互素的模上, 然后每个同余方程对应乘起来就行;
- <br /> 模拟小学乘法版
- /**
- * @param {string} a
- * @param {string} b
- * @return {string}
- */
- function multiply(a, b) {
- const cn = a.length + b.length
- const c = new Array(cn).fill(0)
- /****
- * 两两相乘, 并放进不同的格子里, 如果里面有东西, 则相加
- * 0
- * 8
- * 10
- * 4
- * 5
- */
- for (let i = 0; i <a.length; i++) {
- for (let j = 0; j < b.length; j++) {
- c[i + j + 1] += Number(a[i]) * Number(b[j])
- }
- }
- // 处理进位
- for (let i = cn - 1; i>= 0; i--) {
- const carry = Math.trunc(c[i] / 10)
- if (carry) {
- c[i - 1] += carry
- }
- c[i] = c[i] % 10
- }
- while (c[0] === 0) {
- c.shift()
- }
- // 处理最前面的零
- return c.join("") ||"0"
- }
- <br /> 利用下标取巧版
- /**
- * @param {string} a
- * @param {string} b
- * @return {string}
- */
- function multiply(num1, num2) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- let len1 = a.length,
- len2 = b.length
- let ans = []
- // 这里倒过来遍历很妙, 不需要处理进位了
- for (let i = len1 - 1; i>= 0; i--) {
- for (let j = len2 - 1; j>= 0; j--) {
- let index1 = i + j,
- index2 = i + j + 1
- let mul = a[i] * b[j] + (ans[index2] || 0)
- ans[index1] = Math.floor(mul / 10) + (ans[index1] || 0)
- ans[index2] = mul % 10
- }
- }
- // 去掉前置 0
- let result = ans.join("").replace(/^0+/,"")
- // 不要转成数字判断, 否则可能会超精度!
- return !result ? "0" : result
- }
- <a name="haUnb"></a>
- /**
- * @param {string} a
- * @param {string} b
- * @return {string}
- */
- function divide(a, b) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(a) || !checkNum(b)) {
- throw new TypeError("Big Number Type Error")
- }
- const alen = a.length
- const blen = b.length
- let quotient = 0
- let remainder = 0
- const result = []
- let temp = 0
- for (let i = 0; i <alen; i++) {
- temp = remainder * 10 + parseInt(a[i])
- if (temp < b) {
- remainder = temp
- result.push(0)
- } else {
- quotient = parseInt(temp / b)
- remainder = temp % b
- result.push(quotient)
- }
- }
- return [result.join("").replace(/\b(0+)/gi,""), remainder] // 结果返回 [商, 余数]
- }
- <a name="QvjwM"></a>
- function fact(num) {
- let result = 1
- for(let i=1; i<=num; i++){
- result = result * i
- }
- return result
- }
- // =>
- function fact(num) {
- const checkNum = num => typeof num === "string" && !isNaN(Number(num))
- if (!checkNum(num)) {
- throw new TypeError("Big Number Type Error")
- }
- let result = "1"
- for (let i = "1"; lte(i, num); i = add(i, "1")) {
- result = multiply(result, i)
- }
- return result
- }
- function lte(num1, num2) {
- if (num1.length <num2.length) {
- return true
- } else if (num1.length === num2.length) {
- return num1 <= num2
- } else {
- return false
- }
- }
- <a name="bBxat"></a>
来源: http://www.jianshu.com/p/c261f42da64d