Реализация библиотеки для работы с большими числами в С

Если скорость работы и "красота кода" не критична, то храни десятичные числа в обычных строках, а операции над ними выполняй как на бумажке столбиком. Всё что сложнее +-/* - реализуй через +-/*. Дёшево и сердито =).

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

объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

вообще, насчет строк идея, на мой взгляд, самая удачная в твоем случае.
Не понимаю 2 момента:
1. какая разница твоему преподу на сторонние либы
2. кто тебе запрщал посмотреть различного рода реализации в сторонних либах и скопировать код себе? :)

Используй основание 2^32 (если машина 32-битная). Для модулярной арифметики используй редукцию Монтгомери.

> объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

В вузе за такие отмазки больно бьют по лицу, а особо упорствующих отчисляют куда подальше.

> Буду рад услышать любые идеи и предложения.

Д. Кнут высказывал по этому поводу очень хорошие идеи во втором томе "Искусства программирования". Читай соответсвующие главы и переводи примеры на C.

> какая разница твоему преподу на сторонние либы

Сказано же, сам алгоритм несложный. То есть если разрешить юзать gmp, то курсач обернётся лабой.

В том то и дело что преподу надо обязательно свою реализацию, еще и гуевую. Мало того, курсач на С, консольный и под линухом, так это уже будет на бал оценка ниже. Кнута посмотрю, модулярную арифметику тоже. Самое странное что нигде нет реализации данного крипто-алгоритма.Хорошо было бы взять gmp и не изобретать колесо, но это не мой случай...

по-хорошему, из такого вуза надо валить

это ты как раз вовремя посоветовал ага

> по-хорошему, из такого вуза надо валить

В любом вузе найдётся препод-урод.

> Сказано же, сам алгоритм несложный. То есть если разрешить юзать gmp, то курсач обернётся лабой.

тогда почему не поковырять mpg и обернуть его курсачем? :)

// wbr

>> объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

>В вузе за такие отмазки больно бьют по лицу, а особо упорствующих отчисляют куда подальше.

In real life такие люди редко что создают нового.

> Сам алгоритм не сложный, только вот встала проблема работы с большими числами.

Тоже мне проблема... По-моему преподаватель прав.

> In real life такие люди редко что создают нового.

Как можно создать что-то новое, когда не знаешь, как устроено старое??

Помню видел когда-то в интернетах варианты реализации длинных чисел,
один из них был - представление в виде связного списка, навроде

struct longnum
{
  int number;
  struct longnum * next;
};

в принципе должно работать :)

Ну и вообще, могу предложить смотреть в реализацию криптоалгоритмов 
(и ессесно длинной арифметики) в plan9, там очень просто все,
намного проще чем в ssl и прочих линуксовых реализациях.

в последнем предложении имел в виду openssl конечно же...

> В том то и дело что разрядность чисел 96 знаков, а выполнить надо три действия: НОД(алгорит Евклида)-сликом уж много получится вычитаний, два возведения в степень по модулю. Думаю это может затянутся на долгое время...

Сколько примерно простых действий (+-/*) тебе нужно выполнить? Пару сотен на современных процессорах ты вряд-ли заметишь.

>> In real life такие люди редко что создают нового.

>Как можно создать что-то новое, когда не знаешь, как устроено старое??

Ты не понял. Люди, которые всегда отдают предпочтение тому, что уже есть, редко создают что-то новое. Не Творцы они. Тип людей не тот.

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

> вообще, насчет строк идея, на мой взгляд, самая удачная в твоем случае.

Память расходуется неэффективно. Лучше строки в формате BCD, там в байте вмещаются сразу 2 десятичных цифры.

> кто тебе запрщал посмотреть различного рода реализации в сторонних либах и скопировать код себе?

+1

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

А те, кто велосипедит на низкоуровневых языках не/недореализованные там мелочи - это нисколько не Творцы, а обычные быдлокодеры на низкоуровневых языках.

Нужно разобраться с представлением чисел и только потом с реализацией базовых численных операций. Когда-то давно в студенчестве мутил такое от нечего делать (только мне это было нужно для реализации системы Эль-Гамаля). В "Получисленных алгоритмах" у Кнута описаны все необходимые нюансы. Там же есть и разные варианты алгоритмов численных операций (сложение, вычитание, умножение, деление, возведение в степень, модулярная арифметика). Скажу лишь, что из представленных там алгоритмов умножения наиболее прост в реализации метод Карацубы. При этом он не особо проигрывает методу, использующему дискретное преобразование Фурье.

С возведением в степень особо мутить не нужно. Конечно, можно (и даже нужно) извращаться с построением аддитивных цепочек, чтобы сократить количество умножений. Но это на самом деле не критично. Особенно когда начинаешь разбираться с курсовой в мае.

А строки - это не вариант. Скорость уж больно ужасная.

Для ускорения собственной работы проще сразу смотреть исходники. Причем не gmp, а какого-нибудь простенького bc. Там тоже всё это есть, причем в приличном виде.

>НОД(алгорит Евклида)-сликом уж много получится вычитаний

Берите остаток от деления вместо того, чтобы вычитать. По сути то же, но гора-аздо быстрее!

Возведение в степень тоже разгоняется:
x^2n = x^n * x^n;
x^2^k сл-но требует k операций умножения
x^137 = x^128 * x^8 * x^1 итого всего 11 умножений.

>x^137 = x^128 * x^8 * x^1 итого всего 11 умножений

Считать я, конечно же, не умею :) Но логарифм есть логарифм.

Мне кажется, что наиболее правильно использовать следующую стратегию: двухсотпятидесятиричную двоичнокодированная система счисления - это фактически число, записанное парами шестнадцатеричными цифр - по две две цифры на байт. Таким образом, никаких потерь памяти при хранении нет, все операции очень просто реализуются, работая чисто с байтами. Более того, при таком подходе работает деление на степень двойки методом сдвига всего массива чисел на соответствующее число бит! А основные операции - сравнение, сложение, вычитание, умножение и деление просто реализуются. Например, сложение будет выражаться как-то так: С = A + B carry = 0 for( i = 0, i < len, i++) { ci` = ai + bi + carry; ci = ci` % 0xFF; carry = ci` / 0xFF; } ci = carry; Остальные операции будут не многим сложнее. Фактически везде реализуется школьные алгоритм столбика. А для вычисления НОД я бы рекомендовал использовать бинарный алгоритм Евклида. В таком случае для него не надо будет реализовывать алгоритм деления, который из всей этой группы будет наиболее сложным. Если надо линейное представление нода (например для вычисления мультипликативно обратного) - расширенный бинарный алгоритм Евклида. Для него тоже деление не надо. В итоге мне кажется, что такую арифметику - сравнение, сложение, вычетание и умножение + бинарный евклид - можно реализовать за день, если не торопиться.

ЗЫ почему-то бинарный расширенный алгоритм евклида оказался редкостью, я его довольно долго гуглил. Если понадобится, могу дать - он у меня на диске валяется.

да уж. По ходу я никогда не научусь абзацы на этом форуме делать..

>Берите остаток от деления вместо того, чтобы вычитать. По сути то же, но гора-аздо быстрее!

Это просто верх маразма. Ты когда-нибуть видел блоки аппаратного деления под микроскопом на risc ? Это большая редкость и занимает половину всего кристалла. Деление - одна из самых затратных простых операций.

Топикстартер - посмотри софтовую реализацию библиотеки для работы с многобайтными данными от любого 8-битного микроконтроллера - там все просто, главное нужны элементарные знания двоичной арифметики. Вообще достаточно одной операции сложения - вычитание - это сложение с двоичным дополнением, человеческий мозг кстати только складывать умеет. Все остальные операции - производные. Сейчас разве этому не обучают ?

Я такие вещи в школе писал, на олимпиадах по программированию. Делов на пару вечеров.

Не понимаю, о каких строках может идти речь. std::string в си? А char* - это в данном случае не строка, а массив unsigned char'ов. Длину и знак хранить отдельно.

+-*/ реализуй по школьным правилам "в столбик". Хорошие алгоритмы можно прикрутить позже, если останется время перед сдачей (преждевременная оптимизация - корень всех зол).

Основание системы счисления бери 10. Когда отладишь, можешь увеличить до 2^32-1 (изменив тип "цифр" на unsigned int), но учти, в каком виде будешь выводить. Человекам удобнее в 10м или 16ом.

Ты счас только что предложил свой велосипед под названием двоично-кодированный int :) тогда как про bcd уже давно говорили и этим г-ом кроме интела никто не увлекается. Ни о какой оптимизации с таким подходом и речи быть не может - можно сразу забыть про быстрое умножение/деление при помощи сдвигов. Тогда как в любом процессоре есть специальные команды для работы с многобайтными числами - сложение с переносом и вычитание с учетом заема на предыдущей операции, сдвиги через флаг переноса.

Какой вуз? ))

NTL/Miracl если не хочешь gmp

Прочитал коряво ) Придется тебе тогда действительно кнута смотреть

>> In real life такие люди редко что создают нового.

>Как можно создать что-то новое, когда не знаешь, как устроено старое??

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

>Это просто верх маразма.

Да, выше уже написали про бинарного Евклида, так что нафиг деление.

> Когда слишком хорошо знаешь старое

Ну зачем из крайности в крайность?