Вычислить квадратный корень из BigInteger (System.Numerics.BigInteger)

Ответ 1

Проверьте, не имеет ли BigInteger идеальный квадрат имеет код для вычисления целочисленного квадратного корня Java BigInteger. Здесь он переводится на С# в качестве метода расширения.

    public static BigInteger Sqrt(this BigInteger n)
    {
        if (n == 0) return 0;
        if (n > 0)
        {
            int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));
            BigInteger root = BigInteger.One << (bitLength / 2);

            while (!isSqrt(n, root))
            {
                root += n / root;
                root /= 2;
            }

            return root;
        }

        throw new ArithmeticException("NaN");
    }

    private static Boolean isSqrt(BigInteger n, BigInteger root)
    {
        BigInteger lowerBound = root*root;
        BigInteger upperBound = (root + 1)*(root + 1);

        return (n >= lowerBound && n < upperBound);
    }

Неофициальное тестирование показывает, что это примерно на 75X медленнее, чем Math.Sqrt, для небольших целых чисел. Профилировщик VS указывает на умножения в isSqrt как горячие точки.

Ответ 2

Я не уверен, что метод Ньютона - лучший способ вычислить квадратные корни бигма, потому что он включает в себя деления, которые медленны для бонусов. Вы можете использовать метод CORDIC, который использует только сложение и сдвиги (показано здесь для unsigned ints)

static uint isqrt(uint x)
{
    int b=15; // this is the next bit we try 
    uint r=0; // r will contain the result
    uint r2=0; // here we maintain r squared
    while(b>=0) 
    {
        uint sr2=r2;
        uint sr=r;
                    // compute (r+(1<<b))**2, we have r**2 already.
        r2+=(uint)((r<<(1+b))+(1<<(b+b)));      
        r+=(uint)(1<<b);
        if (r2>x) 
        {
            r=sr;
            r2=sr2;
        }
        b--;
    }
    return r;
}

Там аналогичный метод, который использует только добавление и сдвиги, называемый "квадрат квадрата дийкстра", здесь объясняется здесь:

• http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

Ответ 3

Самый простой возможный способ вычисления квадратного корня для произвольной точности, вероятно, метод Ньютона.

Ответ 4

Вы можете преобразовать это в язык и типы переменных по вашему выбору. Вот усеченный квадратный корень в JavaScript (самый свежий для меня), который использует преимущество 1 + 3 + 5... +nth нечетное число = n ^ 2. Все переменные являются целыми числами, и это только добавляет и вычитает.

var truncSqrt = function(n) {
  var oddNumber = 1;
  var result = 0;
  while (n >= oddNumber) {
    n -= oddNumber;
    oddNumber += 2;
    result++;
  }
  return result;
};

Ответ 5

Короткий ответ: (но остерегайтесь, см. ниже для более подробной информации)

Math.Pow(Math.E, BigInteger.Log(pd) / 2)

Где pd представляет BigInteger, на котором вы хотите выполнить операцию с квадратным корнем.

Длинный ответ и объяснение:

Еще один способ понять эту проблему - понять, как работают квадратные корни и журналы.

Если у вас есть уравнение 5^x = 25, для решения для x мы должны использовать журналы. В этом примере я буду использовать естественные журналы (также возможны журналы в других базах, но естественный журнал - это простой способ).

5^x = 25

Переписывая, мы имеем:

x(ln 5) = ln 25

Чтобы выделить x, имеем

x = ln 25 / ln 5

Мы видим, что это приводит к x = 2. Но так как мы уже знаем x (x = 2, в 5 ^ 2), изменим то, что мы не знаем, и напишем новое уравнение и решим для нового неизвестного. Пусть x - результат операции квадратного корня. Это дает нам

2 = ln 25 / ln x

Переписывая для выделения x, имеем

ln x = (ln 25) / 2

Чтобы удалить журнал, мы теперь используем специальное тождество естественного логарифма и специального числа e. В частности, e^ln x = x. Переписывание уравнения теперь дает нам

e^ln x = e^((ln 25) / 2)

Упрощая левую сторону, имеем

x = e^((ln 25) / 2)

где x будет квадратным корнем из 25. Вы также можете распространить эту идею на любой корень или число, а общая формула для y-го корня x становится e^((ln x) / y).

Теперь, чтобы применить это специально к С#, BigIntegers и конкретно к этому вопросу, мы просто реализуем формулу. ПРЕДУПРЕЖДЕНИЕ: Хотя математика верна, существуют конечные пределы. Этот метод приведет вас только по соседству с большим неизвестным диапазоном (в зависимости от того, насколько большой из числа вы работаете). Возможно, именно поэтому Microsoft не применяла такой метод.

// A sample generated public key modulus
var pd = BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727");
var sqrt = Math.Pow(Math.E, BigInteger.Log(pd) / 2);

Console.WriteLine(sqrt);

ПРИМЕЧАНИЕ. Метод BigInteger.Log() возвращает double, поэтому возникают две проблемы. 1) Число неточно, и 2) существует верхний предел для того, что Log() может обрабатывать для входов BigInteger. Чтобы проверить верхний предел, мы можем посмотреть обычную форму для естественного логарифма, то есть ln x = y. Другими словами, e^y = x. Так как double является возвращаемым типом BigInteger.Log(), то разумно предположить, что наибольший BigInteger затем будет поднят до double.MaxValue. На моем компьютере это будет e^1.79769313486232E+308. Неточность не обрабатывается. Кто-то хочет реализовать BigDecimal и обновить BigInteger.Log()?

Потребитель, будьте осторожны, но он доставит вас по соседству, и возведение в квадрат результата приведет к числу, близкому к исходному входу, до стольких цифр и не столь точно, как ответ RedGreenCode. Счастливое (квадратное) укоренение!;)