Потестируйте скорость работы класса больших чисел

@SerVal · Регистрация: 16.04.2015

Студворк — интернет-сервис помощи студентам

Ребятки, сделал себе небольшой классик для больших чисел.
Типа того:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
static const long long BASE = 1000000000;
static const int BASE_DIGITS = 9;
 
enum sign { positive = 1, negative = -1 };
 
struct BigInt {
 
    std::vector<int> a;
    int sign;
 
    // constructors
    BigInt() : sign(positive) { } // default constructor
}

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

C++
1
2
3
4
5
6
7
8
>TestBigInt.exe -factorial 100000
--- factorial test ---
Calculating 100000!
 big integer :  2824 ... 0
 number of decimal digits = 456574
 number of segments       = 50731
 
time : 10.961 sec.

Это на Intel Quad Q9550 2,8 GHz
Если у кого есть результаты, приведите их пожалуйста.

*мне нравятся большие числа и женщины, но с числами интереснее.

@castaway · 23.08.2015, 23:32

Сообщение от zer0mail

Maple 2^77071069-1 считает и пишет меньше 2 секунд. Как они это делают?

Возможно как то предрасчитывают...

zer0mail · 23.08.2015, 23:46

Заменил 2 на 5, нажал "выполнить" и вот он - файл 5Мб (3 сек, не более).

@castaway · 23.08.2015, 23:52

Ну у них там не по любому один Core-i3 стоит...

@SerVal · 24.08.2015, 00:04 **[ТС]**

Сообщение от zer0mail

50 миллионов знаков числа пи: http://oldweb.cecm.sfu.ca/proj... ta/pi.html

Ну, у меня целые числа. Генерить из них число Pi я не умею. Надо какое-нибудь целое.

Добавлено через 4 минуты

Сообщение от zer0mail

Maple 2^77071069-1 считает и пишет меньше 2 секунд. Как они это делают?

А как узнать, все ли циферки у них правильные?

Тут вот тоже всё шустро.. http://www.wolframalpha.com/in... 77071069-1
... но приближённо.

@castaway · 24.08.2015, 00:06

Сообщение от SerVal

А как узнать, все ли циферки у них правильные?

Сравнить с другим источником, который гарантирует правильность.

zer0mail · 24.08.2015, 00:07

Сообщение от SerVal

Ну, у меня целые числа. Генерить из них число Pi я не умею. Надо какое-нибудь целое.

Это просто файл с циферками. Бери по 3 цифры (или по 5) - будут целые.

@SerVal · 24.08.2015, 00:48 **[ТС]**

Сообщение от zer0mail

Это просто файл с циферками. Бери по 3 цифры (или по 5) - будут целые.

Про файл понятно. Непонятно с чем его сравнивать, поскольку у меня число Pi не генерится.

Добавлено через 3 минуты
Вот, например, десятичные циферки числа Прота 6419*2^1351093+1
http://www.primegrid.com/prime... meid=97236

.. но его никак не зацапаешь.

zer0mail · 24.08.2015, 06:04

Maple сформировал на раз-два.

@Somebody · 24.08.2015, 15:40

Сообщение от zer0mail

Maple 2^77071069-1 считает и пишет меньше 2 секунд. Как они это делают?

В степень возводить много ума не надо. Тут всего log2(77071069) сложений с умножением длинного на короткое.

Добавлено через 1 минуту

Сообщение от SerVal

Вот, например, десятичные циферки числа Прота 6419*2^1351093+1
http://www.primegrid.com/prime... meid=97236
.. но его никак не зацапаешь.

В смысле "не зацапаешь"? Хочешь - в буфер копируй, хочешь - страницу сохраняй.

Добавлено через 5 минут
Насчёт двоичной системы: наверное, это на самом деле не лучше в данном случае. Перевод в десятичную дорого обходится. Вот если бы ещё много разных вычислений был с этим значением - тогда да...

Добавлено через 4 часа 22 минуты
Вот что у меня получилось умножением в двоичной системе с переводом в десятичную:

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
#include <cstdint>
#include <fstream>
#include <iterator>
#include <vector>
 
using namespace std;
 
int main()
{
    vector<uint32_t> fact;
    fact.reserve(2000000);
    fact.push_back(1);
    for (uint32_t i = 1; i <= 15000; i++)
    {
        uint32_t c = 0;
        for (uint32_t& d : fact)
            asm("mull %[i] \n\t"
                "addl %[c], %%eax \n\t"
                "adcl $0, %%edx \n\t"
                "movl %%edx, %[c] \n\t"
                : "+&a"(d), [c]"+r"(c)
                : [i]"r"(i)
                : "edx", "cc"
                );
        if (c != 0)
            fact.push_back(c);
    }
 
    vector<char> result;
    result.reserve(1000000);
    while (fact.size() != 0)
    {
        uint32_t c = 0;
        for (auto id = fact.rbegin(); id != fact.rend(); ++id)
        {
            asm("divl %[ten]"
                : "+a"(*id), "+d"(c)
                : [ten]"rm"(10)
                : "cc"
                );
        }
        if (fact.back() == 0)
            fact.pop_back();
        result.push_back(c + '0');
    }
 
    ofstream f("fact.txt", ios::out | ios::binary | ios::trunc);
    copy(result.crbegin(), result.crend(), ostreambuf_iterator<char>(f));
}

Работает намного медленнее, чем

Haskell
1
2
factorial :: Integer -> Integer
factorial x = product [1..x]

:-(

@SerVal · 24.08.2015, 22:36 **[ТС]**

Сообщение от Somebody

Работает намного медленнее, чем
Код Haskell ...
factorial :: Integer -> Integer
factorial x = product [1..x]

Что на самом деле выдаёт Haskell - дело тёмное.
Ни начальных, ни конечных циферок... Число цифр - тоже неизвестно.. "Не верю!" (с)

Добавлено через 10 минут
Haskell может сохранять большое число в файл?
Типа того:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "BigInt.h"
 
int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "russian");
 
    unsigned int number = 1000000;
    std::string file_name = "factorial." + to_string(number) + ".txt";
 
    std::cout << std::endl <<" Вычисляем факториал : " + to_string(number) << std::endl;
 
    double total_time = (double)clock() / CLOCKS_PER_SEC;
    
    BigInt myFactorial = BigInt::factorial(number);  // вычисляем
    myFactorial.printInfo();            // печатаем инфо.
    std::cout << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl << std::endl;
 
    std::cout << " сохраняем в файл " + file_name << endl;
    myFactorial.Save(file_name); // сохраняем в файл
    
    std::cout << " готово. "<< endl;
}

Output:

C++
1
2
3
4
5
6
7
8
 Вычисляем факториал : 1000000
 big integer :  8 ... 0
 number of decimal digits = 5565709
 number of segments       = 618413
 time : 111.539 sec.
 
 сохраняем в файл factorial.1000000.txt
 готово.

@nonedark2008 · 25.08.2015, 01:02

Сообщение от SerVal

Тем временем, прикрутил в operator * умножение Карацубой. Факториал ускорился ещё в 2 раза.
Чёта мало.. думал раза в 4 будет.

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

@SerVal · 25.08.2015, 03:50 **[ТС]**

Сообщение от zer0mail

Maple сформировал на раз-два.
Вложения arhiv.rar (187.9 Кб, 0 просмотров)

Спасибо. Попробовал посмотреть, что сформировал Maple. ( число Прота 6419 * 2 ^ 1351093 + 1)
int main()

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "russian");
    
    std::cout << endl <<"  Создаём число Прота = 6419 * 2 ^ 1351093 + 1"<< endl <<endl;
 
    double total_time = (double)clock() / CLOCKS_PER_SEC;
    BigInt protNumber = BigInt::pow2(1351093) * 6419 + 1;
    protNumber.printInfo();
    std::cout << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl << std::endl;
 
 
    std::cout << " Загружаем число ttt из файла ttt.txt" << endl;
    BigInt ttt; ttt.Load("ttt.txt");
    ttt.printInfo();
 
    if (ttt != protNumber)
        std::cout << " Ошибка. ttt != protNumber" << endl;
    else
        std::cout << " Ok. ttt == protNumber" << endl;
}

Output:

C++
1
2
3
4
5
6
7
8
9
10
 Создаём число Прота = 6419 * 2 ^ 1351093 + 1
 
 big integer :  21251 ... 889230849
 number of decimal digits = 406724
 number of segments       = 45192
 time : 3.515 sec.
 
 Загружаем число ttt из файла ttt.txt
 error parse string!
 last int : -38

Чёта тут не то..

... похоже, Maple туда не только цифры сохраняет.
Ну, может я криво строку разбираю? (функция разбора строки изысками не страдает).
Parse(const std::string& s):

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

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
    // parse string. decimal digits 0...9. possible delimiters: '\r', '\n, ',' and '.'
    void Parse(const std::string& s){
        a.clear(); sign = 1;
        
        int p = 0;
        if (s[p] == '-') { ++p; sign = -1; }
        else if (s[p] == '+') { ++p; }
        
        for (long long i = s.size() - 1, v = BASE; i >= p; --i, v *= 10) {
            if ((s[i] - '0' == '\r') ||
                (s[i] - '0' == '\n') ||
                (s[i] - '0' == ',')  ||
                (s[i] - '0' == '.'
                ))  continue; // skip '\r', '\n, ',' and '.' 
 
            int x = s[i] - '0';
            if (x < 0 || 9 < x) {
                std::cerr << " error parse string!" << std::endl;
                std::cerr << " last int : " << x << std::endl;
                exit(1);
            }
            if (v == BASE) {
                v = 1;
                a.push_back(x);
            }
            else a.back() += (x)*v;
        }
        trim();
    }

@Somebody · 25.08.2015, 09:13

Сообщение от SerVal

Haskell может сохранять большое число в файл?

Haskell
1
2
3
4
5
6
7
8
9
10
import System.IO
 
factorial :: Integer -> Integer
factorial x = product [1..x]
 
main :: IO ()
main = do
  h <- openFile "fact.txt" WriteMode
  hPrint h $ factorial 15000
  hClose h

zer0mail · 25.08.2015, 09:41

Сообщение от SerVal

Чёта тут не то.. ... похоже, Maple туда не только цифры сохраняет.

Там в конце файла добавлена пустая строка, ее можно удалить редактором.

@golatin · 25.08.2015, 09:59

А почему не пойти нормальным путем? Создать таблицу факториалов скажем с шагом 100 и работать уже непосредственно с ней, что позволит избежать кучи лишних вычислений. Или значения синуса вы тоже рядом Тейлора вычисляете?

zer0mail · 25.08.2015, 11:28

Сообщение от golatin

А почему не пойти нормальным путем?

Предлагаю почитать название темы, поразмышлять над вопросом "Зачем создана тема, чего хочет ТС?". Может, тогда вопрос "А почему..?" сам собой отпадет...

@SerVal · 25.08.2015, 12:08 **[ТС]**

Сообщение от golatin

А почему не пойти нормальным путем? Создать таблицу факториалов скажем с шагом 100 и работать уже непосредственно с ней, что позволит избежать кучи лишних вычислений. Или значения синуса вы тоже рядом Тейлора вычисляете?

golatin, что-то Вашу идею я не совсем понял.

Почему с шагом 100? И до какого числа создавать таблицу факториалов?
А самое главное - где их хранить? Факториал 1млн, например, занимает на диске ~5,3 мегабайта.

Сообщение от golatin

Или значения синуса вы тоже рядом Тейлора вычисляете?

Скорее всего, он так и вычисляется(процессором).

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

*****
Поскольку скоростью работы библиотека не блещет, решил посмотреть - не поможет ли чем видеоадаптер?
Для начала - сложение. Результат пока не радует

C++
1
2
3
4
5
6
7
8
9
Accelerator: AMD Radeon HD 6800 Series
 
Сложение ЦПУ.
 time : 141.652 sec.
 
Сложение ГПУ.
 time : 296.766 sec.
 
Результаты совпадают.

Мда.. что-то Radeon какой-то не шустрый.

@golatin · 25.08.2015, 15:12

Сообщение от SerVal

Скорее всего, он так и вычисляется(процессором).
Поскольку синус функция периодическая, то передавать ему в качестве аргумента значение большее 2PI
- никакого смысла.
Синусу надо передавать остаток от деления на 2PI.

IMHO - вы ошибаетесь.
Когда-то писал для микроконтроллера генерацию ШИМ с целью выпрямления тока частотою 50 Гц.(Здесь 0x7FFF - единица)

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SINTAB: .db #0x0000,#0x0202,#0x0405,#0x0607,#0x0809,#0x0A0A,#0x0C0B,#0x0E0B,#0x100A,#0x1209,#0x1406
        .db #0x1601,#0x17FC,#0x19F4,#0x1BEC,#0x1DE1,#0x1FD5,#0x21C6,#0x23B5,#0x25A3,#0x278D,#0x2976
        .db #0x2B5B,#0x2D3E,#0x2F1E,#0x30FB,#0x32D5,#0x34AC,#0x367F,#0x384F,#0x3A1C,#0x3BE5,#0x3DAA
        .db #0x3F6B,#0x4128,#0x42E1,#0x4495,#0x4646,#0x47F2,#0x4999,#0x4B3C,#0x4CDA,#0x4E73,#0x5007
        .db #0x5197,#0x5321,#0x54A5,#0x5625,#0x579F,#0x5913,#0x5A82,#0x5BEB,#0x5D4E,#0x5EAC,#0x6003
        .db #0x6154,#0x62A0,#0x63E5,#0x6523,#0x665C,#0x678D,#0x68BD,#0x69DD,#0x6AFB,#0x6C12,#0x6D23
        .db #0x6E2C,#0x6F2F,#0x702A,#0x711F,#0x720C,#0x72F2,#0x73D1,#0x74A8,#0x7578,#0x7641,#0x7702
        .db #0x77BC,#0x786E,#0x7919,#0x79BC,#0x7A57,#0x7AEA,#0x7B76,#0x7BFA,#0x7C76,#0x7CEA,#0x7D57
        .db #0x7DBB,#0x7E18,#0x7E6C,#0x7EB9,#0x7EFD,#0x7F3A,#0x7F6E,#0x7F9A,#0x7FBF,#0x7FDB,#0x7FEF
        .db #0x7FFB,#0x7FFF,#0x7FFB,#0x7FEF,#0x7FDB,#0x7FBF,#0x7F9A,#0x7F6E,#0x7F3A,#0x7EFD,#0x7EB9
        .db #0x7E6C,#0x7E18,#0x7DBB,#0x7D57,#0x7CEA,#0x7C76,#0x7BFA,#0x7B76,#0x7AEA,#0x7A57,#0x79BC
        .db #0x7919,#0x786E,#0x77BC,#0x7702,#0x7641,#0x7578,#0x74A8,#0x73D1,#0x72F2,#0x720C,#0x711F
        .db #0x702A,#0x6F2F,#0x6E2C,#0x6D23,#0x6C12,#0x6AFB,#0x69DD,#0x68BD,#0x678D,#0x665C,#0x6523
        .db #0x63E5,#0x62A0,#0x6154,#0x6003,#0x5EAC,#0x5D4E,#0x5BEB,#0x5A82,#0x5913,#0x579F,#0x5625
        .db #0x54A5,#0x5321,#0x5197,#0x5007,#0x4E73,#0x4CDA,#0x4B3C,#0x4999,#0x47F2,#0x4646,#0x4495
        .db #0x42E1,#0x4128,#0x3F6B,#0x3DAA,#0x3BE5,#0x3A1C,#0x384F,#0x367F,#0x34AC,#0x32D5,#0x30FB
        .db #0x2F1E,#0x2D3E,#0x2B5B,#0x2976,#0x278D,#0x25A3,#0x23B5,#0x21C6,#0x1FD5,#0x1DE1,#0x1BEC
        .db #0x19F4,#0x17FC,#0x1601,#0x1406,#0x1209,#0x100A,#0x0E0B,#0x0C0B,#0x0A0A,#0x0809,#0x0607
        .db #0x0405,#0x0202,#0x0000

Подобного типа таблицы прилагаются к любому мат-пакету. Зачем напрягать процессор ненужными вычислениями, когда все уже подсчитано до нас..

@_Ivana · 25.08.2015, 15:18

golatin, спасибо, смешно

Даже смешнее упоминаемой тут формулы Стирлинга

zer0mail · 25.08.2015, 16:10

Сообщение от SerVal

что-то Radeon какой-то не шустрый.

А можно глянуть на код для радеона?

Новые блоги и статьи Все статьи Все блоги /
сукцессия 30. Фосфорный и азотный замки по "честному" закону лимитирования Либиха anaschu 16.07.2026 Основные достижения за последние дни 1. Механизм отложенного высвобождения фосфора Добавлен специальный пул для медленного разложения меланизированных гиф ЕСМ Реализована разная скорость. . .	Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .	Как надо было делать правильно - вообще не слушать ИИ, его дело - текст. Hrethgir 15.07.2026 А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её. Всё это стресс конечно. Почему?. . .	Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет
Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .	сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	23.08.2015, 23:46
	Заменил 2 на 5, нажал "выполнить" и вот он - файл 5Мб (3 сек, не более). 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	23.08.2015, 23:52
	Ну у них там не по любому один Core-i3 стоит... 0

@golatin 317 / 268 / 61 Регистрация: 12.10.2011 Сообщений: 434
	25.08.2015, 09:59
	А почему не пойти нормальным путем? Создать таблицу факториалов скажем с шагом 100 и работать уже непосредственно с ней, что позволит избежать кучи лишних вычислений. Или значения синуса вы тоже рядом Тейлора вычисляете? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	25.08.2015, 15:18
	golatin, спасибо, смешно Даже смешнее упоминаемой тут формулы Стирлинга 0