Как кодировать решение иметь дело с большими количествами?

Вам необходимо хранить большие числа в базе, которую ваш компьютер может легко обрабатывать с нативными типами, а затем хранить цифры в массиве переменной длины. Я бы посоветовал для простоты начать с хранения чисел в базе 10, чтобы получить представление о том, как это сделать. Это сделает отладку намного проще.

Как только у вас есть класс, который может хранить числа в таком виде, это просто вопрос реализации операций сложения, вычитания, умножения и т.д. над этим классом. Каждая операция должна будет выполнить итерацию над цифрами своих операндов и объединить их, аккуратно перенося так, чтобы ваши цифры никогда не были больше, чем база. Добавление и вычитание простые. Умножение требует немного больше работы, так как наивный алгоритм требует вложенных циклов. Тогда, как только это сработает, можно попробовать эффективно реализовать экспоненцию (например, повторное квадрационирование).

Если вы планируете написать серьезную реализацию бигнума, то база 10 ее не обрезает. Это пустая трата памяти и будет медленной. Вы должны выбрать базу, которая естественна для компьютера, например 256 или размер слова (2**32). Однако это усложнит выполнение простых операций, так как при наивном добавлении двух цифр вы получите переполнения, поэтому с этим нужно будет обращаться очень аккуратно.

C не является хорошим выбором для проекта Euler. Преимуществами C являются скорость работы, переносимость на машину (в некоторой степени со стандартным C), языковая совместимость (если один язык взаимодействует с другим, C является популярным первым выбором), близость к определенной библиотеке или API платформы (потому что C является обычным, например, OS API), а также стабильный язык и stdlib. Ни одно из этих преимуществ не применимо к решению задач Project Euler. Даже не сырая скорость, потому что большинство задач не связано с сырыми вычислениями, а с пониманием требуемого алгоритма, и вы можете сидеть там целый день и ждать перед отправкой.

Если вы пытаетесь решить проблемы с Project Euler, чтобы расширить свой опыт работы с C, это совершенно нормально, просто осознайте, что этот опыт не обязательно применим к долгоживущим и реальным проектам на C, над которыми вы можете работать.

Для такого рода коротких, одноразовых проблем те языки, которые обычно описывают как "языки сценариев", будут работать лучше, быстрее (во время разработки), и проще. Попробуйте Python, он остается близко к Си во многих отношениях, включая C API, и из различных популярных "скриптовых языков", возможно, именно тот, для которого Вы найдете наибольшее применение в сочетании с проектами на Си.

Это может стать непопулярным ответом, но это не runt-plus, мне действительно нравится Си и я часто использую Си/Си++, и здесь есть явный ответ на Вашу проблему: "не используйте Си", с Вашим окончательным решением в большом количестве, в зависимости от того, какую альтернативу Вы выберете. Опять же, выбирая Python, целые числа не имеют верхней границы (примечание ниже), и я использую это, чтобы естественным образом кодировать ответы на проблемы Project Euler, где в других языках я должен использовать болезненную по сравнению альтернативную библиотеку чисел.

(Python integers: В 2.x есть два целых типа, 'int' и 'long' (которые были полностью унифицированы в 3.x). Приведение между ними практически бесшовно, а 'long' позволяет получать произвольно большие значения, вместо того, чтобы быть просто большим типом 'int', как у С long)

Популярной библиотекой бинумов для C/C++ является GNU MP Bignum Library. Я использовал ее для нескольких задач Project Euler, но факт остается фактом, что Си не очень подходящий язык для задач Euler. Если бы производительность была более важной, то Си мог бы дать больше, но сейчас гораздо лучше использовать язык, встроенный в поддержку bignum, такой как Ruby (есть много других).

Простой способ - думать о числе как о его строковом представлении в базе b. Допустим, b=10, простая арифметическая операция, такая как сложение на двух таких строках, может быть выполнена тем же самым методом, который мы используем при сложении чисел ручкой и бумагой. То же самое относится и к другим простым операциям. Для лучшего результата можно взять большую базу.

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

Хотя я рекомендую написать свою собственную бину для практики, если вы действительно застряли, то вы можете взять идеи из кода уже реализованных bigint библиотек. Для серьезной реализации что-то вроде gmp - очевидный выбор. Но вы также можете найти мелкие bigint, закодированные другими людьми при решении подобных практических задач в сети (например, Abednego's bigint.cpp).

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

Для более продвинутых вещей посмотрите GMP.

Если вы хотите хорошую версию на C++ (я знаю, вы сказали C, но это действительно интересный код), взгляните на внутреннюю часть CGAL: http://www.cgal.org/

Я полностью согласен с Роджером Пейтом. Я много раз видел людей, сталкивающихся с проблемой целочисленных лимитов с C/C++/Java, но с Python это не проблема. Для большинства проблем Project Euler наиболее важно придумать правильный алгоритм, и производительность, которую вы получите от C, не будет иметь большого значения. Более того, с ассоциативными типами данных, словарем, набором и т.д., доступными на Python, а также с некоторыми встроенными библиотеками, итертуалами, просто чтобы назвать одну из них, гораздо быстрее решить проблему с Python. Я начал всерьёз изучать Python с тех пор, как прыгнул в проект Euler bandwagon, и был доволен своим решением (мой первый язык - C++, второй - Perl, но я хотел выучить Python)