Оптимизировать программу на C#, который создает 2 словари и поиск подходящего значения


У меня есть 2 словаря. Я пытаюсь оптимизировать этот код, чтобы запустить как можно быстрее.

Это для решения хвостовики шажок гигантский шаг алгоритма
Алгоритм:

Given b = a^x (mod p)
First choose n, such that n^2 >= p-1
Then create 2 lists:
    1. a^j (mod p) for 0 <= j < n
    2. b*(a(inverse)^n)^k for 0 <= k < n
Finally look for a match between the 2 lists.


public static BigInteger modInverse(BigInteger a, BigInteger n)
{
    BigInteger i = n, v = 0, d = 1;
    while (a > 0)
    {
        BigInteger t = i / a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t * x;
        v = x;
    }
    v %= n;
    if (v < 0) v = (v + n) % n;
    return v;
}

static int Main()
{
    BigInteger r = 92327518017225,
               rg,
               temp,
               two=2,
               tm, 
               n = ((BigInteger)Math.Sqrt(247457076132467-1))+1, 
               mod = 247457076132467;
    Dictionary<int, BigInteger> b = new Dictionary<int, BigInteger>();
    Dictionary<int, BigInteger> g = new Dictionary<int, BigInteger>();
    temp = modInverse(two, mod);
    temp = BigInteger.ModPow(temp, n, mod);
    for (int j = 0; (BigInteger)j < n; j++)
    {
        rg = r * BigInteger.ModPow(temp, j, mod);
        g.Add(j, rg);
    }
    for (int i = 0; (BigInteger)i < n ; i++)
    {
        tm = BigInteger.ModPow(2, i, mod);
        foreach (KeyValuePair<int, BigInteger> d in g)
        {
            if (d.Value.Equals(tm))
            {
                Console.WriteLine("j={0}   B*t^j(mod m) = {1}",d.Key,d.Value);
                Console.WriteLine("a^"+i+" = "+tm);
            }
        }
        b.Add(i,tm);
    }
    Console.ReadKey();
    return 0;
}


374
3
c#
задан 21 сентября 2011 в 08:09 Источник Поделиться
Комментарии
2 ответа

Один из способов вы можете улучшить скорость поиска:


  • Для одного из двух словарей, строить массив значений. Отсортировать этот массив.

  • Чтобы выполнить поиск:

  • > Пройти последовательно через значения других словарь.

  • > Для каждого значения, проанализировать массив.Ищет() для значения в отсортированном массиве, чтобы увидеть, если есть совпадение.

Благодаря бинарным поиском, этот метод позволит снизить вниз до o(n журнал N) вместо ваш текущий метод грубой силы, который является o(Н2)

1
ответ дан 22 сентября 2011 в 12:09 Источник Поделиться

Есть несколько очевидных оптимизаций.


  1. Удалить весь код, относящийся к Б. Словарь вам только вставить в это пустая трата времени, памяти, программиста и способность понимать, что происходит.

  2. Использовать г в качестве словаря. Способ сделать это, чтобы изменить его из словаря в словарь. Тогда ваш цикл foreach может быть заменена простой TryGetValue.

  3. Угробить литой Дж к типа BigInteger:

    int n_int = ((int)Math.Sqrt(247457076132467-1))+1;
    ...
    n = (BigInteger)n_int

    И сравнивать Дж в n_int. Если он не поместится в int, Джей не должен быть int или.


  4. Использовать основные арифметические свойства в циклах. Е. Г. а не

    tm = BigInteger.ModPow(2, i, mod);

    вы должны иметь

    tm = 1,
    ...
    for (int i = 0; i < n_int; i++)
    {
    ...
    tm = (tm * 2) % mod;
    }

P. S. На самом деле, если бы ты посмотрел в Википедии страница на алгоритм, вы бы нашли псевдокод, который обрабатывает все это уже было.

1
ответ дан 22 сентября 2011 в 09:09 Источник Поделиться