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

@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 какой-то не шустрый.

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

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .
Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .

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