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

@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 секунд. Как они это делают?

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

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