Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.56/18: Рейтинг темы: голосов - 18, средняя оценка - 4.56
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310

Увеличение скорости работы программы

16.02.2018, 21:37. Показов 3801. Ответов 29
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем привет ребят. Пишу программу для разложения числа(на определенные множители). Надо работать с большими числами используя библиотеку boost. Когда использую uint64_t, то программа очень быстро работает, как подключаю библиотеку boost в несколько раз медленнее работает. Подскажите, как оптимизировать код? Там числа будут не больше чем в 2^40, значит можно использовать uint64, но дальше кое-где приходиться делать умножение чисел по модулю, что при умножении выходит за этот диапозон. Подскажите, пожалуйста, как быть? Вот коды:
Без boost:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <random>
 
using namespace std;
 
mp::cpp_int powmod(mp::cpp_int a, mp::cpp_int b, mp::cpp_int m)
{
    mp::cpp_int res = 1;
 
    while (b > 0)
        if (b & 1)
        {
            res = (a % m * res) % m;
            --b;
        }
        else
        {
            a = (a % m * (a % m)) % m;
            b >>= 1;
        }
    return res;
}
 
void algorithm(int64_t a, int64_t b, int64_t p)
{
    random_device rd;
    mt19937 gen(rd());
 
    uniform_int_distribution<uint64_t> dis(1, p);
    vector<int64_t> vector1{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int64_t n = vector1.size();
    vector<vector<int64_t>> mas(n, vector<int64_t>(n, 0));
    int64_t r = 0;
    int64_t e = n - 1;
    int64_t s = 1;
 
    //выбор элемента, который еще не встречался
    for (int64_t i = 0; i < n; i++)
    {
        do
        {
            s = dis(gen);
            //возведение в степень по модулю
            r = powmod(a, s, p);
            while (e != -1)
            {
                if (r % vector1[e] == 0)
                {
                    r /= vector1[e];
                    mas[i][e]++;
                }
                else
                    e--;
            }
            if (r != 1)
                i--;
            e = n - 1;
        } while (r != 1);
    }
}
 
void main()
{
    algorithm(5, 43, 1073676287);
}
с boost:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <random>
 
using namespace std;
 
int64_t powmod(int64_t a, int64_t b, int64_t m)
{
    uint64_t res = 1;
 
    while (b > 0)
        if (b & 1)
        {
            res = (a % m * res) % m;
            --b;
        }
        else
        {
            a = (a % m * (a % m)) % m;
            b >>= 1;
        }
    return res;
}
 
void algorithm(int64_t a, int64_t b, int64_t p)
{
    random_device rd;
    mt19937 gen(rd());
 
    uniform_int_distribution<uint64_t> dis(1, p);
    vector<mp::cpp_int> vector1{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int64_t n = vector1.size();
    vector<vector<mp::cpp_int>> mas(n, vector<mp::cpp_int>(n, 0));
    mp::cpp_int r = 0;
    int64_t e = n - 1;
    mp::cpp_int s = 1;
 
    //выбор элемента, который еще не встречался
    for (int64_t i = 0; i < n; i++)
    {
        do
        {
            s = dis(gen);
            //возведение в степень по модулю
            r = powmod(a, s, p);
            while (e != -1)
            {
                if (r % vector1[e] == 0)
                {
                    r /= vector1[e];
                    mas[i][e]++;
                }
                else
                    e--;
            }
            if (r != 1)
                i--;
            e = n - 1;
        } while (r != 1);
    }
}
 
void main()
{
    algorithm(5, 43, 1073676287);
}
Вроде не особо много поменял, но работает гораздо медленнее.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.02.2018, 21:37
Ответы с готовыми решениями:

Измерение скорости работы блока программы
Как можно протестировать на скорость работы отдельный блок программы? Пример: замер скорости class_one.function1(). int main() {...

Увеличение скорости загрузки из файла obj мешей в Directx
Пробую написать свой класс для загрузки .obj мешей в Directx. Идея в 2 функциях: Первая(Convert_Obj) конвертирует стандартный формат...

Оценка скорости работы алгоритмов сортировки
Создайте массив из 10 000 элементов, заполните случайными значениями от 0 до 10 000. Измерьте время выполнения каждого алгоритма и...

29
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 минут
C++
1
2
3
4
5
6
7
// var1, var2, div - аргументы
constexpr int64_t base = 1<<20;
int64_t a1 = (var1%div)/base, b1 = (var1%div)%base;
int64_t a2 = (var2%div)/base, b2 = (var2%div)%base;
int64_t res = a1*a2%div;
res = (res*base + a1*b2 + a2*b1)%div;
res = (res*base + b1*b2)%div;
1
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
17.02.2018, 06:07
New man, подкоректировал свой предыдущий код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using int128_t = int64_t;
 
inline int64_t pm(const int64_t var1, const int64_t var2, const int64_t div)
{
    constexpr int64_t base = 1 << 20;
    int64_t a1 = (var1 % div) / base, b1 = (var1 % div) % base;
    int64_t a2 = (var2 % div) / base, b2 = (var2 % div) % base;
    int64_t res = a1 * a2 % div;
    res = (res * base + a1 * b2 + a2 * b1) % div;
    return (res * base + b1 * b2) % div;
}
 
int128_t powmod(int128_t a, uint64_t b, int128_t m)
{
    int128_t res = 1;
    a %= m;
 
    while (b)
        if (b & 1)
        {
            res = pm(a, res, m);
            --b;
        }
        else
        {
            a = pm(a, a, m);
            b >>= 1;
        }
    return res;
}
стало работать в 2 раза медленней чем с 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║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
17.02.2018, 12:21
Цитата Сообщение от New man Посмотреть сообщение
на stackoverflow нашёл, что g++ и clang поддерживают тип __int128.
Я и сам это видел.

Цитата Сообщение от New man Посмотреть сообщение
Результаты разбросаны в интервале от 0,72 до 0,28 секунд.
Странно, у меня проц вроде как слабый уже на наше время, но всё равно с 2ти попыток

C++
1
2
3
4
5
6
7
8
9
for (unsigned i = 0; i < 20; ++i)
{
    auto start = std::chrono::system_clock::now();
    algorithm(5, 43, 1073676287);
    auto end = std::chrono::system_clock::now();
 
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}
Разброс 0.18-0.57 сек. Но это с бустовым 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 при помощи получения произведения по остатку от миллиона интов.

Код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <array>
#include <random>
#include <chrono>
 
#include "boost/multiprecision/cpp_int.hpp"
 
using namespace std;
using int128_t = boost::multiprecision::int128_t;
 
inline int64_t pm1(const int64_t var1, const int64_t var2, const int64_t div)
{
    constexpr int64_t base = int64_t(1) << 20;
    constexpr int64_t threshold = int64_t(1) << 30;
    if (var1 <= threshold && var2 <= threshold)
    {
        return (var1*var2) % div;
    }
    else if (div <= threshold)
    {
        return (var1%div)*(var2%div) % div;
    }
    else
    {
        const int64_t a1 = (var1 % div) / base, b1 = (var1 % div) % base;
        const int64_t a2 = (var2 % div) / base, b2 = (var2 % div) % base;
        int64_t res = a1 * a2 % div;
        res = (res * base + a1 * b2 + a2 * b1) % div;
        return (res * base + b1 * b2) % div;
    }
}
 
// checks — numbers which pm is needed
int64_t time_test1(const int64_t div, const size_t checks, const int64_t* values) {
    int64_t res = values[0] % div;
    for (const int64_t* v = values + 1;v < values + checks; ++v)
    {
        res = pm1(*v, res, div);
    }
    return res;
}
 
 
// checks — numbers which pm is needed
int128_t time_test2(const int128_t div, const size_t checks, const int64_t* values) {
    int128_t res = values[0] % div;
    for (const int64_t* v = values + 1;v < values + checks; ++v)
    {
        res = (res**v) % div;
    }
    return res;
}
 
int main()
{
    std::random_device rd;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<int64_t> dis(int64_t(1) << 20, int64_t(1) << 40);
 
 
    constexpr size_t checks = 1000 * 1000;
    int64_t* values = new int64_t[checks];
    for (size_t i = 0; i < checks; ++i)
        values[i] = dis(gen);
    for (const int64_t div_pow : {10, 15, 20, 25, 30, 35, 40})
    {
        std::cout << "================================" << std::endl;
        const int64_t div = 1 << div_pow;
        auto start = std::chrono::system_clock::now();
        const auto first = time_test1(div, checks, values);
        auto end = std::chrono::system_clock::now();
        std::chrono::duration<double> first_time = end - start;
        start = std::chrono::system_clock::now();
        const auto second = time_test2(div, checks, values);
        end = std::chrono::system_clock::now();
        std::chrono::duration<double> second_time = end - start;
        std::cout << "Results: " << first << " " << second << std::endl;
        std::cout << "Time 1: " << first_time.count() << " Time2: " << second_time.count() << std::endl << std::endl;
    }
    return 0;
}


Результаты:
Кликните здесь для просмотра всего текста
================================
Results: 0 0
Time 1: 0.0386267 Time2: 0.0401346

================================
Results: 0 0
Time 1: 0.0390328 Time2: 0.0463342

================================
Results: 0 0
Time 1: 0.0363231 Time2: 0.046611

================================
Results: 0 0
Time 1: 0.0341942 Time2: 0.0584498

================================
Results: 0 0
Time 1: 0.0349017 Time2: 0.0431049

================================
Results: 0 0
Time 1: 0.0392408 Time2: 0.0424088

================================
Results: 0 0
Time 1: 0.037971 Time2: 0.0537009


Компилятор MS VC, Full Optimization -0x.

Результат работы профайлера во вложении.
Миниатюры
Увеличение скорости работы программы  
1
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
19.02.2018, 15:56
О, блин, я совсем забыл, что можно заоптимизировать деления с помощью сдвигов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
iinline int64_t pm1(const int64_t var1, const int64_t var2, const int64_t div)
{
    constexpr int64_t shift = 20;
    constexpr int64_t base = int64_t(1) << shift;
    constexpr uint64_t mask = base - 1 ;
    constexpr int64_t threshold = int64_t(1) << 30;
    if (var1 <= threshold && var2 <= threshold)
    {
        return (var1*var2) % div;
    }
    else if (div <= threshold)
    {
        return (var1%div)*(var2%div) % div;
    }
    else
    {
        const int64_t a1 = var1 >> shift, b1 = var1 & mask;
        const int64_t a2 = var2 >> shift, b2 = var2 & mask;
        int64_t res = (a1 * a2) % div;
        res = ((res << shift) + a1 * b2 + a2 * b1) % div;
        return ((res << shift) + b1 * b2) % div;
    }
}
Результат:
Кликните здесь для просмотра всего текста
================================
Results: 0 0
Time 1: 0.0357404 Time2: 0.0431497

================================
Results: 0 0
Time 1: 0.0369436 Time2: 0.0423462

================================
Results: 0 0
Time 1: 0.0343245 Time2: 0.0438995

================================
Results: 0 0
Time 1: 0.0346134 Time2: 0.0433195

================================
Results: 0 0
Time 1: 0.0396879 Time2: 0.0526786

================================
Results: 0 0
Time 1: 0.0388364 Time2: 0.0415213

================================
Results: 0 0
Time 1: 0.032143 Time2: 0.0399493
1
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
19.02.2018, 19:03
New man, New man, всё равно медленней буста (:
0
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
19.02.2018, 20:30  [ТС]
У меня как-то кстати одинаково по времени работает, что с mp::cpp_int, что с int128_t
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.02.2018, 20:30

Проверка скорости работы своего list
Можете написать какую нибудь проверку скорости работы list (без algorithm). Создал свой вариант, вроде работает и быстро, и не могли бы...

Оптимизация или увеличение скорости работы программы
Доброго времени суток, программисты! Буквально на днях столкнулся с проблемой, связанной с перегрузкой &quot;дельфина&quot; при...

Увеличение скорости работы программы (димнамически создаются PictureBox)
Написал маленькую программу где димнамически создаются PictureBox и вних заполняется определенная каритнка. При запуске заполнение...

Увеличение скорости работы бд
Хотелось бы узнать, какие есть методы по увеличению скорости работы бд? или хотя бы просто &quot;как&quot; лучше создавать архитектуру, для...

Увеличение скорости без остановки программы
В общем, есть программа, назовем ее &quot; Беговая дорожка&quot;. Она еще не доработана до конца, но у меня возникла дилемма с которой я все не могу...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru