найти корень куба, используя ограниченные математические операторы - PullRequest
Новая
       1

найти корень куба, используя ограниченные математические операторы

0 голосов
/ 21 декабря 2018

Мне нужно написать функцию, которая сообщает мне, является ли число идеальным кубом.Если это так, я хочу, чтобы корень куба возвращал false, как показано ниже: 

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

Он должен работать для очень больших чисел.Производительность - большой бонус.

Однако используемая мной библиотека означает, что я могу использовать только следующие математические функции / операторы: 

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

Если в JS предоставляется ответ только с использованиемвыше операторов я могу преобразовать ответ в синтаксис ( big.js ) сам (библиотека, которую я использую).Возможно ли это?

PS Мне нужно использовать big.js из-за точности, которую он гарантирует.

Ответы [ 6 ]

0 голосов
/ 04 января 2019

Чтобы избежать головной боли от кубического корня, вы можете использовать родственник big.js, называемый decimal.js-light (сам по себе или вместе с big.js)

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
0 голосов
/ 22 декабря 2018

Итак, давайте посмотрим на некоторые кубы в двоичном виде 

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), пока не получите нулевой результат.

Теперь мы можем использовать Ньютона-Рафсона, чтобы найти решение, Корень куба из Википедии услужливо дает нам формулу итерации.Если a - это число, от которого мы хотим найти корень, а x_0 - это наше первое предположение, использующее приведенное выше 

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

. Это может сойтись очень быстро.Например, с a=12345678901234567890 мы находим, что a находится между 8 ^ 21 и 8 ^ 22, следовательно, корень куба должен быть между 2 ^ 21 и 2 ^ 22.

Запуск итерации 

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 находится между 2311204 ^ 3 и 2311205 ^ 3.

Этот алгоритм может работать с вычислениями с использованием big.js.Вышеуказанные вычисления были выполнены с использованием класса Java BigInt.

0 голосов
/ 21 декабря 2018

Вот еще одна версия той же идеи, что и код Камиля Келчевского, но принятая для использования API big.js и основанная на деталях его реализации. 

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).Этот трюк должен сократить несколько итераций цикла.Потенциально использование итерации Ньютона-Рафсона вместо простого двоичного поиска может быть немного быстрее, но я не думаю, что на практике вы можете увидеть разницу.

0 голосов
/ 21 декабря 2018

Насколько я знаю, показатель степени в Javascript доступен только через библиотеку Math с Math.pow .

Используя экспоненту, кубический корень из x можно вычислить как cubeRoot(x) = x^(1/3).В javascript, использующем Math, это выглядело бы как var cubeRoot = Math.pow(x, 1/3).

Поскольку ваша функция должна возвращать false, если результат дробный, я бы использовал 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 локальных нодеях и похоже, что он может обрабатывать кубы размером 8000120000600001 (или 200001^3), прежде чем не удастся вернуть false для некоторых не кубов.Я не проверял это всесторонне, но это лучший взлом, который я могу придумать, учитывая ограничения вашей проблемы.

0 голосов
/ 21 декабря 2018

Вы можете использовать встроенную JS BigInt .Я предполагаю, что входное значение является положительным целымДля циклов while я даю аппроксимацию сложности времени, где n - количество десятичных входных цифр.Эта версия ответа была вдохновлена ​​ ответом Salix alba и вики "корень куба" :

  1. Двоичный поиск O (n log2 (10) / 3) <= <em>O (1,11 * n) (для n = 1000 я получаю 1110 итераций - тест здесь , - дляl=0 и r=a O (10/3 n) )

    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

  2. Ньютон-Рафсон схема O (log (9n)) (для n <= 1000Я получаю максимум 13 итераций <a href="https://jsfiddle.net/0t97y8ca/3/" rel="nofollow noreferrer"> тест ).У меня проблема с условием «остановка» - для чисел 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

  3. Метод Галлея O (log (3n)) (для проверенных n <= 1000 цифрЯ получаю максимум 8 итераций - <a href="https://jsfiddle.net/ahgjdzou/1/" rel="nofollow noreferrer"> тест )

    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
0 голосов
/ 21 декабря 2018

Я нашел этот замечательный ответ , который показал алгоритм, который я немного изменил.Вот что вы можете сделать: 

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
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...