|
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
|
|||||||||||
Увеличение скорости работы программы16.02.2018, 21:37. Показов 3801. Ответов 29
Метки нет (Все метки)
Всем привет ребят. Пишу программу для разложения числа(на определенные множители). Надо работать с большими числами используя библиотеку boost. Когда использую uint64_t, то программа очень быстро работает, как подключаю библиотеку boost в несколько раз медленнее работает. Подскажите, как оптимизировать код? Там числа будут не больше чем в 2^40, значит можно использовать uint64, но дальше кое-где приходиться делать умножение чисел по модулю, что при умножении выходит за этот диапозон. Подскажите, пожалуйста, как быть? Вот коды:
Без boost:
0
|
|||||||||||
| 16.02.2018, 21:37 | |
|
Ответы с готовыми решениями:
29
Измерение скорости работы блока программы Увеличение скорости загрузки из файла obj мешей в Directx Оценка скорости работы алгоритмов сортировки |
|
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
|
||||||
| 17.02.2018, 01:41 | ||||||
|
Можно попроще решить.
Пусть k = 2^20; Тогда число можно представить как a*k + b; a,b принадлежат [0..k] по условию. v1, v2 - выражения, от произведения которых надо получить остаток. d - делитель. Выразим их как: a1*k+b1 = v1%d; a2*k+b2 = v2%d; Тогда произведение чисел: (a1,b1)*(a2,b2) = a1*a2*k*k + (a1*b2+a2*b1)*k+b1*b2 Теперь надо взять остаток по d в три шага. m1 = (a1*a2)%d; m2 = (m1*k+a1*b2+a2*b1)%d; // вроде выражение в скобках не должно быть больше 2^40 m3 = (m2*k+b1*b2)%d; // итоговый остаток. Вроде должно быть правильно, но я не уверен. Добавлено через 2 минуты И можно обойтись 64 битами. Добавлено через 4 минуты По сути, мы закодируем длинное число по основанию 2^20 и с двумя цифрами. Добавлено через 8 минут
1
|
||||||
|
║XLR8║
|
||||||
| 17.02.2018, 06:07 | ||||||
|
New man, подкоректировал свой предыдущий код
int128_t из буста
1
|
||||||
|
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
|
|
| 17.02.2018, 11:21 | |
|
outoftime, я тут на stackoverflow нашёл, что g++ и clang поддерживают тип
__int128. Проверь и его.https://stackoverflow.com/ques... teger-in-c Добавлено через 29 минут Кстати, позапускал я твой код со своей версией пару раз. Результаты разбросаны в интервале от 0,72 до 0,28 секунд.
0
|
|
|
║XLR8║
|
||||||||
| 17.02.2018, 12:21 | ||||||||
int128_t с gcc в моих сорсах нету многих перегрузок, он просто как std::array<__int128, 11ul>::value_type определенДобавлено через 12 минут Не по теме: New man, зацени у меня репутация 666 НЕ ЛАЙКАЙТЕ МЕНЯ! (:
0
|
||||||||
|
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
|
|
| 17.02.2018, 13:13 [ТС] | |
|
Спасибо большое ребята) вы классные)
0
|
|
| 17.02.2018, 13:36 | |
|
0
|
|
|
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
|
|||||||
| 19.02.2018, 14:34 | |||||||
|
outoftime, таки протестировал свой метод с некоторыми оптимизациями в сравнении с boost при помощи получения произведения по остатку от миллиона интов.
Код: Кликните здесь для просмотра всего текста
Результаты: Кликните здесь для просмотра всего текста
Компилятор MS VC, Full Optimization -0x. Результат работы профайлера во вложении.
1
|
|||||||
|
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
|
|||||||
| 19.02.2018, 15:56 | |||||||
|
О, блин, я совсем забыл, что можно заоптимизировать деления с помощью сдвигов.
Кликните здесь для просмотра всего текста
1
|
|||||||
|
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
|
|
| 19.02.2018, 20:30 [ТС] | |
|
У меня как-то кстати одинаково по времени работает, что с mp::cpp_int, что с int128_t
0
|
|
| 19.02.2018, 20:30 | |
|
Проверка скорости работы своего list Оптимизация или увеличение скорости работы программы Увеличение скорости работы программы (димнамически создаются PictureBox) Увеличение скорости работы бд Увеличение скорости без остановки программы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|