Как работать с большими числами, не вмещающиеся в тип double

@Т_Ё_М_А · Регистрация: 14.12.2009

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Нужно найти x.

6^x mod 89548831 = 35152307

я решил сделать обычным перебором. Но числа огромные, и когда x доходит до 396, число становится слишком большим, чтобы вместиться в переменную типа double. Как можно решить эту проблему? Числа простые, поэтому использовать кратные им не выйдет.

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            double h;
            double hd;
            int p, g, x;
            p = 89548831;
            g = 6;
            x = 0;
            h = 0;
            hd = 0;
            
            if (h == 35152307)
            {
 
            }
            else
            {
                for (int i = 0; i <= 400; i++)
                {
                    x = i;
                    hd = Math.Pow(g, x);
                    h = ((hd) % p);
                    Console.WriteLine("{0}^{1}mod {2} = {3}     {4}", g, x, p, h, hd);
 
                }
            }
            Console.ReadLine();
 
        }
    }
}

@freeba · 20.01.2012, 00:26

Задача точно решается не перебором

Но если очень хочется:

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
 
namespace SampleBigInteger
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger x = 0;
            var stopwatch = System.Diagnostics.Stopwatch.StartNew();
            while (powmod(6, ++x) % 89548831 != 35152307)
            {
                if (x % 1000 == 0) Console.WriteLine("{0}, {1}, {2}", x, powmod(6, x) % 89548831, stopwatch.Elapsed);
            }
            Console.WriteLine("Element: {0}, time: {1}", x, stopwatch.Elapsed);
            stopwatch.Stop();
            Console.ReadKey();
        }
 
        static BigInteger powmod(BigInteger a, BigInteger k)
        {
            BigInteger b = 1;
 
            while (k != 0)
            {
                if (k % 2 == 0)
                {
                    k /= 2;
                    a *= a; 
                }
                else
                {
                    k--;
                    b *= a; 
                }
            }
            return b;
        }
    }
}

Добавлено через 3 минуты
По приколу дошел до х=40000. Не оно. Может в алгоритме ошибся?

@Т_Ё_М_А · 20.01.2012, 01:09 **[ТС]**

Сообщение от freeba

static BigInteger powmod(BigInteger a, BigInteger k)
* * * * {
* * * * * * BigInteger b = 1;
while (k != 0)
* * * * * * {
* * * * * * * * if (k % 2 == 0)
* * * * * * * * {
* * * * * * * * * * k /= 2;
* * * * * * * * * * a *= a;
* * * * * * * * }
* * * * * * * * else
* * * * * * * * {
* * * * * * * * * * k--;
* * * * * * * * * * b *= a;
* * * * * * * * }
* * * * * * }
* * * * * * return b;
* * * * }

freeba, можешь объяснить как это работает, я чёто не догоняю. А пространство имён
using System.Numerics только в Framework 4 да?

В алгоритме ошибки быть не должно.

Jupiter · 20.01.2012, 01:33

Сообщение от Т_Ё_М_А

using System.Numerics только в Framework 4 да?

именно

@freeba · 20.01.2012, 02:28

Сообщение от Т_Ё_М_А

можешь объяснить как это работает, я чёто не догоняю.

Это функция возведения в степень, неявно использующая двоичное представление (медленнее своих аналогов, но более понятная). Покури Кнута (только не увлекайся), помучай братца гугльберга. И снизойдет просветление на тебя.

Всю голову уже сломал над этой задачей. Спать пойду. Утро - вечера мудренее.

@ibmpc · 22.01.2012, 00:08

Сообщение от Т_Ё_М_А

Как работать с большими числами, не вмещающиеся в тип double

Создать свой числовой тип данных представляющих комплексные числа.
Экспоненциальная запись
Проще это числа вида 5,e+35 состоящие из двух частей.

Что нужно знать про арифметику с плавающей запятой

@Т_Ё_М_А · 22.01.2012, 00:43 **[ТС]**

freeba, спустя 30 часов дошло до 245 000 но ответа пока не найдено. Перепроверил все данные, алгоритм. Ошибки быть не должно. Буду ждать.

ibmpc, спасибо, почитаю.

@freeba · 22.01.2012, 01:34

Сообщение от Т_Ё_М_А

спустя 30 часов дошло до 245 000 но ответа пока не найдено.

Сурово. 6^245000 приличное число. Скоро начнет кончаться оперативка. Должен быть более православный способ.

Добавлено через 17 минут
Попробуй такой вариант. Только он основан на Double (если переписать на BigInteger возможно, подтвердиться ложность решения) и ответ содержит погрешность (полюбому). Но ответ - стольки значное число, что тут нужен не один год, для перебора влоб.

C#

var stopwatch = System.Diagnostics.Stopwatch.StartNew();
            double x = 0;
            double n = 1;
            
            while (true)
            {
                n *=2;
                x = Math.Exp((double)1 / 6 * Math.Log(n * 89548831 + 35152307, Math.E));
                Console.WriteLine("{0}, {1}, {2}", x, n, stopwatch.Elapsed);
                if (x % 1 == 0) break;
            }
            Console.WriteLine("Element: {0}, time: {1}", x, stopwatch.Elapsed);
            stopwatch.Stop();
            Console.ReadKey();

@Т_Ё_М_А 25 / 8 / 2 Регистрация: 14.12.2009 Сообщений: 281
	20.01.2012, 01:09 [ТС]	3
	Сообщение от freeba static BigInteger powmod(BigInteger a, BigInteger k) * * * * { * * * * * * BigInteger b = 1; while (k != 0) * * * * * * { * * * * * * * * if (k % 2 == 0) * * * * * * * * { * * * * * * * * * * k /= 2; * * * * * * * * * * a = a; * * * * * * * } * * * * * * * * else * * * * * * * * { * * * * * * * * * * k--; * * * * * * * * * * b = a; * * * * * * * } * * * * * * } * * * * * * return b; * * * * } freeba, можешь объяснить как это работает, я чёто не догоняю. А пространство имён using System.Numerics только в Framework 4 да? В алгоритме ошибки быть не должно. 0

Jupiter Каратель 6609 / 4028 / 401 Регистрация: 26.03.2010 Сообщений: 9,273 Записей в блоге: 1
	20.01.2012, 01:33	4
	Сообщение от Т_Ё_М_А using System.Numerics только в Framework 4 да? именно 1

@freeba Неадекват 1492 / 1230 / 246 Регистрация: 02.04.2010 Сообщений: 2,789
	20.01.2012, 02:28	5
	Сообщение от Т_Ё_М_А можешь объяснить как это работает, я чёто не догоняю. Это функция возведения в степень, неявно использующая двоичное представление (медленнее своих аналогов, но более понятная). Покури Кнута (только не увлекайся), помучай братца гугльберга. И снизойдет просветление на тебя. Всю голову уже сломал над этой задачей. Спать пойду. Утро - вечера мудренее. 1

@ibmpc 80 / 78 / 10 Регистрация: 29.12.2011 Сообщений: 183
	22.01.2012, 00:08	6
	Сообщение от Т_Ё_М_А Как работать с большими числами, не вмещающиеся в тип double Создать свой числовой тип данных представляющих комплексные числа. Экспоненциальная запись Проще это числа вида 5,e+35 состоящие из двух частей. Что нужно знать про арифметику с плавающей запятой 1

@Т_Ё_М_А 25 / 8 / 2 Регистрация: 14.12.2009 Сообщений: 281
	22.01.2012, 00:43 [ТС]	7
	freeba, спустя 30 часов дошло до 245 000 но ответа пока не найдено. Перепроверил все данные, алгоритм. Ошибки быть не должно. Буду ждать. ibmpc, спасибо, почитаю. 0

	22.01.2012, 01:34