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

@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
Если у кого есть результаты, приведите их пожалуйста.

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

@SerVal · 20.08.2015, 05:55 **[ТС]**

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

Если хочется самому писать велосипеды ради интереса, а не взять готовое отлаженное решение..

Дык, где оно "готовое отлаженное решение"? Нетути.

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

то могу посоветовать прикрутить умножение через БПФ(Быстрое преобразование Фурье).

Это да. Но прикручивать БПФ на CPU - неинтересно. Его можно получить библиотечной функцией от видеоадаптера. Но на входе нужен вектор. Библиотек с вектором я не нашёл. Вот и приходится изобретать велосипед.

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

Ассемблерные вставочки можно.

Визуал Студио ассемблерные вставочки больше не даёт.

Пока пробую прикрутить в качестве оператора * Карацубу, чтобы маленько побыстрее было, а главное - чтобы память поменьше отъедало. Результат пока не радует. Примеры Карацуба-умножений в Инете - сплошная косятина.

Ilot · 20.08.2015, 07:45

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

Да... Питон и Мапл впечатляют.. жаль, что из них в С++ ничего не зацапаешь.

Откройте для себя формулу Стирлинга.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?n! = \sqrt{2\pi n}{\left(\frac{n}{e} \right)}^{n}\left( 1 + \frac{1}{12n} + \frac{1}{288{n}^{2}} + ... \right)$
Факториал считается практически мнгновенно. Не удивлюсь если мат пакеты используют это или альтернативное асимптотическое разложение...

zer0mail · 20.08.2015, 08:55

Асимптотическое разложение 400тыс точных знаков не даст.

@mymedia · 20.08.2015, 09:07

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

Дык, где оно "готовое отлаженное решение"? Нетути

Да, как же нет? Вот тут уже приводили питон с его длинной арифметикой (мне он очень нарвится). У питона есть сишный интерфейс через заголовок <libpython>. При желании можно прикрутить к нему плюсовый класс BigInt — не проблема.

Ilot · 20.08.2015, 09:19

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

Асимптотическое разложение 400тыс точных знаков не даст.

Даст. На то оно и асимптотическое разложение.

@SerVal · 20.08.2015, 10:24 **[ТС]**

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

Да, как же нет? Вот тут уже приводили питон с его длинной арифметикой (мне он очень нарвится). У питона есть сишный интерфейс через заголовок <libpython>. При желании можно прикрутить к нему плюсовый класс BigInt — не проблема.

Что-то я не понял про Питона. То есть, из моей С++ программы можно передавать Питону векторы, как большие числа ? И, соответственно, получать от него векторы, как результаты сложений, умножений..?

Добавлено через 11 минут
Маленько улучшил факториал. В два раза.

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 : 5.117 sec.

Ежели удастся прикрутить Карацубу, в качестве CPU умножения - этого будет достаточно.
После чего, попробую перенести часть функций на видеоадаптер. Надеюсь, с длинными числами он пошустрее будет.

@mymedia · 20.08.2015, 10:29

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

Что-то я не понял про Питона. То есть, из моей С++ программы можно передавать Питону векторы, как большие числа ? И, соответственно, получать от него векторы, как результаты сложений, умножений..?

Ну, так, конечно, можно сделать. Лучше всего с помощью boost.python. Но я имел ввиду другое: в питоне уже реализовна длинная арифметика можно было бы использовать её.
А если серьёзно, то при лёгком гуглинге обнаруживатеся такая вещь как NTL. Выглядит очень даже ничего

zer0mail · 21.08.2015, 09:08

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

Даст. На то оно и асимптотическое разложение.

Только времени на получение этих 400тыс знаков понадобится больше, чем просто посчитать через длинную арифметику.

Добавлено через 16 часов 24 минуты
Вставил ассемблерный кусок, выжал по-максимуму. Все равно уступает ТС в разы.

Оказывается, ТС компилировал в 64битном режиме, а я в 32битном.

И хотя для расчета частного/остатка у меня используется одна операция div(85% времени занимает), получается что 64битные регистры эффективней.

@SerVal · 21.08.2015, 18:03 **[ТС]**

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

.. компилировал в 64битном режиме, а я в 32битном.

Ну да, это ж для больших чисел.

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

Чёта мало.. думал раза в 4 будет. Наверное, надо обратить внимание на деление:
сейчас методом Ньютона-Рафсона делятся только большие числа. А деление большого на маленькое - "в столбик".

На моём зачуханом кваде:

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 : 2.11 sec.

Новый экзешник прикрепил. Желающие могут проверить.
Ах да, факториал 100 тыс. - ужо не актуален. Выкладываем наши достижения для 1 миллион факториал!

@castaway · 22.08.2015, 22:48

GMP+MPFR считают факториал миллиона за 37 сотых секунды.

zer0mail · 22.08.2015, 22:53

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

GMP+MPFR считают факториал миллиона за 37 сотых секунды

Их можно прикрутить к Visual Studio 2010 ?

@castaway · 22.08.2015, 23:02

Поправка: 37 сотых с указанной точностью 100 знаков. Это не совсем верное измерение.

zer0mail, думаю что можно, но я не пробовал.

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

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

Выкладываем наши достижения для 1 миллион факториал!

А ваш класс за какое время считает факториал от миллиона? Сколько цифр у этого числа? Мне мой симбиоз выдал 5 с лишним миллионов.

@Somebody · 22.08.2015, 23:02

Так как вычислений много, а вывод в десятичной системе один, считать надо в двоичной, чтобы не было делений на каждой итерации.

@castaway · 22.08.2015, 23:11

zer0mail, в этой теме ТС как-то прикрутил. Можешь спросить у него.

Добавлено через 6 минут
Установил точность в миллион знаков. Время вычисления 227.262 секунд.

@SerVal · 23.08.2015, 02:00 **[ТС]**

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

А ваш класс за какое время считает факториал от миллиона? Сколько цифр у этого числа? Мне мой симбиоз выдал 5 с лишним миллионов.

Пока вот так:

C++
1
2
3
4
5
6
7
8
TestBigInt.exe -factorial 1000000
-- factorial test --
Calculating 1000000!
 big integer :  8 ... 0
 number of decimal digits = 5565709
 number of segments       = 618413
 
time : 109.367 sec.

*обновлённый экзешник приложил.

@SerVal · 23.08.2015, 02:29 **[ТС]**

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

Так как вычислений много, а вывод в десятичной системе один, считать надо в двоичной, чтобы не было делений на каждой итерации.

Факториал 1 миллиона в двоичной системе это 5565709*4 двоичных циферок.
А так как минимальное хранилище это байт, это будет ~21 Мегабайт вместо 5.
В общем, много-премного и с памятью будет совсем бяда..

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

GMP+MPFR считают факториал миллиона за 37 сотых секунды.

Однако ж мне нужны векторы, для обработки на ГПУ. Складывать и умножать большие числа я хочу на ГПУ.
Получить от GMP+MPFR вектор может и можно, но вряд ли за 37 сотых секунд.

@Somebody · 23.08.2015, 13:07

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

Факториал 1 миллиона в двоичной системе это 5565709*4 двоичных циферок.
А так как минимальное хранилище это байт, это будет ~21 Мегабайт вместо 5.
В общем, много-премного и с памятью будет совсем бяда..

В одном байте 8 двоичных циферок, в четырёх - 32, а у тебя в четырёх - 9 десятичных, что соответствует 29,9 двоичных.

zer0mail · 23.08.2015, 18:58

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

Так как вычислений много, а вывод в десятичной системе один, считать надо в двоичной, чтобы не было делений на каждой итерации.

Вычисления сократились с 54 сек до 11, а вывод увеличился с 1 сек до 14 минут.

@SerVal · 23.08.2015, 20:57 **[ТС]**

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

Вычисления сократились с 54 сек до 11, а вывод увеличился с 1 сек до 14 минут.

Впечатляет, но непонятно - вычисление чего сократилось?
* я вот тоже намедни сильно ускорил, да не тут-то было! Результаты хоть и похожи, да не совпадают.

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

C++
1
2
3
4
5
6
7
8
9
>TestBigInt.exe -generate "2^77071069-1"
 
Generating number 2^77071069-1
 Ok.
 big integer :  368882791 ... 195571711
 number of decimal digits = 23200704
 number of segments       = 2577856
 
time : 8672.88 sec.

Мда.. создаётся больше 2-х часов. Уж совсем была наша победа..
То есть, клиент получит число для проверки в виде "2^77071069-1" и создавать его больше 2-х часов.
Тут уж не до Люка-Лемера.

Может я Карацубу неправильно прикрутил, а может ещё что.. посмотрю, конечно..
Плохо то, что поменяв что-то в библиотеке - не с чем сравнить.

Кто-нибудь знает, нельзя ли откуда-нибудь скачать большое число (файл с циферками) ?

zer0mail · 23.08.2015, 23:22

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

Кто-нибудь знает, нельзя ли откуда-нибудь скачать большое число (файл с циферками) ?

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

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

Впечатляет, но непонятно - вычисление чего сократилось?

Сократилось вычисление факториала. BigInt у меня хранится в массиве, в каждом элементе порция по модулю 10^9. Теперь порция по модулю 2³² и делить не надо, но проблема вывести данные в виде 10-ного числа (массив ~50тыс элементов).

Все же странно, что 64-битная арифметика в разы быстрее делит. У меня ведь тоже делимое находится в двух 32-битных регистрах и делится на делитель в третьем 32-битном регистре. Какая разница электронике - разбито 64битное число на 2 регистра или сидит в одном?

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

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	20.08.2015, 08:55
	Асимптотическое разложение 400тыс точных знаков не даст. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	22.08.2015, 22:48
	GMP+MPFR считают факториал миллиона за 37 сотых секунды. 0

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	22.08.2015, 23:02
	Так как вычислений много, а вывод в десятичной системе один, считать надо в двоичной, чтобы не было делений на каждой итерации. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	22.08.2015, 23:11
	zer0mail, в этой теме ТС как-то прикрутил. Можешь спросить у него. Добавлено через 6 минут Установил точность в миллион знаков. Время вычисления 227.262 секунд. 0