Очень большие числа

http://lmgtfy.com/?q=cpp large numbers

Реализуют библиотеку для работы с большими числами самостоятельно.

Длинная арифметика это называется.

Длинная арифметика

gmp

Ткните в литературу

TAOCP, глава 4.

bignum

Без использования внешних библиотек.

Но зачем?

Для себя. Интересны внутренности процесса.

Без использования внешних библиотек

тогда на ассемблере.

Например, сложение. Младшие разряды складываем инструкцией ADD, остальные - ADC (сложение с учётом флага переноса)

Можно в столбик, если не заморачиваться. А вообще для каждой функции есть крутые алгоритмы, но там всё сложно и за пять минут наверное не осилить, можешь начать с википедии и потом по научным работам.

Тогда кроме исходников gmp можешь посмотреть исходники bc.

всё, словно на черепахе, на которой три слона, стоит на представлении чисел в памяти. читай про endianness, ieee754 например.

А как это поможет работе с большими числами? ЕМНИП, 754 стандарт говорит нам про операции с плавающей точкой и только о них. И вроде как там ничего не говорилось про реализацию с произвольной точностью и/или реализацию длинной арифметики. Могу ошибаться, но просьба тогда ткнуть носом в нужные пункты стандарта.

Ну и да - а причем тут endianess и длинная арифметика? Вроде как вражда остроконечников с тупоконечниками начинает играть роль только как одна из деталей реализации, да и то не уверен. То же хотелось бы более развернутого объяснения.

А как это поможет работе с большими числами? ЕМНИП, 754 стандарт говорит нам про операции с плавающей точкой и только о них. И вроде как там ничего не говорилось про реализацию с произвольной точностью и/или реализацию длинной арифметики. Могу ошибаться, но просьба тогда ткнуть носом в нужные пункты стандарта.

Почитай хотя бы вот это: http://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#cite_n...

Там есть стандарт на числа с плавающей точкой о 128 битах. А первая же ссылка на работу Bailey and Borwein, где они популярно рассказывает зачем нужны вычисления с длинными вещественными, а также упоминает популярные пакеты работы с ними. Он написал сам пакет QD, который считает в double-double (128 bit) и quad-double (256 bit ) точности. QD гораздо удобнее, когда нужная точность находится в пределах 20-64 десятичные цифры. Если нужно точнее, то есть GMP, MPFR и C++ интерфейсы к ним.

Danke schön.

Когда учился на курсах по С++, вторым заданием как раз было написать класс для работы с большими числами. Все поголовно сделали через строки. :)

Как это через строки? string?

ну я выделился, написал через char* :)

А так, у всех стринг был.

оригинально!

Я так понимаю, что это был не самый быстрый способ. Но задание зачли. :)

А какие есть еще варианты для реализации длинной арифметики в случае произвольной длины? Массивы они будут массивы. Или там было что то эпичное, типа:

std::string add(std::string a, std::string b)
{
   //код, берущий по одному(ну или по 4-8) символу(ов) с конца каждой
     строки, складывающий их и переносящий в следующий разряд при 
     необходимости.
}

main()
{
std::string a = "123";
std::string b = "321";
std::string result = add(a, b);
std::cout << result <<std::endl;
}

C++ не знаю :-)

Варианты в системе счисления. Тупая реализация на строках — в десятичной системе.

А 16-ричную систему счисления уже сложнее реализовать?) А если написать свои atoi/itoa для случая арифметики по основанию 62?

Есть ли вообще идеи реализации длинной арифметики отличные от массива неких объектов(байт, int, long int) и представления операций над длинным числом в виде операции над таковыми массивами?(кажется я с недосыпу бред несу)

Унаследовать длинное число от vector<uint32_t> как-то разумнее выглядит с точки зрения производительности. А если вспомнить про SSE, то можно попробовать реализовать и на векторах из 64-битных чисел.

Без использования внешних библиотек.

Исторически, десятичная «длинная арифметика» произвольной точности была реализована в языке «Аналитик» аппаратно в ЭВМ «МИР-2».

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

В haskell длинная арифметика из коробки (всё-таки язык для вычисления факториалов как никак).

второй том Кнута тебе поможет

Примеры примерами, но все - какие еще могут быть варианты? Мне в голову идеи не приходят.

курсовик человек пишет

Унаследовать длинное число от vector<uint32_t> как-то разумнее выглядит с точки зрения производительности.

Только не унаследовать (бить линейкой!), а использовать вложение.

Мне в голову идеи не приходят.

ты хочешь сказать, что инженеры из ieee полные ламеры и не догадались бы до того, что сейчас ты вот прям сейчас возмёшь и придумаешь? ;)

очередная курсовая рОбота? :)

да не только в вашем haskell, а в доброй дюжине ЯП, в python даже например

Придумать идею может любой человек. Тем более, если она уже есть. Ламеры не ламеры... Не в этом суть. Я и не говорил, что могу придумать что то еще. Мне интересно - находил ли кто либо другие решения помимо взять массив символов(чисел)? Именно для ситуации с длинной арифметикой произвольной длины. Для арифметики конечной точности все просто и понятно - некая структура, содержащая конечное число полей и будет представлением числа.

Для себя. Интересны внутренности процесса.

ничего трудного в этом нет, научить компьютер считать в столбик :)

GHC все бинарники линкует с GMP, так что проще тот же GMP напрямую заюзать.

http://e-maxx.ru/algo/big_integer

возможно, просто в сессию человек самообразованием не по основным направлениям редко занимается

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

позиционная система счисления

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

а вообще курни в подлинике(точнее в англ переводе ) изданное 2005 году Фибоначеево ( книжка 13 века) книга абака - там отличные логи как словесно производят деление в отсутствии (ибо лионардо пизанский таким способом показывает насколько позиционная запись заруливает) арабской записи - логи страшнее ассемблерногго кода.

так что адекватный задаче синтаксис - это часто больше половины её решения.

можеш обьеденить вектора коэфициентами в списки .