ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / C++ BigIntegers parallel library
25 сообщений из 104, страница 4 из 5
  4  все
C++ BigIntegers parallel library
    #38394079
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SerValдержать в памяти BigInt-ы (векторы с миллиардом знаков) - это ж никакой
памяти не хватит.
А я это говорил ещё на первой странице... Да и для целей криптографии (где простые числа в
основном и используются) гораздо выгоднее числа держать в двоичном виде, а не
двоично-десятичном как у тебя. Работает оно так потом быстрее.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
11.09.2013, 19:29
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394100
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
mayton , я с Вами полностью согласен. И с Вами, Дмитрий .
И зачем библиотеки для больших чисел.. а Микрософт недавно добавила в C#.. :)

*хранить в int-ах приходится потому, что у акселераторов пока нет типа char. Делают.
и векторы у них есть только короткие, типа rgbi.
...
Рейтинг: 0 / 0
11.09.2013, 20:14
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394122
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SerVal,

От буйной фантазии юного (ш)кодера нет спасения ни для железа ни для софта и вобщем
то голове покоя тоже нет. Я не знаю что там Mircrosoft ввела но кажется в С#/Net decimal
существовал давно и его основное назначение - работа с финансовыми расчётами
и сопряжение с типами данных в DBMS и конвертация туда и обратно.

Я не знаю зачем там тебе так сильно нужна хардкорная оптимизация сложения
ну если уж так сильно хочется - почитай про:
- BCD арифметику
- Учебник Юрова (2 издание) Assembler - Глава 8 - Арифм.операции над двоично-десятичными числами (команды
AAA, ADC, AAS, AAM, AAD).

P.S. Тут в смежном форуме тоже был один перфекционист. Пилил свою In-memory db с ооочень
быстрым откликом. Только вот любое сопряжение с ней из .Net к примеру просаживало отклики
тысячекратно. Вот такой вот архитектурный промах-с. Так ште... не ошибись дверью.
...
Рейтинг: 0 / 0
11.09.2013, 21:13
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394143
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
mayton , если я Вам так сильно мешаю. не обязательно ведь заглядывать в эту ветку. Не правда ли?
...
Рейтинг: 0 / 0
11.09.2013, 21:57
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394148
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Извини брадт. Я всё таки модератор.
...
Рейтинг: 0 / 0
11.09.2013, 22:09
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394153
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
maytonИзвини брадт. Я всё таки модератор.
Ну и замечательно.
В таком случае, не буду утомлять модераторов и остальных участников форума "буйными фантазиями юного шкодера".
Всем хорошего настроения.
За сим, разрешите откланяться.
С уважением, SerVal.
...
Рейтинг: 0 / 0
11.09.2013, 22:29
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394207
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SerValПро буст я не знаю.
Может оно и к лучшему. Меньше знаешь - крепче спишь.
Но не беспокойтесь, это вовсе не благодаря Бусту все работает быстрее в сотни раз :)
...
Рейтинг: 0 / 0
12.09.2013, 01:24
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394225
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
SerVal m_Sla , Вы молодец, разобрались. Спасибо. Правда в Вашем коде я пока разобраться не могу.
Однако ж сам дошёл до получения вектора <carry>. Получить из <prefix scan> <carries> пока не получается. :(
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
a:                < 9, 7, 5, 3, 1> 
b:                < 3, 2, 1, 8, 6> 
c:                < C, M, N, C, N> 
prefix scan:  < C, C, N, C, N> 
carries:        < 0, 1, 1, 0, 1> 
sum:            < 2, 0, 7, 1, 8> 

// из <prefix scan> получаем <carries>
   memmove(carry.data()+1,carry.data(),carry.size()-1);
   carry[0]=0;

Как Вы получаете из <prefix scan> <carries> - ещё непонятнее. Каким-то копированием памяти? ??? Совсем непонятно.<prefix scan> сдвигаем вправо на один разряд и получается <carries>

Как распараллелить <prefix scan> написано тут http://www.toves.org/books/distalg/#3.1
...
Рейтинг: 0 / 0
12.09.2013, 05:29
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38394236
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
maytonА если серъезно - то факторизация гораздо интереснее чем то чем ты занят. Поинтересуйся как-нибудь.
Можно зацепить краем теорвер, теорию чисел, алгебру.Да-да. Попробуйте разложить на множители число ну хотя бы с 300 десятичными цифрами.
...
Рейтинг: 0 / 0
12.09.2013, 07:24
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38395193
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
?maytonА если серъезно - то факторизация гораздо интереснее чем то чем ты занят. Поинтересуйся как-нибудь.
Можно зацепить краем теорвер, теорию чисел, алгебру.Да-да. Попробуйте разложить на множители число ну хотя бы с 300 десятичными цифрами.
При чём здесь 300? Я автору предложил интересное поле для экспериментов. Задача факторизации
более интересна и познавательна чем сложение. Я сам не претендую ни на что. Только подсказываю.
...
Рейтинг: 0 / 0
12.09.2013, 19:14
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38395440
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
maytonПри чём здесь 300?Ну просто типичный размер для RSA
...
Рейтинг: 0 / 0
13.09.2013, 08:08
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
C++ BigIntegers parallel library
    #38929993
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
Ребятки, я тут маленько сложение доделал. Однако ж результаты не впечатляют. :(

D:\aProjects\TestBigInt\x64\Release>TestBigInt.exe -nvidia
Accelerator : NVIDIA GeForce GTX 980
==============
BigInt1 размер : 10 миллионов цифр.
BigInt2 размер : 10 миллионов цифр.
Loop = 100

Addition on CPU: 33.8 seconds.
Addition on GPU: 26.8 seconds.
******
При сложении на видеокарте она загружена на 3-5%, а ЦПУ на все 100%.
Понятно, что и ускорения как такового нетути. Подозреваю, что это из-за неподходящей структуры BigInt.

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

private:
std::vector<int> number; // здесь хранятся цифры
};


Вектор для хранения удобен, но очень медленно заполняется значениями: resize(), push(), push()..
Нельзя ли заполнить вектор из строки параллельно? (чёта никакой идеи по этому поводку нетути).
Или изменить сам класс BigInt? *идеи тоже нетути.
...
Рейтинг: 0 / 0
08.04.2015, 08:45
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930008
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
Понатыкал где только можно #pragma loop(hint_parallel(4))
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
//***************************
// конструктор из строки
BigInt::BigInt(const std::string& str)
{
    int str_size= str.size();
    number.reserve(str_size+1);

   #pragma loop(hint_parallel(4))
    for (int i = str_size-1; i>=0; i--)
    {
        number.push_back(str[i]-'0');
     }
}

... но не помогло. :)
...
Рейтинг: 0 / 0
08.04.2015, 09:07
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930019
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
SerValВектор для хранения удобен, но очень медленно заполняется значениями: resize(), push(), push()..


Есть мощный ускоритель -- reserve().

SerValНельзя ли заполнить вектор из строки параллельно?


resize(), push(), push( -- это:

выделение новой памяти нужного нового размера

копирование элементов из старой памяти в новую в пределах минимума из старого и нового размера

выполнение конструкторов для элементов (новый размер - старый размер)

выполнение деструкторов для элементов (старый размер - новый размер)

сам подумай, какие из этих операций можно распараллеливать.
...
Рейтинг: 0 / 0
08.04.2015, 09:20
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930020
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
Ну и появилась ценная идея: может хранить большие числа в научной нотации?
Типа: a*2^n+b; Тогда можно ускорителю передавать не огромные строки, а числа a, n и b.

ГПУ всё равно делать нечего, пусть сам в своей памяти и распакует перед сложением.
А результат вернёт тоже в научном виде.

*правда как распаковывать я тоже не знаю, но где-то ж, наверное, написано?
...
Рейтинг: 0 / 0
08.04.2015, 09:22
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930041
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
MasterZivЕсть мощный ускоритель -- reserve().

- reserve() уже используется (посмотрите код выше).
Посмотрю пока как распаковывать научную нотацию в массив int[].
...
Рейтинг: 0 / 0
08.04.2015, 09:44
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930378
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SerValНу и появилась ценная идея: может хранить большие числа в научной нотации?
Типа: a*2^n+b; Тогда можно ускорителю передавать не огромные строки, а числа a, n и b.

ГПУ всё равно делать нечего, пусть сам в своей памяти и распакует перед сложением.
А результат вернёт тоже в научном виде.

Чел. Это просто какой-то фейспалм! Во первых не все числа точно представимы в сабж.

Во вторых что значит "ГПУ всё равно делать нечего". Это что ? Откуда? Как так
вообще можно делать постановки?!

А потом в дайджестах новостей софта и железа стоит плачь и вопль великий... дескыть
железо греется без причины.... занято неизвестно чем... Может адварь какой или троян?
...
Рейтинг: 0 / 0
08.04.2015, 13:07
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930407
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonSerValНу и появилась ценная идея: может хранить большие числа в научной нотации?
Типа: a*2^n+b; Тогда можно ускорителю передавать не огромные строки, а числа a, n и b.

Во первых не все числа точно представимы в сабж.
Все, только a и b будут иметь порядок максимального sqrt(a*2^n+b)
Например для любого x64 числа это а и b размером до 2^32 и n = 32

Только не понимаю зачем строки, когда можно считать массив N байт одним числом из 8N бит. Например 10 байт это числа до 2^80
...
Рейтинг: 0 / 0
08.04.2015, 13:25
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930448
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
maytonЭто просто какой-то фейспалм! Во первых не все числа точно представимы в сабж.
Спасибо что сказали. Теперь буду знать. Заодно и не буду тратить время на поиск преобразования таких чисел в массив.
Поищу в интернете - нет ли какого другого компактного формата представления больших целых чисел.
*****
Для нВидии карт выпустили библиотеку для работы с большими числами. Называется CUMP. Какой-то умный японец сделал.
А для С++ AMP такой библиотеки нетути. :(

*cобственно говоря мне нужна не столько библиотека, сколько функции типа isDivider(number), isPrime(number)..
...
Рейтинг: 0 / 0
08.04.2015, 13:46
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930483
SerVal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SerVal
Гость
Dima ТВсе, только a и b будут иметь порядок максимального sqrt(a*2^n+b)
Например для любого x64 числа это а и b размером до 2^32 и n = 32

a, b, n - от 0 до MAXUINT64. К тому же база может быть и не двойкой, а десяткой или больше.

Только не понимаю зачем строки, когда можно считать массив N байт одним числом из 8N бит. Например 10 байт это числа до 2^80
Ну, тогда нужна какая-то библиотека или исходники, чтобы можно было складывать и вычитать числа из 8N бит.
У меня такой нетути. К тому же для вычислений на ГПУ библиотеки для ЦПУ не подходят, то есть надо исходник.
...
Рейтинг: 0 / 0
08.04.2015, 14:01
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930540
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SerValУ меня такой нетути. К тому же для вычислений на ГПУ библиотеки для ЦПУ не подходят, то есть надо исходник.
GMP посмотри, она с исходниками вроде
...
Рейтинг: 0 / 0
08.04.2015, 14:25
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930698
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TSerValУ меня такой нетути. К тому же для вычислений на ГПУ библиотеки для ЦПУ не подходят, то есть надо исходник.
GMP посмотри, она с исходниками вроде
Кстати ты нашёл где там "gmp.h" ? Я - нет.
...
Рейтинг: 0 / 0
08.04.2015, 15:51
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930742
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonКстати ты нашёл где там "gmp.h" ? Я - нет.
ЕМНИП Он в процессе сборки либы появляется. В виндовсе сам ниасилил. Мне дали готовую .lib для MSVC2008 с gmp.h
в линуксе надо сначала отдельным пакетом установить (libgmp-dev) и при компиляции так
Код: plaintext
1.
g++ ... -lgmp
...
Рейтинг: 0 / 0
08.04.2015, 16:08
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930751
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ОК. У меня MinGW для Windows. Я попробую доустановить пакеты поддержки GMP для начала.
Если не выйдет по попрошу у тебя собранную либу.
...
Рейтинг: 0 / 0
08.04.2015, 16:11
| Ответить | Цитировать | Написать  
C++ BigIntegers parallel library
    #38930774
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonОК. У меня MinGW для Windows. Я попробую доустановить пакеты поддержки GMP для начала.
В дебиан все просто, одна строчка
Код: plaintext
1.
sudo apt-get install libgmp-dev


и пользуйся.
maytonЕсли не выйдет по попрошу у тебя собранную либу.
Боюсь что не поможет. Она у меня x32 для виндовса. А у тебя x64
...
Рейтинг: 0 / 0
08.04.2015, 16:22
| Ответить | Цитировать | Написать  
25 сообщений из 104, страница 4 из 5
  4  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / C++ BigIntegers parallel library
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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