none
Работа с большими числами. RRS feed

  • Вопрос

  • Здравствуйте.Имеется три восьмизначных числа a,b,c.Как высчитать выражение (a^b)mod(b) на c#  с использованием System.Numerics или каким нибудь другим способом.

     

    • Перемещено Siddharth Chavan 1 октября 2010 г. 21:23 MSDN Forums Consolidation (От:Visual C#)
    26 июня 2010 г. 19:47

Ответы

  • Если числа 8 значные тогда сами числа можно представлять в Int32 или Int64, а результат в BigInteger:

     

    static void Main(string[] args)
        {
          long a = 46872344, b = 12111111, c = 54723324;
          BigInteger res = BigInteger.Pow(a,(int)b)%c;
         
          Console.WriteLine("(a^b) mod c: {0}",res);
          Console.ReadKey();
          
        }

     Вообще, мне кажется, вычисление в такую степень займет много времени. Поэтому придется использовать алгоритмы типа бинарного, это самый простой, легко реализовать, или Монтгомери.

     

    • Предложено в качестве ответа OlegGel 27 июня 2010 г. 9:44
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    26 июня 2010 г. 21:07
  • Примерно так:

    Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
     
      Bignum result = 1;
     
      while (exponent > 0) {
        if (exponent & 1) {
          
          result = (result * base) % modulus;
        }
        
        exponent >>= 1;
        base = (base * base) % modulus;
      }
     
      return result;
    }

    BigNum представляет класс для работы с большими числами, замени на свой и все.

    • Предложено в качестве ответа sharok 27 июня 2010 г. 13:48
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    27 июня 2010 г. 13:48
  • Если есть  возможность использовать .NET 4.0, то там есть структура для работы с большими числами, System.Numerics.BigInteger. Если 4 версии нету, то можно использовать сторонние разработки, например IntX (http://intx.codeplex.com) или использовать Solver Foundation(http://code.msdn.microsoft.com/solverfoundation), вроде, на нем основан стандартный BigInteger в .NET 4.0. 
    • Предложено в качестве ответа OlegGel 27 июня 2010 г. 9:44
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    26 июня 2010 г. 20:26

Все ответы

  • Если есть  возможность использовать .NET 4.0, то там есть структура для работы с большими числами, System.Numerics.BigInteger. Если 4 версии нету, то можно использовать сторонние разработки, например IntX (http://intx.codeplex.com) или использовать Solver Foundation(http://code.msdn.microsoft.com/solverfoundation), вроде, на нем основан стандартный BigInteger в .NET 4.0. 
    • Предложено в качестве ответа OlegGel 27 июня 2010 г. 9:44
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    26 июня 2010 г. 20:26
  • System.Numerics.BigInteger есть,как именно реализовать задачу,никак что то не получается.
    26 июня 2010 г. 20:31
  • Если числа 8 значные тогда сами числа можно представлять в Int32 или Int64, а результат в BigInteger:

     

    static void Main(string[] args)
        {
          long a = 46872344, b = 12111111, c = 54723324;
          BigInteger res = BigInteger.Pow(a,(int)b)%c;
         
          Console.WriteLine("(a^b) mod c: {0}",res);
          Console.ReadKey();
          
        }

     Вообще, мне кажется, вычисление в такую степень займет много времени. Поэтому придется использовать алгоритмы типа бинарного, это самый простой, легко реализовать, или Монтгомери.

     

    • Предложено в качестве ответа OlegGel 27 июня 2010 г. 9:44
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    26 июня 2010 г. 21:07
  • Спасибо.
    26 июня 2010 г. 21:16
  • а исходников этих алгоритмов у вас случайно нет?
    27 июня 2010 г. 6:45
  • Вам же сказали про кодплекс, это opensource заведение, исходники там есть, наприм ер для BigInteger

    http://biginteger.codeplex.com/SourceControl/list/changesets

    27 июня 2010 г. 9:59
  • Примерно так:

    Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
     
      Bignum result = 1;
     
      while (exponent > 0) {
        if (exponent & 1) {
          
          result = (result * base) % modulus;
        }
        
        exponent >>= 1;
        base = (base * base) % modulus;
      }
     
      return result;
    }

    BigNum представляет класс для работы с большими числами, замени на свой и все.

    • Предложено в качестве ответа sharok 27 июня 2010 г. 13:48
    • Помечено в качестве ответа I.Vorontsov 29 июня 2010 г. 5:47
    27 июня 2010 г. 13:48
  •  Не могли бы вы  целиком исходник показать,а то что то не получается.
    27 июня 2010 г. 20:50
  • using System;
    using System.Numerics;
    
    namespace Mod
    {
     class Program
     {
     public static bool LastBit(BigInteger number)
     {
      BigInteger BinaryHolder;
      BinaryHolder = number % 2;
      
      if (BinaryHolder ==1)
      return true;
      return false;
     }
     private static BigInteger ModPow(BigInteger number, BigInteger exponent, BigInteger modulus)
     {
      BigInteger result = 1;
      while (exponent > 0)
      {
      if (LastBit(exponent))
      {
    
       result = (result * number) % modulus;
      }
    
      exponent >>= 1;
      number = (number * number) % modulus;
      }
    
      return result;
     }
    
     static void Main(string[] args)
     {
      BigInteger res = ModPow(4, 13, 497);
      Console.WriteLine("(a^b) mod c: {0}",res);
      Console.ReadKey();
      
     }
     }
    }
    
    28 июня 2010 г. 18:47
  • Огромное спасибо.
    28 июня 2010 г. 19:28