Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / C++ BigIntegers parallel library / 25 сообщений из 104, страница 1 из 5
06.09.2013, 09:37
    #38388694
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Не могу найти ничего подходящего. Погуглил, есессно. Все библиотеки используют только один процессор.
Кроме того, конструкторов типа

Код: plaintext
1.
2.
3.
4.
5.
6.
std::string string1="123456789...."; // строка с миллионом цифр 

cout << "Constructing Big Intintegers."<< endl;

BigInt bigInt1(string1);
BigInteger bigInteger1 = stringToBigInteger(string1);


- так и не дождался. До умножения и деления, есессно, дело не дошло. :(

У меня в компику 8 процессорных ядер у CPU и 1600 ядер у GPU и ничего они в это время не делают.
Если кому-нибудь известна библиотека - поделитесь, пожалуйста, ссылкой.
*писать самому как-то не очень.. типа изобретать велосипед. :(
...
Рейтинг: 0 / 0
06.09.2013, 11:08
    #38388829
skynowa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
CUDA
...
Рейтинг: 0 / 0
06.09.2013, 11:47
    #38388886
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Спасибо за ответ, однако, не совсем понял, при чём здесь CUDA ? CUDA - это технология программирования видеоадаптеров nVidia.
Программировать видеоадаптеры я пока не планирую. Ищу обыкновенный класс BigInt.
Ну и сложение, умножение.. к нему. Типа:
Код: plaintext
1.
2.
3.
BigInt a("1");
BigInt b("2");
BigInt c = a +b;


Сейчас лазию по Интернету... мож кто-нибудь уже написал.
Заодно проверил и библиотеку Microsoft BigInteger для C# (numerics.dll). Она тоже одноногая(еле ползает). :(
Ну и всякие самописные смотрю.. они в лучшем случае на уровне студенческих лабораторных работ.
С большими числами они не работают. *точнее, делают вид, что работают.
...
Рейтинг: 0 / 0
06.09.2013, 12:45
    #38388976
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValСпасибо за ответ, однако, не совсем понял, при чём здесь CUDA ? CUDA - это технология программирования видеоадаптеров nVidia.
Программировать видеоадаптеры я пока не планирую. Ищу обыкновенный класс BigInt.


CUDA здесь при том, что оно именно это и делает -- параллельные вычисления на, по странному стечению обстоятельств, видеопроцессоре.
...
Рейтинг: 0 / 0
06.09.2013, 13:03
    #38389014
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValИщу обыкновенный класс BigInt.
Ну и сложение, умножение.. к нему.
Если бы ты его не искал, а запрограммировал сам, то понял бы что
1) Это быстрее чем искать
2) Сложение и умножение последовательны и, как следствие, не распараллеливаются.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
06.09.2013, 13:15
    #38389028
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Dimitry SibiryakovSerValИщу обыкновенный класс BigInt.
Ну и сложение, умножение.. к нему.
Если бы ты его не искал, а запрограммировал сам, то понял бы что
1) Это быстрее чем искать
2) Сложение и умножение последовательны и, как следствие, не распараллеливаются.


Векторов -- параллелятся.
...
Рейтинг: 0 / 0
06.09.2013, 13:29
    #38389052
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Добрый день MasterZiv .
Посмотрел я КУДУ. И никакой библиотеки класса типа BigInt и интерфейса к нему не обнаружил.
*вероятно, по странному стечению обстоятельств.

Не могли бы Вы привести простенький примерчик типа:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
#include "мояCUDA.h"
int main( int argc, char *argv[])
{
BigInt a("1");
BigInt b("2");
BigInt c = a + b;

cout << a<< "+" <<b <<" = " << c << endl;
}


Ну и откуда скачать header и саму библиотеку. Возможно, я просто не нашёл, или чего-то не понимаю.
*****
Взглянул на ещё одну библиотеку: http://www.shoup.net/ntl/ .. компилится, но тоже использует только один процессор.
*****
...
Рейтинг: 0 / 0
06.09.2013, 13:39
    #38389068
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Dimitry SibiryakovЕсли бы ты его не искал, а запрограммировал сам, то понял бы что
1) Это быстрее чем искать
2) Сложение и умножение последовательны и, как следствие, не распараллеливаются.

Добрый день Дмитрий.
1) Самому написать, к сожалению, не быстрее.
2) сложение и умножение замечательно распараллеливаются. *написать простенький пример на C++- дело 10-15 минут.
Впрочем, Вы и сами можете взглянуть:
"Introduction to parallel & distributed algorithms"
Adding big integers: http://www.toves.org/books/distalg/#3.3
...
Рейтинг: 0 / 0
06.09.2013, 13:48
    #38389085
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValВпрочем, Вы и сами можете взглянуть:
А мне-то зачем? Это же тебе библиотека нужна...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
06.09.2013, 14:01
    #38389097
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Dimitry SibiryakovА мне-то зачем? Это же тебе библиотека нужна...
Ну, хотя бы затем, чтобы в следующий раз не писать такое:
Dimitry SibiryakovСложение и умножение последовательны и, как следствие, не распараллеливаются..
А то неудобно как-то.

*такая библиотека много кому нужна. :)
...
Рейтинг: 0 / 0
06.09.2013, 14:06
    #38389102
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValНу, хотя бы затем, чтобы в следующий раз не писать такое:

Видишь ли, теория, описанная в книгах, несколько отличается от практики. Да, я верю, что
распараллеливание арифметики над числами в миллионы бит даёт выйгрышь. Но на тысячах бит
накладные расходы на создание и координацию потоков съедают всю прибыль. И чем расписывать
все эти тонкости для чайника, проще сказать "сложение не распараллеливается".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
06.09.2013, 14:12
    #38389108
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerVal*такая библиотека много кому нужна. :)
Это спорное утверждение.
Целые большие числа нужны только в криптографии. А там нет таких разрядностей - миллион цифр.
Максимум тысячи, и то двоичных разрядов.

Касательно торможения при инициализации числа - вполне возможно тормозит не преобразование из строки, а выделение памяти под результат (перевыделение при росте массива).
Если эта догадка верна, то распараллеливание вам не поможет :)
...
Рейтинг: 0 / 0
06.09.2013, 14:17
    #38389117
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Anatoly MoskovskyКасательно торможения при инициализации числа - вполне возможно
тормозит не преобразование из строки, а выделение памяти под результат
Умножение на 10. Фиг знает как они его делают...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
06.09.2013, 14:18
    #38389121
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerVal
Не могли бы Вы привести простенький примерчик типа:


Ты бы лучше объяснил, что же тебе нужно.
...
Рейтинг: 0 / 0
06.09.2013, 15:09
    #38389208
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
АнатолийЦелые большие числа нужны только в криптографии. А там нет таких разрядностей - миллион цифр. Анатолий , называть "большими" числа размером меньше миллиона цифр даже как-то неудобно.
АнатолийКасательно торможения при инициализации числа - вполне возможно тормозит не преобразование из строки, а выделение памяти под результат (перевыделение при росте массива).
Если эта догадка верна, то распараллеливание вам не поможет :)
Я посмотрел. Ребятки не умеют параллельно запихивать циферки из строки в массив. Или не хотят?
Я как вижу что-нибудь вроде:
Код: plaintext
1.
2.
3.
4.
for(int i=0 i<strlen(str);  i++
{
  array[i]=(char)str[i];
}

Сразу понятно, что дальше ничего приличного не будет.
А утверждают, что их библиотеки для больших чисел. Мда... программисты ещё те...
*********
MasterZivТы бы лучше объяснил, что же тебе нужно.
Я ж говорю - билиотека, которая на самом деле работает, а не делает вид.
И есть проект распределённых вычислений PrimeGrid@home , который ищет всякие там числа Мерсена, Вудала.. и прочие простые.
И регулярно утверждают, что нашли что-то большое и ценное. А проверить их невозможно. Может врут, а может не очень..
Во: Record prime Fermat divisor:
57^22747499+1 Divides F(2747497)

Ясное дело, я не такой придурок, чтобы самому эти числа искать(кому они нужны), но проверить хочется.
*это для начала. есть и другая нужда. :)
******
Сейчас прикинул мож и правда самому натяпать? Ребятки, такая структура подойдёт:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
class BigInt {
public:
BigInt() { };
BigInt(const std::string&); // конструктор из строки
private:
std::vector<int> number;
};


*Ну, ещё операторов натяпать и можно пробовать чё-нибудь сложить.
******
...
Рейтинг: 0 / 0
06.09.2013, 15:39
    #38389246
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValИ есть проект распределённых вычислений PrimeGrid@home , который ищет всякие там числа Мерсена, Вудала.. и прочие простые.
И регулярно утверждают, что нашли что-то большое и ценное. А проверить их невозможно. Может врут, а может не очень..
Я сначала надеялся что это распараллеливание для чего-то действительно полезного нужно.
Но судя по всему оно вообще не нужно. Никому. И вам в том числе.
Так что удачи в мечтаниях .
...
Рейтинг: 0 / 0
06.09.2013, 15:57
    #38389275
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValMasterZivТы бы лучше объяснил, что же тебе нужно.
Я ж говорю - билиотека, которая на самом деле работает, а не делает вид.


В общем, я понял (далеко не сразу), что ему нужно.
Ему нужна библиотека для поддержки вычислений очень больших точных чисел (не с плавающей точкой),
которая поддерживала бы распараллеливание вычислений.

Если что не так -- поправь.
...
Рейтинг: 0 / 0
06.09.2013, 15:59
    #38389282
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
Anatoly Moskovsky , очень приятно, что Вы знаете, кому что нужно и полезно(тем более мне).
... просто удивительно, почему Вы ещё не депутат Государственной Думы.
...
Рейтинг: 0 / 0
06.09.2013, 16:03
    #38389291
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
MasterZiv , Вы совершенно правы.
И мне всё равно как она будет считать: параллельно или перпендикулярно. Лишь бы быстро.
*пока такой библиотеки нетути. :(
...
Рейтинг: 0 / 0
06.09.2013, 17:01
    #38389431
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValИ есть проект распределённых вычислений PrimeGrid@home , который ищет всякие там числа Мерсена, Вудала.. и прочие простые.
И регулярно утверждают, что нашли что-то большое и ценное. А проверить их невозможно. Может врут, а может не очень..
Во: Record prime Fermat divisor:
57^22747499+1 Divides F(2747497)

Ясное дело, я не такой придурок, чтобы самому эти числа искать(кому они нужны), но проверить хочется.
А вы что собственно проверить хотите? Что число 57^22747499+1? Как именно? Или что 57^22747499+1 делит F(2747497)? Каким способом? Чтобы проверить, нужен нетривиальный софт. И арифметические операции с большими числами - это только очень маленький его кусочек.
...
Рейтинг: 0 / 0
06.09.2013, 17:41
    #38389488
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
GuestА вы что собственно проверить хотите? Что число 57^22747499+1? Как именно?
Чтобы проверить, нужен нетривиальный софт.
Для начала, то что число простое. Чего ж тут сложного?

К примеру, пишем:
Код: plaintext
1.
2.
3.
4.
BigInt candidate;
candidate=Parse("2^12345+1");
if((candidate%2) == 0 )
cout << "candidate is NOT prime number."<< endl;


Собственно, нужна только библиотека. А уж всяких алгоритмов достаточно. Начиная от простого решета, до Рабина-Мюллера :)
...
Рейтинг: 0 / 0
06.09.2013, 23:17
    #38389760
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerVal, Рабин-Мюллер не дает гарантию что число простое. А перебрать все возможные делители в ближайший миллиард лет вам никак не успеть, ни на одном процессоре ни на 1000.
...
Рейтинг: 0 / 0
06.09.2013, 23:24
    #38389768
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
?Рабин-Мюллер не дает гарантию что число простое.
В качестве проверки можно сгенерить из этого числа RSA ключ. Сработает - точно простое.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
07.09.2013, 12:11
    #38389920
SerVal
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
GuestSerVal, Рабин-Мюллер не дает гарантию что число простое. А перебрать все возможные делители в ближайший миллиард лет вам никак не успеть, ни на одном процессоре ни на 1000.
Ясное дело, Мюллер для предварительной проверки перед Лемнером. Но ето ещё рано обсуждать.
А насчёт "не успеть".. так моя бабушки считала на калькуляторе "Феликс".. тож говорила, что до конца года не успеть..
У них там цельный отдел ручки крутил.

Dimitry SibiryakovВ качестве проверки можно сгенерить из этого числа RSA ключ. Сработает - точно простое.
А генератор RSA ключа может генерить ключ из числа с 1 000 000 000 цифрами ? Если может, то за сколько он примерно это сделает?
*****************************
Ну да ладно, натяпал пока простенький класс BigInt:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
class BigInt {
public:
    BigInt() { };
	BigInt(const std::string&);
	virtual ~BigInt()	{ };

	friend	std::ostream &operator<<(std::ostream&, BigInt&); 
	friend void BigInt::parseSubstring(const std::string& str, size_t start_pos, const size_t  block_size, const size_t block_num, std::vector<int>* x);
	size_t getLength() const { return number.size();}

	BigInt Parse(const std::string);
	enum Sign { negative = -1, zero = 0, positive = 1 };
private:
Sign sign;
std::vector <int> number;
};


Ну и конструктор из строки(заполнение вектора). Правда работает чёта медленно.
Строку из 1 000 000 000 циферок запихивает в вектор за 180 секунд. :(

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
D:\aProjects\TestBigInt\x64\Debug>TestBigInt.exe -amd
Accelerator : ATI Radeon HD 5800 Series
==================
Preparing string1 for BigInt1.
string1 size=1000000000 digits.
CPU: constructing BigInt1.
Exec time : 180 seconds.
==================



Посмотрю пока, чегой-то всё так медленно?

Ах да, скачал ещё одну библиотеку для больших чисел: C++ Big Integer Library https://mattmccutchen.net/bigint/
Тож одноногая. Однако, надо же что-то для сравнения результатов и времени.
*строки больше 10-20 тыс знаков она не переваривает. Подсунул этой библиотеке строку из 100 тыс. цифров..
Уж и в магазин сходил, а у неё всё конструктор хрюкает. Не дождался. :(
******
Всем привет и хорошего настроения. :)
...
Рейтинг: 0 / 0
07.09.2013, 13:30
    #38389943
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
C++ BigIntegers parallel library
SerValПосмотрю пока, чегой-то всё так медленно?
Или код кривой, или распараллелить забыл.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / C++ BigIntegers parallel library / 25 сообщений из 104, страница 1 из 5
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]