Этот код можно ускорить. Как?

Лень читать, что по ссылке. Нужен дискретный логарифм по модулю? Получай.

Нечто по ссылке зашифровано под 504.

http://i.piccy.info/i7/bedb41d2519091dddd45adf72d7a5e98/1-5-7353/11830918/Sny...

никаких лиспосрачей

C++

«Я три дня преследовала вас, чтобы сказать, как вы мне безразличны».

Гоноркод-то, курсеровый, читал?

1. Числа - по 155 цифр, их в тамошний повмод не засунешь. Тут нужна гмп.

2. valgrind показывает, что куча времени уходит на всякие вызовы функций гмп. Короче, я как-то коряво юзаю гмп, видимо, а заодно и плюсы, от этого все проблемы.

За алгоритм спасибо, но я уже решил задание) Мне нужно просто понять, где недочеты, кроме моей днк)

Да, я знаю, но раз срок вроде как практически вышел - это раз, до полного дедлайна еще очень далеко - два, а в-третьих, есть вариант запихнуть эту штуку под пароль в виде правильного ответа, но кто тогда будет туда добираться?

пофиксил оп-пост.

Оправдание ты себе нашёл конечно убийственное.

Во-первых ты запостил решение, во-вторых ты запостил условие, да еще и вообще не запариваясь на обфускации. По мне так ссаными тряпками тебя с курсера стоит прогнать.

Я поправил еще пост. Не знаю, теперь же вообще тред тупаком попахивает. Лучше бы ты помог, конечно, чем дисциплину наводил. Но я исправился.

Почему бы на форуме корсеры не спросить? В соседнем nlp всегда активно обсуждаются алгоритмы, помощи найти легко. К тому же недавно запилили новые подфорумы для разговоров (и для решений) по конкретным ПА.

Я там спрашивал, но те, кто пишет на си, в тех тредах только раз светятся, хвастаются впечатлящими цифрами и пропадают. Основную массу постов занимают сишарпщки и джависты с их 10-200 секунд и проблемами с BigInteger.

http://e-maxx.ru/algo/discrete_log
уже линкованное - если это тот алгоритм- то прочитай в нем - секцию улучшенная реализация

в первом цикле
зачем каждый раз вычислять inv ? он же неменяеться ?
pow равен старому pow * inc - и ненадо какждый раз его в степень возводить

Ты не смотри, что числа порядка 2**512. Там в подсказке недаром написано про диапазон чисел 0 .. 2**20. Решение валяется именно в этом диапазоне.

Я знаю, я его как бы нашел. 375 миллиардов с чем-то там. Оно в диапазоне от 0 до 2**40, а не 2**20. 2**20 - это мое разбиение, чтобы выразить искомое число как х1*2**20+х0, чтобы тратить не О(2**40), а О(2**20) времени. Если бы я не смотрел, я бы две недели считал в лучшем случае))

Ага, у меня inv вынесен на самом деле. А вот pow надо покрутить.

ох, там, видимо, уже все продумали до нас, и алгоритм возведения в степень по модулю таки лучше, чем умножение, а потом взятие по модулю. Потому что так только растет время. Ну, либо я все-таки еще хуже, чем думал раньше.

На SBCL работает 600 секунд на моем C2D. На тривиальных алгоритмах из ironclad, которые деревянные чуть менее чем полностью.

Надо будет запилить нормальную реализацию вычислений в GF. А то стыд и срам ёпт

fast exponent?

Я говорю, что люди просто брали с/++ и гмп и делали это за 2 секунды. А не пилили свои велосипеды.

посмотрел на псведокод... мне кажется в частности твоя проблема в «// using map». если это - std::map, то при большом количестве элементов производительность его деградирует жутким образом.

попробуй например google::dense_hash_map. о результатах доложи :) хэшфункцию возьми из буста. например.

потому что стд мап - не хэш таблица

Может, unordered map покатит? В этих твоих штуках можно сто лет ковыряться, и все равно говно сделаю.

Ну можно с unordered попробовать, но с dense_hash_map всё просто. http://goog-sparsehash.sourceforge.net/ Пакет для убунты/дебиана точно есть.

точнее вот: http://sparsehash.googlecode.com/svn/trunk/doc/dense_hash_map.html

С помощью CL и LispWorks PE. /thread

В общем, поигравшись... с моей кривой имплементацией выходит 14 секунд. Но есть потенциал для оптимизации, вечерком руки дойдут - попробую. Большой прирост дают, как правильно сказали (ну и как я предполагал своим «фаст экспонент»), более аккуратное возведение в степень - домножением.

удалось ли Вам ускорить код свыше 23 секунд?

не могли бы Вы рассказать подробнее про ускорение,

спустя год я уже ничего не помню.

У Вас не осталось кода случайно посмотреть модификации? Мой код по листингу вроде начинает что то делать,но видимо слишком долго расчитывает потому что вылетает с Fatal Error

удалось ли Вам ускорить код свыше 23 секунд?

Да, было что-то около 7, но этому треду же скоро год как, у меня и кода уже не осталось. Но там все достаточно просто.

Если я тебе дам свой код, сможешь подсказать в чем проблема? У меня аналогичное задание, только не с курсеры, а в универе. Алгоритм описанный на e-maxx только с длинными числами, дает удивительно медленное вычисление. Я описал класс-обертку для работы с mpir, чтобы можно было работать с ними также как с обычными числами. Алгоритма с e-maxx так и не дождался на 20 бит. Даже тупой перебор секунд за 20 справляется. А 40 бит ничего не берет

Разогнал 20 бит до 3 секунд. Но все равно