Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
1

Ускорить деление больших чисел

21.09.2015, 20:47. Показов 1697. Ответов 2
Метки нет (Все метки)

Всё бы ничего, да уж очень медленно.
По форуму смотрел, в Инете искал. Ничего аппетитного нетути.

Деление длинного на длинное.
Кликните здесь для просмотра всего текста

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
const BigInt BigInt::operator / (const BigInt &v) const {
 
    long long norm = BASE / (v.a.back() + 1);
 
    BigInt a = *this; a.sign = positive; a *= norm;
    BigInt b = v;     b.sign = positive; b *= norm;
 
    BigInt q, r;
    q.a.resize(a.a.size());
 
    for (long long i = a.a.size() - 1; i >= 0; i--) {
        r *= BASE;
        r += a.a[i];
        unsigned long long s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
        unsigned long long s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
        unsigned long long d = (BASE * s1 + s2) / b.a.back();
        r -= b * d;
        while (r < 0)
            r += b, --d;
        q.a[i] = d;
    }
 
    q.sign = sign * v.sign;
    q.trim();
    return q;
}


main:
Кликните здесь для просмотра всего текста

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
#include "BigInt.h"
 
int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "russian");
    //runTest(argc, argv);
 
    std::cout << " Проверка умножения и деления." << endl;
 
    string file_name = "Mp33.txt";
    std::cout << std::endl << " Загружаем число A из файла " << file_name << std::endl;
    
    double total_time = (double)clock() / CLOCKS_PER_SEC;
    BigInt A; A.Load(file_name);
    
    std::cout << " Ok." << std::endl;
    A.printInfo();
    std::cout << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl << std::endl;
    std::cout << endl;
 
    std::cout << " Умножение. B = A*A" << std::flush;
    total_time = (double)clock() / CLOCKS_PER_SEC;
    BigInt B = A * A;
    std::cout << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl << std::endl;
 
    std::cout << " Деление. C = B/A" << std::flush;
    total_time = (double)clock() / CLOCKS_PER_SEC;
 
    BigInt C = B / A;
    std::cout << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl;
 
    if (C == A) { std::cout << endl << " Результат Ok. C = A" << endl; }
    else { std::cout << endl << " Результаты не совпадают. C != A " << endl; }
}


Output:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
 Проверка умножения и деления.
 Загружаем число A из файла Mp33.txt
 Ok.
 big integer :  12 ... 500142591
 number of decimal digits = 258716
 number of segments       = 28747
 time : 0.019 sec.
 
 Умножение. B = A*A time : 0.244 sec.
 
 Деление. C = B/A time : 45.527 sec.
 
 Результат Ok. C = A
То что деление медленнее умножения, это понятно. Но не в 200 же раз!
Чёта тут не то.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.09.2015, 20:47
Ответы с готовыми решениями:

Деление больших чисел (нужно ускорить)
Ребятки, помогите ускорить. Уж очень медленно. Класс совсем простой(вектор со знаком): static...

Деление больших чисел
Здравствуйте, уважаемые форумчане. Необходимо разделить большое чило на большое число. Эти числа...

Деление больших чисел
Доброго времени суток. Спасите пожалуйста, как здесь быть:) Даны два числа. Ваша задача найти...

Класс больших чисел. Деление по Кнуту.
Кнут т2 стр. 300 алгоритм D. Кто реализовал для b=2^32 или 2^16 - поделитесь, плз, если не жалко !...

2
Заблокирован
21.09.2015, 21:14 2
Группа геноссе Burnikel-Ziegler-Verfahren вроде изобрели вундервафлю для длинного деления, которая есть
a new recursive method for division with remainder of integers. Its running time is 2K(n) + O(n log n) for division of a 2n-digit number by an n-digit number where K(n) is the Karatsuba multiplication time. It pays in practice for numbers with 860 bits or more. Then we show how we can lower this bound to 3/2K(n) + O(n log n) if we are not interested in the remainder.
1
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
22.09.2015, 10:46  [ТС] 3
IrineK, спасибо.
Оказывается, по методу Burnikel-Ziegler сделано деление в Яве (java.Math.BigInteger) и в GNU( http://gmplib.org/ ).
Реализацию на С++ пока не нашёл, но по крайней мере ясно, куда копать.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.09.2015, 10:46

Ускорить подсчёт суммы чисел
Всем, привет! Программа считает сумму чисел, вводимых с клавиатуры. Например: 1,2,3,4,5 или ...

Реализовать поиск совершенных чисел для больших чисел (Big Integer)
Всем привет! Задача заключается в поиске совершенных чисел. И тут возникла потребность в...

Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел больших 20
Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел...

Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел больших 20.
Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.