Я выполняю некоторые проблемы Project Euler и большую часть времени вычисляет большие числа за пределами int, float, double и т.д.
Во-первых, я знаю, что мне нужно искать более эффективные способы расчета, чтобы избежать проблемы с большим количеством. Я слышал о библиотеках Bignum.
Но для академических интересов я хотел бы знать, как закодировать мое собственное решение этой проблемы.
Может ли какой-нибудь эксперт помочь мне? (Мой язык - C)
Вам нужно сохранить большие числа в базе, которую ваш компьютер может легко обрабатывать с помощью собственных типов, а затем хранить цифры в массиве переменной длины. Я бы предположил, что для простоты вы начинаете с хранения чисел в базе 10 только для того, чтобы понять, как это сделать. Это облегчит отладку.
Как только у вас есть класс, который может хранить числа в этой форме, это просто вопрос реализации операций add, subtract, multiply и т.д. в этом классе. Каждой операции придется перебирать цифры своих операндов и объединять их, соблюдая осторожность, чтобы ваши пальцы не превышали основания. Сложение и вычитание просты. Для умножения требуется немного больше работы, так как наивный алгоритм требует вложенных циклов. Затем, как только вы начнете работать, вы можете попытаться эффективно выполнить возведение в степень (например, повторное возведение в квадрат).
Если вы планируете написать серьезную реализацию bignum, база 10 не будет ее обрезать. Это расточительство памяти, и оно будет медленным. Вы должны выбрать базу, которая является естественной для компьютера, например 256 или размер слова (2 ** 32). Однако это упростит выполнение простых операций, так как вы получите переполнение, если вы наивно добавите две цифры, поэтому вам нужно будет обработать это очень осторожно.
C не является хорошим выбором для Project Euler. Преимущества C - необработанная скорость, переносимость машины (в некоторой степени со стандартным C), языковая совместимость (если какой-то язык взаимодействует с другим, C - популярный первый выбор), придерживаясь рядом с конкретной библиотекой или API платформы (поскольку C является обычным явлением, например OS API), а также стабильным языком и stdlib. Ни одно из этих преимуществ не относится к решению проблем Project Euler. Не слишком высокая скорость, поскольку большинство проблем связаны не с необработанными вычислениями, а с пониманием требуемого алгоритма, и вы можете сидеть там весь день и ждать перед отправкой.
Если вы пытаетесь решить проблемы Project Euler, чтобы расширить свой опыт с помощью C, это прекрасно, просто осознайте, что этот опыт не обязательно относится к долгосрочным и реальным проектам C, над которыми вы можете работать.
Для такой короткой одноразовой проблемы те языки, которые обычно описываются как "языки сценариев", будут работать лучше, быстрее (в режиме dev) и проще. Попробуйте Python, он по-прежнему близок к C, включая C API, и из разных популярных "языков сценариев", возможно, тот, который вы найдете наиболее употребительным в сочетании с проектами C.
Это может стать непопулярным ответом, но это не rant — плюс мне действительно нравится C и часто используется C/С++ — и здесь есть явный ответ на вашу проблему: "не используйте C", с ваше окончательное решение большого количества в зависимости от выбранной вами альтернативы. Опять же, выбирая Python, целые числа не имеют верхней границы (примечание ниже), и я использую это, чтобы естественно набирать ответы на проблемы Project Euler, где на других языках мне приходится использовать альтернативную библиотеку с больным сравнением.
(Целые числа на Python: два типа целых чисел в 2.x, 'int' и 'long' (которые были полностью унифицированы в 3.x). Преобразование между ними практически бесшовно, а "long" позволяет произвольно больших значений, вместо того, чтобы просто быть более крупным "int", как C long.)
Простым способом является представление числа как его строкового представления в базе b. Предположим, что b = 10, простая арифметическая операция, такая как добавление на две такие строки, может быть выполнена с использованием того же метода, который мы используем при добавлении чисел ручкой и бумагой. То же самое касается других простых операций. Для получения лучших результатов вы можете получить большую базу.
Для большинства задач Project Euler должно быть достаточно простой реализации бигнама, возможно, все, но я не много решил в Euler, поэтому не могу быть уверенным, но есть способы использовать гораздо более быстрые алгоритмы для таких операций как умножение и деление/мода.
Хотя я рекомендую писать свой собственный bignum для практики, если вы действительно застряли, вы можете взять идеи из кода уже реализованных библиотек bigint. Для серьезной реализации что-то вроде gmp является очевидным выбором. Но вы также можете найти небольшие бинты, закодированные другими людьми при решении аналогичной проблемы в Интернете (например, Abednego bigint.cpp).
Популярной библиотекой bignum для C/С++ является библиотека GNU MP Bignum. Я использовал его для нескольких проблем Project Euler, но факт остается фактом: C не очень подходит для проблем Эйлера. Если производительность была более важной, C было бы больше, но теперь вам гораздо лучше использовать язык, который построен в поддержке бигмуна, например Ruby (есть много других).
Вот хороший и простой модуль bignum для C. Вы можете учиться на нем для идей. Код C не является самым высоким качеством, но алгоритм хорошо реализован и довольно распространен.
Для более продвинутых вещей найдите GMP.
Если вам нужна хорошая версия на С++ (я знаю, вы сказали C, но это действительно интересный код), посмотрите на внутренности CGAL: http://www.cgal.org/
Я полностью согласен с Роджером Пате. Я видел много раз, когда люди сталкивались с проблемой с целым числом с C/С++/Java, но с Python это не проблема. Для большинства проблем Project Euler наиболее подходящим является правильный алгоритм, и производительность, получаемая с C, не будет иметь большого значения. Кроме того, с ассоциативными типами данных, словарем, набором и т.д., Которые доступны в Python и некоторыми встроенными библиотеками, itertools, просто для того, чтобы назвать один, гораздо быстрее решить проблему с Python. Я начал серьезно изучать Python, так как я прыгнул на победителя Project Euler, и я был доволен своим решением (мой первый язык - С++, второй язык - Perl, но я хотел изучить Python).