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

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

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

Новые блоги и статьи Все статьи Все блоги /
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.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