什么是快速计算数字有效位数的方法？

Question

什么是快速计算数字有效位数的方法？

我有以下函数，它能够工作，但由于字符串操作而相当缓慢。

/**
 * Count the number of significant digits of a number.
 *
 * For example:
 *   2.34 returns 3
 *   0.0034 returns 2
 *   120.5e+3 returns 4
 *
 * @param {Number} value
 * @return {Number} The number of significant digits
 */
function digits (value) {
  return value
      .toExponential()
      .replace(/e[\+\-0-9]*$/, '')  // remove exponential notation
      .replace( /^0\.?0*|\./, '')    // remove decimal point and leading zeros
      .length
};

有更快的方法吗？

更新：这里是一份用于测试正确功能的断言列表：

assert.equal(digits(0), 0);
assert.equal(digits(2), 1);
assert.equal(digits(1234), 4);
assert.equal(digits(2.34), 3);
assert.equal(digits(3000), 1);
assert.equal(digits(0.0034), 2);
assert.equal(digits(120.5e50), 4);
assert.equal(digits(1120.5e+50), 5);
assert.equal(digits(120.52e-50), 5);
assert.equal(digits(Math.PI), 16);

我的自定义方法对于 digits(0) 失败了，我通过在第二个正则表达式中添加一个 ? 来修复这个问题。

- Jos de Jong

---

你试图做的事情在本质上受到浮点数表示为二进制浮点数的挑战。 - Pointy

除非使用一些基准测试，否则任何答案都不足以令人满意。你如何定义“最快”？任何人都可以提出任意的解决方案，我们都可以争论一整夜，认为它比你的更快/更慢。 - Mohammed Joraid

@JosdeJong 我来回答。优点是您可以在值上不执行任何数学操作就完成它。缺点是旧浏览器不支持类型化数组。 - Pointy

你是在参考某种描述你正在尝试实现的技术的纸质材料吗？我越想越觉得，由于浮点数学的本质和将十进制转换为二进制浮点数学的行为所遇到的困难的结合，你正在尝试做的事情本质上非常困难。即使你按照我建议的进行二进制操作，事情也会变得很奇怪：例如，值“0.3”在二进制中是一个重复的小数。 - Pointy

这是一个简单的jsbin示例，用于探索该问题。(http://jsbin.com/huqod/1) 在输入框中尝试一些简单的值;18很有趣。请注意，即使进行了一些简单的操作，事情也变得很奇怪。有时十进制表示法会是“干净的”，但二进制是循环小数。有时十进制表示不精确。浮点数运算就是古怪和真的很难在分析上处理。 - Pointy

Answer 1

这里有一种更数学化的执行相同操作的方法（似乎要快得多）。 JSPerf比较了三种实现方式。

根据http://ecma262-5.com/ELS5_HTML.htm#Section_8.5，整数 n < +-(2^53) 可以准确计算。浮点数被转换为字符串，然后强制转换为整数（通过删除小数部分，因此类似的规则适用）。

var log10 = Math.log(10);
function getSignificantDigitCount(n) {
    n = Math.abs(String(n).replace(".", "")); //remove decimal and make positive
    if (n == 0) return 0;
    while (n != 0 && n % 10 == 0) n /= 10; //kill the 0s at the end of n

    return Math.floor(Math.log(n) / log10) + 1; //get number of digits
}

- megawac

---

这恰好是我在寻找的“不同”的解决方案类型。非常感谢你编写jsperf。我为最大数字值（pi）添加了另一个测试案例：http://jsperf.com/get-significant-digits/2。 - Jos de Jong

这真的很棒，你的方法快了2-4倍！ - Jos de Jong

一个小问题：当n=0时，该函数返回-Infinity而不是0。 - Jos de Jong

啊哦:( 这个函数对于输入如 0.0034, 120.5e50, 120.5e-50 也会给出错误的结果。 - Jos de Jong

任何涉及对值进行操作的解决方案都会带来问题。 - Pointy

Answer 2

还有另一种方法，使用字符串操作并处理一些特殊情况以获得更好的性能：

function digits(value) {
    if (value === 0) {
        return 0;
    }
    //create absolute value and
    var t1 = ("" + Math.abs(value));
    //remove decimal point
    var t2 = t1.replace(".","");

    //if number is represented by scientific notation,
    //the places before "e" (minus "-" and ".") are the
    //significant digits. So here we can just return the index
    //"-234.3e+50" -> "2343e+50" -> indexOf("e") === 4
    var i = t2.indexOf("e");
    if (i > -1) {
        return i;
    } 

    //if the original number had a decimal point,
    //trailing zeros are already removed, since irrelevant
    //0.001230000.toString() -> "0.00123" -> "000123"
    if (t2.length < t1.length) {
        // -> remove only leading zeros
        return t2.replace(/^0+/,'').length;
    }

    //if number did not contain decimal point,
    //leading zeros are already removed
    //000123000.toString() -> "123000"
    // -> remove only trailing zeros
    return t2.replace(/0+$/,'').length;
}

- basilikum

Answer 3

正则表达式的轻微改进

function digits (value) {
  return value
      .toExponential()
      .replace(/^([0-9]+)\.?([0-9]+)?e[\+\-0-9]*$/g, "$1$2")
      .length
};

- Omer Arshad

---

这怎么能更快呢？仅仅减少对.replace()的调用次数并不总是更快 - 在大多数情况下，这只会让人觉得你在炫耀你的正则表达式技巧。 - BoltClock

抱歉，我之前认为这种方法更快，但似乎这种改进并没有太大的区别:( - Jos de Jong

Answer 4

正则字符串检查。稍微有所改进。

function digits(value) {
  value = "" + value;
  var res = 0;
  for (var i = 0, len = value.length; i < len; i++){
    if (value[i]==="e")break;
    if (+value[i]>=0)
      res++;
}
  return res;
};

---

jsperf基准测试结果与原帖和其他答案的代码进行比较。

---

更新

function digits(value) {

  console.log(value);
  value = "" + (+value);

  var res = 0;
  for (var i = 0, len = value.length; i < len; i++) {
  
  if (value[i] === "e") 
    {
    break;
    }
    
    if (+value[i] >= 0)
    {
     res++;
    }     
  }
  console.log(value);
  return res;
}

function check(val1, val2) {

  console.log( val1+"==="+val2 +" = "+ (val1 === val2));
  return val1 === val2;
}


check(digits(0), 1);
check(digits(2), 1);
check(digits(1234), 4);
check(digits("0012003400"), 8);
check(digits("0022.002200"), 6);
check(digits(2.34), 3);
check(digits(3000), 4);
check(digits(0.0034), 2);
check(digits(12003), 5);
check(digits(1.23e+50), 3);
check(digits("1.23e+50"), 3);
check(digits(120.5e51), 4);
check(digits(1120.5e+52), 5);
check(digits(120.52e-53), 5);
check(digits(Math.PI), 16);

- Mohammed Joraid

---

简单明了。但是对于大/小值不起作用：字符串表示法会包含指数（如“1.23e+50”）。如果我们计算到指数部分的数字，它就能够正常工作。 - Jos de Jong

更重要的是，对于一个包含一半零的值，例如“12003” -> 有5个有效数字，但该方法返回3，它不能正确地工作。 - Jos de Jong

Answer 5

你可以使用类型化数组直接检查浮点值的字节。这样做的优点是速度快，不需要进行任何数学运算。你可以直接查看尾数的位。

你可以从以下内容开始：

var n = yourFloatingPointValue; 

var f64 = new Float64Array(1);
var dv = new DataView(f64.buffer);

dv.setFloat64(0, n, false); // false -> big-endian

var bytes = [];
for (var i = 0; i < 8; i++)
  bytes.push(dv.getUint8(i));

现在 bytes 数组包含整数，表示浮点值在内存中的8位值。第一个字节包含符号位在最高位位置，以及指数的前7位。第二个字节包含指数的5个最低有效位和尾数的前三位。剩下的字节都是尾数。

- Pointy

---

能否请您将它封装成一个函数，这样我们就可以将其添加到我们正在运行的小型基准测试中。只是好奇，变量n后来会发生什么？ - Mohammed Joraid

啊，我明白你的意思了。通过TypedArray访问内部位真的很酷！确实很有趣看看它的性能如何。如果真的更快，那么很容易创建一个函数，仅在浏览器支持时选择此方法，否则会回退到另一种解决方案。 - Jos de Jong

我很乐意将其封装在一个函数中。由于它严格按二进制方式工作，因此很难比较结果。我有一个真实世界的义务即将到来，但几个小时后我就可以添加更多内容了。 - Pointy

我期待着看到您如何估算二进制表示中的有效十进制位数... - Bergi

@Bergi 嗯，考虑到OP的动机，我认为那并不是真正必要的。如果你的精度用完了，无论你看二进制位还是十进制表示法都一样。对我来说，查看十进制展开的问题在于它不能告诉你实际情况。一个有很多二进制位剩余的数字可能会以完全不同的方式展开。 - Pointy

@Bergi，实际上我越想，就越觉得这是一场徒劳的追逐。那么0.3呢？它会在尾数中添加许多1。当你在进行一些数学计算后从二进制转换为十进制时，你会得到类似的不良数字。简而言之，我认为这种努力是错误的；浮点数只是复杂的，如果其语义不理想，则应该寻求“大十进制”固定点解决方案。 - Pointy

Answer 6

有一种更快、更间接的方法，就是将其转换为字符串并找到其长度。

a = 2.303
sig_fig = len(str(a))-len(str(int(a)))-1

额外的-1是为了“.”

- Bitopan Gogoi