Деление 1 на огромное целое

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

В качестве примечания, я хотел бы реализовать алгоритм самостоятельно, без использования сторонней библиотеки.

У кого-нибудь есть идеи?

Спасибо!

EDIT: причина, по которой я не хочу использовать стороннюю библиотеку, заключается в том, что я хочу выполнить эту операцию с помощью openCL, но без потери точности в процессе. Поэтому использование одной из этих библиотек в данном случае фактически невозможно.


algorithm floating-point opencl
person Ignacio A. Rivas    schedule 20.07.2011    source источник
comment
Что ж, с точки зрения пуристов, у вас уже есть наиболее точное представление этого числа — 1 / <The number in the string>.   -  person Justin    schedule 20.07.2011
comment
В Википедии есть отличный обзор этой темы со ссылками на множество сторонних библиотек, которые вы можете изучить, чтобы получить представление о собственной реализации en.wikipedia.org/wiki/Arbitrary-precision_arithmetic   -  person Eric J.    schedule 20.07.2011
comment
Просто сделайте quotient = 0.0;. Обратная величина 4000-значного целого числа слишком мала, чтобы ее можно было представить в виде double.   -  person dan04    schedule 20.07.2011
comment
Что представляют собой эти 4000 (!) цифр, кардинальное число? Какая точность вам нужна в результате?   -  person Martin James    schedule 20.07.2011
comment
@Eric: ИМО, это может быть ответ на вопрос, а не просто комментарий.   -  person Vincent Mimoun-Prat    schedule 20.07.2011
comment
Мне нужно, чтобы алгоритм был максимально точным при выполнении этого деления, поэтому мне нужны все десятичные дроби операции.   -  person Ignacio A. Rivas    schedule 20.07.2011
comment
treskal.com/kalle/exjobb/original-report.pdf   -  person    schedule 20.07.2011
comment
Что ж, в C++ нет встроенного типа с такой точностью, так что в этом отношении вы SOL.   -  person Jonathan Grynspan    schedule 20.07.2011
comment
@Ignacio: в общем, может быть бесконечное количество десятичных знаков. Вам нужно либо определиться с пределом, либо, если вам нужна бесконечная точность, работать с рациональными числами.   -  person Mike Seymour    schedule 20.07.2011
comment
4000 - странное количество цифр. Есть ли шанс, что вы могли бы представить цифры в битах? Этот ответ содержит некоторые подсказки: больших чисел   -  person    schedule 20.07.2011
comment
@Grynspan: в C++ нет встроенного типа для деревьев, кольцевых буферов или пакетов TCP. Это не значит, что нет библиотек, которые уже делают это!   -  person Nowhere man    schedule 20.07.2011
comment
-1 Этот вопрос показывает незначительные исследовательские усилия и налагает произвольные ограничения (без сторонних библиотек) без каких-либо объяснений. Некоторое уточнение того, почему вы пытаетесь сделать что-то столь необычное и что вы уже пробовали, сделало бы этот вопрос намного лучше.   -  person Dan J    schedule 20.07.2011
comment
Я дал +1 dan04, но плавающая запятая не обязательно означает IEEE754. Это даже относится к нормальной форме/научной нотации/к чему бы то ни было. Я не знаю, будет ли это правильным использованием или нет, но это будет понятной ошибкой. Небольшая работа с арифметической библиотекой произвольной точности должна быть в состоянии генерировать пригодный для использования результат в нормальной форме, но есть большая вероятность, что после точки будет бесконечное количество цифр, поэтому нет максимально точного числа Должна быть выбрана точка отсечки значащих цифр.   -  person Steve314    schedule 20.07.2011
comment
-1 Такой плохо составленный вопрос ... пытался помочь, но теперь пришлось переименовать весь вопрос, потому что он был помечен как C # / C ++, чтобы, вероятно, привлечь больше внимания из-за популярности этих тегов.   -  person    schedule 20.07.2011
comment
4000 цифр — это очень мало по сравнению с этим primes.utm.edu/largest.html :D   -  person ascanio    schedule 20.07.2011
comment
@Нигде, чувак, которого я знаю, но ему не нужны сторонние библиотеки. Итак, мы вернулись ни к чему встроенному.   -  person Jonathan Grynspan    schedule 20.07.2011
comment
Для ничего не встроенных комментаторов — верьте или нет, алгоритмы — это то, что вы можете реализовать для себя и даже ответить на вопросы о них.   -  person Steve314    schedule 20.07.2011

Ответы (4)


arrow_upward
10
arrow_downward

Вы описываете частный случай деления, известный как инвертирование числа. Вот статья, в которой дается описание метода итерации Пикарта для инвертирования большого целого числа: http://www.dcc.uchile.cl/~cgutierr/ftp/picarte.pdf

person Mark Ransom    schedule 20.07.2011
comment
Это именно то, что я искал, большое спасибо, Марк! - person Ignacio A. Rivas; 20.07.2011

arrow_upward
2
arrow_downward

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

Что касается самостоятельной реализации, если это не в образовательных целях, я бы сказал, не становитесь жертвой синдрома НИЗ! И поиск в Интернете по binary arithmetic должен предоставить множество документов для начала…

person Nowhere man    schedule 20.07.2011
comment
Полностью согласен. Это немного похоже на синдром NIH. - person Rudy Velthuis; 20.07.2011
comment
Иногда есть причины для синдрома NIH - например, проблемы с лицензией. Я частично уважаю, что Игнасио также может не хотеть всю GNU MP, даже если лицензии не являются проблемой, но извлечение соответствующих битов все же было бы разумным и просмотр источника, чтобы увидеть, какой алгоритм (ы) он использования кажется разумной идеей. - person Steve314; 20.07.2011
comment
Конечно, есть причины для синдрома NIH. Но в этом случае существует достаточно библиотек с открытым исходным кодом, использующих лицензию, которая не ограничивает использование закрытого исходного кода. - person Rudy Velthuis; 20.07.2011

arrow_upward
1
arrow_downward

Вы должны использовать структуру System.Numerics.BigInteger, он позволяет вам выполнять множество вычислений, однако он доступен только в .NET 4.0.

person Waleed    schedule 20.07.2011
comment
У меня уже есть число, сопоставленное со строкой, и снова я хочу реализовать алгоритм деления самостоятельно, без использования другого типа данных, такого как BigInteger, GNU-BC или GMP. - person Ignacio A. Rivas; 20.07.2011
comment
Почему самостоятельно? Это домашнее задание? Если вы пишете код производственного уровня, то почему бы вам не использовать существующую и хорошо протестированную библиотеку? Это решаемая проблема. Кроме того, если вы уже используете .NET 4.0, то это не значит, что вы импортируете какую-то новую стороннюю библиотеку, она уже есть для вас. - person Ed S.; 20.07.2011
comment
Разве BigInteger не только для целых чисел? Я думаю, ему нужен результат с плавающей запятой. - person Can Poyrazoğlu; 20.07.2011
comment
Это не домашнее задание, я просто хочу запустить эту операцию с помощью openCL, не теряя при этом особой точности. Поэтому использование одной из этих библиотек в данном случае фактически невозможно. - person Ignacio A. Rivas; 20.07.2011
comment
@can: результат с плавающей запятой. - person ; 20.07.2011
comment
@Игнасио: openCL - это не C #. Почему это помечено как C#? - person ; 20.07.2011
comment
@ 0A0D: 1/(число из 4000 цифр) имеет ли оно смысл как число с плавающей запятой? Деление BigInteger будет иметь дело только с целыми числами и усекаться после десятичной точки (в документации MSDN это четко указано), и ДАЖЕ ЕСЛИ вы можете выполнить деление с истинной плавающей запятой, результат будет фактически 0 как с плавающей запятой, ему нужно больше точность, что-то вроде класса BigFloatingPoint. - person Can Poyrazoğlu; 20.07.2011
comment
@can: он говорит, что усекается только после создания экземпляра. В нем не упоминается разделение. В любом случае, это все спорный вопрос, так как вопрос не имеет никакого отношения к C#. msdn.microsoft.com/en-us/library/dd268345.aspx - person ; 20.07.2011
comment
@ 0A0D: я не вижу НИКАКИХ практических применений BigInteger в отношении этого вопроса. В любом случае, я комментировал родительский ответ, а не вопрос. - person Can Poyrazoğlu; 20.07.2011
comment
@can: Я не думаю, что ты понимаешь, о чем говоришь, ни с какой точки зрения. - person ; 20.07.2011
comment
@0A0D: давайте назовем это непониманием того, что я говорю, из-за того, что я не читал то, что я написал (или, по крайней мере, я хочу в это верить), вместо того, чтобы флеймить, пожалуйста, приведите рабочий пример использования класса .NET Framework BigInteger, который может помочь с обработкой числа в диапазоне 1/(4000 цифр). - person Can Poyrazoğlu; 20.07.2011
comment
@can: диапазон 1/4000 цифр не имеет смысла. Во всяком случае, BigInteger — это неизменяемый тип, представляющий произвольное большое целое число, значение которого в теории не имеет верхней или нижней границы. Поскольку вы тот, кто заявляет, что это не работает, я ожидаю, что вы приведете пример. Я также предлагаю вам изучить BigInteger в MSDN. - person ; 20.07.2011
comment
@0A0D: я знаю, что такое BigInteger, и работал с ним раньше. Я знаю, что большое целое не имеет границ, но как представить 1/(любое целое число, кроме 1) как целое число? Результатом будет число с плавающей запятой, и независимо от того, представите ли вы знаменатель с 4000 цифрами с помощью BigInteger, 1/(это число) БУДЕТ быть с плавающей запятой, которую вы НЕ МОЖЕТЕ представить, и любой float/double/Decimal представления будут фактически равны нулю, а не 0,000000000... (поскольку вы делите на 4000-значное число). Я не понимаю, как BigInteger помогает решить проблему. Вы используете BigInt для 4k цифр, а не 1/4k цифр - person Can Poyrazoğlu; 20.07.2011

arrow_upward
1
arrow_downward

Если ваше число X является целым числом, вы, возможно, не сможете делать то, что хотите. float и double почти отсутствуют; вам придется использовать long double. На некоторых платформах long double — это просто double.

Если вы не хотите использовать сторонний пакет bignum (почему?), вам придется реализовать алгоритм деления самостоятельно (и это в значительной степени потребует от вас разработки хорошего пакета bignum) .

person David Hammen    schedule 20.07.2011
comment
Даже long double не имеет требуемой точности. - person Jonathan Grynspan; 20.07.2011
comment
@ Джонатан: я согласен. Я предполагаю, что он хочет этого для представления (например, вывода), а не для расчета. - person David Hammen; 20.07.2011
comment
Я не думаю, что он знает, чего хочет. Он только что упомянул openCL в другом ответе. - person ; 20.07.2011