я в свое время не нашел и писал для себя небольшой класс на основе векторов

gmp дёргать.
http://gmplib.org/manual/C_002b_002b-Interface-General.html

Всегда было интересно, а для каких задач нужны ну уж настолько огромные числа?

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries

на suckless gmp в разделе sucks за тормознутость.

http://www.google.ru/search?q=bignum c++

и да,

$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
10^100
10000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000
obase=7
10^100
16201341553122251063252024261246503522112115506446252526241360534151\
125226544036056624134325461423451523416401660341314

это тебе для проверки правильности работы твоей программы.

для 10^1000 тоже работает.

да, gmp тоже годно.

Вроде в новый стандарт хотят впихнуть.

когда занимался спортивным программированием, то часто писал с нуля длинку. Оно не сложно. Учитывая, что умножение не нужно - то оно делается за минут 30. Взять основания СС 10^8 и хранить эти цифры в обратном порядке, при сложении учитывать «переполнение» и перебрасывать его на следующий разряд. А перевод в 7 СС - просто в цикле делить и делить с конца вектора.

:)

Можно ссылку?

Сори, не могу найти. Можно считать мои слова брехнёй.

вот я дебил был 2 года назад! я переводил в строки, а потом что-то с ними делал =(

я тут начал разбираться в brainfuck-e и в программе которую пишу, код примера «+++++++.» представляю в числе «11111112», а дальше можно вносить изменения в это код простыми арифметическими действиями, например +11 это будет уже код «++++++.>». Почему именно числа? Потому что делаю кластер распределенных вычислений, по моим расчетам передавать задания другим машинам в кластере в виде арифметики гораздо быстрее, нежели, передавать массивы исходных кодов brainfuck-a. Именно из-за скорости и начал осваивать малознакомый мне ранее с++ =)

Спасибо

Спасибо, буду пробовать ваши советы

Учитывая, что умножение не нужно - то оно делается за минут 30.

Вот и подросло поколение, которое сложение в столбик программирует полчаса.

Номинация «лучше вещества месяца»

Покажи свое.

А перевод в 7 СС - просто в цикле делить и делить с конца вектора.

проще умножать на M/7, где M это MAX_INT+1.

вот я дебил был 2 года назад! я переводил в строки, а потом что-то с ними делал

почему «дебил»? Все так делали, кроме быдлокодеров.

Вот и подросло поколение, которое сложение в столбик программирует полчаса.

мне, дебилу, потребовалось часа 4, лет так 20 назад. Ньюбии растут, да, куда нам, старикам…

Покажи свое.

Не бессмысленно ли делать такой реквест, если ты не поймешь, сам я кусочек кода написал или поглядывал на e-maxx.ru?

лол) я образно же ну. Я обычно еще пишу умножение за O(n^1.5) + отлаживаю. Поэтому и выходит под пол часа :) А вообще на олимпиадах нужно было быстро писать да, да и умножение длинки на длинку мне не попалось ни разу, пока-что :)

я сразу начал с длинки с СС 10^8 на динамических массивах. ЧЯДНТ?)

то что твоя длинка irl никому не нужна

ну я ведь ее на олимпиадках писал, а не для общего потребления.:)

проще умножать на M/7, где M это MAX_INT+1.

В кольце по модулю 1e8 (используемый TakeOver) обратный элемент у 7 очевидно единственный, и он равен 42857143, так что очень странно умножать на что-то другое, чтобы поделить на 7.

ты не понял идею

делить ничего не нужно. ВСЕ число умножается. и потом сдвигается на M вправо. получается частное и выдвигается остаток

Проще довериться компилятору:

int main(void)
{
    int x;
    x /= 10000000;
}

$ gcc -O0 -S c.c

	movl	12(%esp), %ecx
	movl	$1801439851, %eax
	imull	%ecx
	sarl	$22, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movl	%eax, 12(%esp)

речь про длинную арифметику. И конечно это не я придумал, компилятор тоже в курсе ☺

кстати в CommonLisp искароппки длинная арифметика, а также рациональные дроби с бесконечной точностью.

в F# оно, емнип, тоже из коробки: BigInteger и BigRational //ф шарпом почти не пользовался.

да и в Руби тоже есть, но меня именно скорость не устроила, так вычисления надо будет делать десятками млн.

Ну не удивительно же, что у них скорость проседает, да и память. Умножение длинных чисел - это быстрое преобразование Фурье за O(NlogN) , где N - кол-во значащих разрядов(чем больше СС - тем их меньше). Применять длинку нужно там, где есть реальная необходимость, а не где попало, имхо :)

https://code.google.com/p/zozotez/

Посмотри тут.

как показывает практика лучше/удобнее bc ничего нету.

alf@alfresco-dev:~$ time echo "ibase=10;obase=7;2*10^1000 + 12*10^999" | bc
54513016115254264313261200636056354666106040412444511166560656300554\
33645625005365660144604330040625013533021624344211621242163052562406\
42026464624543360641635611632500351423515000625001243406525064442326\
46151222356266356303012110013505230032221554424621502665453506410404\
46416055303135424511421065053241635355333566346025514056164511056223\
50025465124660660123316145613066410111013002633516104013553341620500\
13642242531340102324535116632004420505045245600624442220156654621413\
03363222452413553236515101103563121566255320214121104601121210561336\
44164366110045031341605333422250134642520312401455534523646054334454\
66360125212053560335522005231245053016413325502225036455266316201550\
06314566144204263505200363403506355205664633452611331655056536512502\
22231166246262665051551342242036561215554640144304023453620355663241\
23252006102336401365311254143542462513162345214560541446111226512441\
03166003645031243021622262453015651115315514113340106051325426044561\
63411230062505025603106122225256565165504250465015342546614542122266\
41354044125360660112534031352464631146343341640404404220540626632342\
16146462135554252353201115630536432030010206412440026364203165232315\
4021415153655001526506244113

real    0m0.050s
user    0m0.052s
sys     0m0.000s

Boost.Multiprecision

Ну или просто GMP C++ Class Interface

а отправить из С++/Ruby в bc и забрать обработанные данные будет быстрее, нежели в самом С++ выполнить это? мне кажется, выполнить в С++ операции выйдет быстрее.

а давайте еще посоревнуемся кто быстрее дрочит

когда вы делаете вычисления миллионами, иди миллиардами, эти секунды складываются, в часы, а иногда в дни. по мне существенно, сколько ждать результата - 30 дней или 60

когда вы делаете вычисления миллионами, иди миллиардами, эти секунды складываются, в часы, а иногда в дни. по мне существенно, сколько ждать результата - 30 дней или 60

ты не поверишь, но вычисления по программе можно делать ВНУТРИ bc.

Например(из мана)

$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
            define f (x) {
                if (x <= 1) return (1);
                return (f(x-1) * x);
              }

f(10)
3628800

по моим расчетам передавать задания другим машинам в кластере в виде арифметики гораздо быстрее, нежели, передавать массивы исходных кодов brainfuck-a.

Я бы просто взял бы либу minilzo и сжимал массив перед передачей. LZO на сжатие всего в 2 раза медленней, чем memcpy, а профит очевиден — сжимать будет лучше, чем арифметическое преобразование. И программировать лечге, ибо там всего две функции в библиотеке.

«когда говорят о скорости/быстроте я хватаюсь за пистолет». :D

сначала надо сделать, чтоб программа работала, если программа не удовлетворяет критерию «скорость» (он у тебя правда есть ?) то начинают замерять скорость и оптимизировать узкие моменты.
bc работает очень быстро и позволяет очень быстро получить результат.

Я в криптографии использую большие числа...

Я в криптографии использую большие числа...

Криптография — другое. В ней фиксированные числа, например числа в 2048 бит, это 16 чисел по 128 бит из SSE2+.

Ты говоришь что блочные шифры... Там там и есть. Но посмотри на Алгоритм Диффи — Хеллмана, когда модуль и степь большие числа :) И не всегда применима технология SSE.

В общем не суть где использовать, но я использовал gmplib

Но посмотри на Алгоритм Диффи — Хеллмана, когда модуль и степь большие числа :) И не всегда применима технология SSE.

этот алгоритм можно хоть на bash'е писать. Он нужен только для обмена ключами, т.е. один раз за сеанс. Дальше мы пакуем всё блочным симметричным шифром, и тут производительность важна.

Согласен что дальше всё пакуем... Но я лишь показал где может применяться длинная арифметика.

эти алгоритмы вроде готовые есть. Зачем?