代码之家 › 专栏 › 技术社区 › danday74

使用有限的数学运算符查找多维数据集根

big.js math javascript

-1

danday74 · 技术社区 · 7 年前

cubeRoot(1)   // 1
cubeRoot(8)   // 2
cubeRoot(9)   // false
cubeRoot(27)  // 3
cubeRoot(28)  // false

它必须适用于非常大的数字。表现是一个很大的奖励。

但是,我使用的库意味着我只能使用以下数学函数/运算符:

abs, round, sqrt
/ * + -
===
> >= < <=
%
^

big.js )语法我自己(我正在使用的库)。这可能吗?

big.js 由于它保证了精度。

6 回复 | 直到 7 年前

SergGr 7 年前

这里是与Kamil Kieczewski代码相同的想法的另一个版本,但采用了big.js API并依赖于其实现细节。

function isZero(v) {
    let digits = v.c;
    return digits.length === 1 && digits[0] === 0;
}

function isInteger(v) {
    if (isZero(v))
        return true;
    return v.c.length <= v.e + 1;
}

function neg(v) {
    return new Big(0).minus(v);
}


function cubeRoot(v) {
    const ZERO = Big(0);
    const TEN = new Big(10);

    let c0 = v.cmp(ZERO);
    if (c0 === 0)
        return ZERO;
    if (c0 < 0) {
        let abs3 = cubeRoot(v.abs());
        if (abs3 instanceof Big)
            return neg(abs3);
        else
            return abs3;
    }

    if (!isInteger(v))
        return false;

    // use 10 because it should be fast given the way the value is stored inside Big
    let left = TEN.pow(Math.floor(v.e / 3));
    if (left.pow(3).eq(v))
        return left;

    let right = left.times(TEN);

    while (true) {
        let middle = left.plus(right).div(2);
        if (!isInteger(middle)) {
            middle = middle.round(0, 0); // round down
        }
        if (middle.eq(left))
            return false;
        let m3 = middle.pow(3);
        let cmp = m3.cmp(v);
        if (cmp === 0)
            return middle;
        if (cmp < 0)
            left = middle;
        else
            right = middle;
    }
}

left 和 right 而不是卡米尔的密码。特别是,这取决于以下事实: Big 以标准化指数表示法存储值:作为十进制数字和指数的数组。所以我们很容易找到这样的 n 那个 10^n <= cubeRoot(value) < 10^(n+1) . 这个技巧应该减少循环的一些迭代。潜在使用 Newton-Raphson iteration 代替简单的二进制搜索可能会快一点,但我认为在实践中你看不出有什么不同。

Salix alba 7 年前

让我们来看一些二进制的立方体

2^3 = 8 = 100b (3 binary digits)
4^3 = 64 = 100 000b  (6 binary digits)
8^3 = 512 = 100 000 000b (9 binary digits)
(2^n)^3 = 2^(3n) = (3n binary digits).

因此,对于粗略的第一次猜测,计算二进制数字的数量, d 说,除以三,让 n = d/3 这告诉我们立方体根数是否介于 2^n 和 2^(n+1)

如果无法访问二进制数字,只需重复除以8(或8的幂),直到得到零结果。

现在我们可以用牛顿-拉斐逊来解释这个问题。 Wikipedia cube root 给出了迭代公式。如果 a 是我们要查找和的根的数字 x_0 我们的第一个猜测是使用上述方法吗

x_{n+1} = ( a / x_n^2 + 2 x_n ) / 3.

这可以很快收敛。例如 a=12345678901234567890 A.

运行迭代

x_1 = 2333795, x_1^3 = 12711245751310434875 
x_2 = 2311422, x_2^3 = 12349168818517523448
x_3 = 2311204, x_3^3 = 12345675040784217664
x_4 = 2311204, x_4^3 = 12345675040784217664

我们看到它在三次迭代后收敛了。检查表明 A.

此算法可以使用big.js进行计算。以上计算是使用Java的BigInt类完成的。

Kamil KieÅczewski 7 年前

您可以使用JS内置 BigInt . 我假设输入是正整数。对于 while N 是输入的小数位数。这个版本的答案的灵感来自 Salix alba answer 和 wiki "cube root"

Binary search O(n日志2(10)/3) <= O(1.11*n) (对于n=1000,我得到1110次迭代-测试 here ,-用于 l=0 和 r=a )

function cubicRoot(a) 
{ 
  let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
  let r = 2n ** BigInt(d+1); // right boundary approximation
  let l = 2n ** BigInt(d);   // left boundary approximation
  let x=BigInt(l); 
  let o=BigInt(0);           // old historical value
  
  while(1) {
    o = x;
    y = x * x * x;      
    y<a ? l=x : r=x;      
    if(y==a) return x;
    x = l + (r - l)/2n;      
    if(o==x) return false;
  }
}

// TEST

let t = "98765432109876543210987654321098765432109876543210987";
let B = BigInt(t) * BigInt(t) * BigInt(t);

console.log('cRoot(B):   ', cubicRoot( B )     .toString());
console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

Newton-Raphson O(对数(9n)) (对于n<=1000,我最多得到13次迭代 test ).我对数字的“停止”条件有问题 a=b*b*b - 1 我需要检查x的两个历史值(如果它们至少出现一次,那么停止)——但我不知道在某些情况下,我们应该检查树或更多的历史值来停止算法。

function cubicRoot(a) 
{ 
  let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
  let x = 2n ** BigInt(d);    
  let o=BigInt(0); // last history value
  let u=BigInt(0); // pre-last history value
  let i=0; // loop counter for worst scenario stop condition
  
  while(i<d*4) {
    i++;
    u = o;
    o = x;     
    y = x*x*x;            
    if(y===a) return x;
    x = ( a / (x*x) + 2n* x ) / 3n;
    if(o==x || u==x) return false; 
  }
  
  return false; // worst scenario - if for some case algorithm not finish after d*4 iterations
}

// TEST

let t = "98765432109876543210987654321098765432109876543210987";
let B = BigInt(t) * BigInt(t) * BigInt(t);

console.log('cRoot(B):   ', cubicRoot( B )     .toString());
console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

Halley method (对于测试的n<=1000位数,我最多可以进行8次迭代- test

function cubicRoot(a) 
{ 
  let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
  let x = 2n ** BigInt(d);    
  let o=BigInt(0); // last history value
  let i=0; // loop counter for worst scenario stop condition
  
  while(i<d) {
    i++;
    o = x;     
    y = x*x*x;            
    if(y==a) return x;
    x = 1n + x*(y + 2n*a)/(2n*y + a);
    if(o==x) return false; 
  }
  
  return false; // worst scenario (??)
}

// TEST

let t = "98765432109876543210987654321098765432109876543210987";
let B = BigInt(t) * BigInt(t) * BigInt(t);

console.log('cRoot(B):   ', cubicRoot( B )     .toString());
console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

Jack Bashford 7 年前

我发现 this great answer ,它显示了一个我稍微修改过的算法。以下是您可以做的:

function simpleCubeRoot(x) {    
    if (x === 0) {
        return 0;
    }
    if (x < 0) {
        return -simpleCubeRoot(-x);
    }

    var r = x;
    var ex = 0;

    while (r < 0.125) { 
        r *= 8; ex--; 
    }
    while (r > 1.0) { 
        r *= 0.125; ex++; 
    }

    r = (-0.46946116 * r + 1.072302) * r + 0.3812513;

    while (ex < 0) { 
        r *= 0.5; ex++; 
    }
    while (ex > 0) { 
        r *= 2; ex--; 
    }

    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);

    if (Number.isInteger(r)) {
        return r;
    }
    return false;
}

演示:

function simpleCubeRoot(x) {
    if (x === 0) {
        return 0;
    }
    if (x < 0) {
        return -simpleCubeRoot(-x);
    }

    var r = x;
    var ex = 0;

    while (r < 0.125) {
        r *= 8;
        ex--;
    }
    while (r > 1.0) {
        r *= 0.125;
        ex++;
    }

    r = (-0.46946116 * r + 1.072302) * r + 0.3812513;

    while (ex < 0) {
        r *= 0.5;
        ex++;
    }
    while (ex > 0) {
        r *= 2;
        ex--;
    }

    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);

    if (Number.isInteger(r)) {
        return r;
    }
    return false;
}

console.log(simpleCubeRoot(27)); //Should return 3
console.log(simpleCubeRoot(0)); //Should return 0

Guillaume Boutin 7 年前

据我所知,Javascript中的指数只能通过数学库通过 Math.pow .

x 可通过以下公式计算 cubeRoot(x) = x^(1/3) . 在使用Math的javascript中,这看起来像 var cubeRoot = Math.pow(x, 1/3) .

Math.round 比较立方根。您的函数如下所示:

function cubeRoot(x) {
    var root = Math.pow(x, 1/3);
    if (Math.round(root) !== root) {
        return false;
    }
    return root;
}

但是, 1/3 0.33333... 在一定的浮动精度下,这将不适用于大型多维数据集。例如, Math.pow(45629414826904, 1/3) 可能会给你类似的回报 35733.99999999998 .

然后我会做的是,如果四舍五入结果的差异非常小(比如小于 1/1000000 ),重新计算数字的立方,以查看这是否能使您恢复原始状态 x

function cubeRoot(x) {
    var root = Math.pow(x, 1/3);
    var roundedRoot = Math.round(root);
    var diff = Math.abs(root - roundedRoot);

    if (diff <= 1/1000000) {
        var reCubed = Math.pow(roundedRoot, 3);
        if (reCubed === x) {
           return roundedRoot;
        }
        return false;
    }
    if (diff !== roundedRoot) {
        return false;
    }
    return root;
}

我在y local NodeJ上进行了一些测试,它似乎可以处理最大的多维数据集 8000120000600001 (或 200001^3 )在未能返回之前 false 在一些非立方体上。我还没有对它进行过广泛的测试,但鉴于您的问题的局限性,这是我能想出的最好的破解方法。

danday74 7 年前

为了避免立方根头痛,您可以使用 big.js decimal.js-light big.js )

不支持分数次幂,但 decimal.js-light 为此,您可以按如下方式获取多维数据集根:

const Big = require('big.js')
const Decimal = require('decimal.js-light')

const nthRoot = (bigNumber, intRoot) => {
  const strBigNumber = bigNumber.toFixed()
  const decimal = Decimal(strBigNumber)
  const root = decimal.pow(1 / intRoot)
  return Big(root.toFixed())
}

module.exports = nthRoot

使用方法如下:

nthRoot(Big(8), 3)          // 1.9999999999999998613
nthRoot(Big(8), 3).round()  // 2