none
квадратный корень из BigInteger RRS feed

  • Вопрос

  • Подскажите функцию для извлечения кв. корня из числа BigInteger (System.Numerics.BigInteger). Метод Pow работает только с целыми степенями.
    • Перемещено Siddharth Chavan 1 октября 2010 г. 22:09 MSDN Forums Consolidation (От:Visual C#)
    7 декабря 2009 г. 20:11

Ответы

  • Написать функцию, реализующую метод Ньютона.

    public static BigInteger SqRtN(BigInteger N)
            {
                /*++
                 *  Using Newton Raphson method we calculate the
                 *  square root (N/g + g)/2
                 */
                BigInteger rootN = N;
                int bitLength = 1; // There is a bug in finding bit length hence we start with 1 not 0
                while (rootN / 2 != 0)
                {
                    rootN /= 2;
                    bitLength++;
                }
                bitLength = (bitLength + 1) / 2;
                rootN = N >> bitLength;
    
                BigInteger lastRoot = BigInteger.Zero;
                do
                {
                    lastRoot = rootN;
                    rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
                }
                while (!((rootN ^ lastRoot).ToString() == "0"));
                return rootN;
            } // SqRtN

    Источник BigInteger square root help
    • Предложено в качестве ответа I.Vorontsov 8 декабря 2009 г. 7:16
    • Изменено I.Vorontsov 10 декабря 2009 г. 17:05
    • Помечено в качестве ответа Moiseev Stanislav 22 декабря 2009 г. 10:27
    8 декабря 2009 г. 7:16

Все ответы

  • Math.Sqrt()

    Если для конкретного типа данных нет каста по умолчанию то кастить в Double в явном виде.

    This posting is provided "AS IS" with no warranties, and confers no rights.
    7 декабря 2009 г. 21:21
    Модератор
  • Написать функцию, реализующую метод Ньютона.

    public static BigInteger SqRtN(BigInteger N)
            {
                /*++
                 *  Using Newton Raphson method we calculate the
                 *  square root (N/g + g)/2
                 */
                BigInteger rootN = N;
                int bitLength = 1; // There is a bug in finding bit length hence we start with 1 not 0
                while (rootN / 2 != 0)
                {
                    rootN /= 2;
                    bitLength++;
                }
                bitLength = (bitLength + 1) / 2;
                rootN = N >> bitLength;
    
                BigInteger lastRoot = BigInteger.Zero;
                do
                {
                    lastRoot = rootN;
                    rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
                }
                while (!((rootN ^ lastRoot).ToString() == "0"));
                return rootN;
            } // SqRtN

    Источник BigInteger square root help
    • Предложено в качестве ответа I.Vorontsov 8 декабря 2009 г. 7:16
    • Изменено I.Vorontsov 10 декабря 2009 г. 17:05
    • Помечено в качестве ответа Moiseev Stanislav 22 декабря 2009 г. 10:27
    8 декабря 2009 г. 7:16
  • Спасибо за помощь.
    Правда, по результатам тестов скорость работы с большими числами в C# оказалась меньше примерно в 2 раза, чем на PHP.
    А я надеялся на то, что C# будет быстрее.
    8 декабря 2009 г. 16:00
  • Не забывайте отмечать ответы..
    8 декабря 2009 г. 20:28
  • Что нибудь в этом роде скорее всего будет работать быстрее (и позволит использовать произвольные степени, а не только 1/2):

        class Program
        {
            static void Main(string[] args)
            {
                BigInteger bi = 100000000;
    
                BigInteger root = Sqrt(bi);
            }
    
            private static BigInteger MaxDoubleInteger = new BigInteger(Double.MaxValue);
    
            public static BigInteger Sqrt(BigInteger bi)       
            {          
                BigInteger sqrt;
    
                if (bi < MaxDoubleInteger)
                {
                    sqrt = new BigInteger(Math.Sqrt((double)bi));
                }
                else           
                {           
                    double sqrtExp = BigInteger.Log10(bi) / 2;
              
                    double wholePower = Math.Floor(sqrtExp);
    
                    double reminderPower = sqrtExp - wholePower;
    
                    sqrt = BigInteger.Pow(new BigInteger(10), (int)(wholePower - 3)) * new BigInteger(Math.Pow(10, reminderPower + 3));
                }
    
                return sqrt;
            }

    Если хочется ускорить метод Ньютона то наверное стоит перестать сравнивать строки:

    while
     (!((rootN ^ lastRoot).ToString() == "0"
    ));

    This posting is provided "AS IS" with no warranties, and confers no rights.
    12 декабря 2009 г. 1:39
    Модератор
  • Тип Double работает с точностью 15 десятичных цифр. Так что для чисел больше Int64 этот метод даёт приближённый результат. Функция ниже пусть и медленная, но работает правильно.

    А Math.Sqrt можно использовать как первое приближение для rootN.

    29 августа 2014 г. 21:15