быстрое вычисление для расширенной точности с плавающей запятой для применения теории чисел

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

Проблема, с которой я сталкиваюсь, заключается в том, что мне нужно вычислять нормы, которые превышают 1e20 = 10 ^ 20, что превышает как целочисленную точность, так и точность с плавающей запятой моего оборудования (Macbook).

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

У меня два вопроса: Q1: Является ли моя оценка в 300 раз медленнее для программной эмуляции расширенной точности (скажем, до точности 10^36, примерно в два раза выше аппаратной) чрезмерно пессимистичной?

Q2: Есть ли у меня много тысяч долларов, чтобы решить проблему, какие аппаратные решения могут быть доступны?


hardware-acceleration floating-point floating-accuracy floating-point-precision
person John M    schedule 31.08.2013    source источник
comment
Я вижу минус. Я пишу здесь впервые, поэтому, если этот вопрос не подходит для этого форума, пожалуйста, укажите мне правильное направление или дайте мне знать, как я могу улучшить вопрос.   -  person John M    schedule 31.08.2013
comment
Не знаю насчет 300x. Я сделал 72-битное целое число в 16-битной сборке без заметной разницы, но мои вычисления не потребовали нескольких дней для запуска.   -  person ChiefTwoPencils    schedule 31.08.2013
comment
@BobbyDigital - Спасибо, Бобби.   -  person John M    schedule 31.08.2013
comment
Вещи, которые могли бы быть более понятными в вашем вопросе, чтобы вы могли получить наиболее полезный ответ: 1) почему вы вообще используете числа с плавающей запятой? Являются ли некоторые из чисел, которые вы умножаете, дробями? 2) если да, знаете ли вы, что если знаменатель не является степенью двойки (а иногда даже если это так), число с плавающей запятой не совпадает с рациональным, которое оно должно представлять? Такие вещи становятся заметными, если вы перемножаете их сотни, чтобы получить целое число. Вы можете получить не то целое число, которое ожидали.   -  person Pascal Cuoq    schedule 31.08.2013
comment
@PascalCuoq - Спасибо за помощь. Я умножаю иррациональные числа. И действительно, вы абсолютно правы в том, что не всегда получаете ожидаемое целое число, и именно поэтому я ищу дополнительную точность. Однако ответ BobbyDigital помогает мне. Возможно, реализация double-double или quad-double (а не произвольная точность) не будет иметь такой плохой производительности, как я опасаюсь.   -  person John M    schedule 31.08.2013
comment
Вы можете использовать библиотеку GMP и mpf_t или используйте библиотеку MPFR. поверх GMP.   -  person Brett Hale    schedule 31.08.2013
comment
@JohnM В единственном отчете, который я слышал о реализации quad-double, на которую вы, скорее всего, ссылаетесь, говорилось, что она была медленнее, чем MPFR для этого конкретного использования. Глядя на реализацию, это было не слишком удивительно. Эти библиотеки трипл-дабл и квадро-двойник могут быть очень эффективными, когда требуется немного меньше номинальной точности, и разумно использовать эту свободу действий, чтобы пропустить некоторые шаги нормализации и/или термины более низкого порядка. Обычная простая в использовании библиотека quad-double требует слишком много двойных операций, чтобы превзойти библиотеку с множественной точностью, основанную на целых числах.   -  person Pascal Cuoq    schedule 31.08.2013
comment
@BrettHale - Спасибо, Бретт. Мне еще не удалось успешно заставить GMP работать на моем Mac. Но это определенно вариант, который я рассматриваю. Я не уверен, насколько большим будет удар по производительности по сравнению со стандартной аппаратной операцией умножения с плавающей запятой. Вы имеете какое-нибудь представление об этом?   -  person John M    schedule 31.08.2013
comment
@JohnM Я использую MacPorts для установки библиотек Unix. Он позаботится о зависимостях, поэтому вам нужно будет только указать ему установить MPFR (sudo port install mpfr), и он позаботится об установке GMP. Это может привести к большему количеству зависимостей, чем вам хотелось бы, но пусть это работает, и обычно вы получаете то, что вам нужно.   -  person Pascal Cuoq    schedule 31.08.2013
comment
@PascalCuoq - этот совет MacPorts сработал прекрасно. Спасибо!   -  person John M    schedule 01.09.2013

Ответы (1)


arrow_upward
2
arrow_downward

Учитывая предоставленную вами информацию, я не вижу другого решения, кроме MPFR. Да, аппаратные вычисления с плавающей запятой дают результат раньше, но это неверный результат.

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

Два подхода к оценке требуемой точности — предварительный численный анализ и интервальная арифметика. Я ничего не знаю о численном анализе, но суть в том, что каждый иррациональный фактор представлен числом с плавающей запятой с множественной точностью, которое, как мы предполагаем, меньше 0,5 ULP, и каждое умножение может отличаться на 0,5 ULP от реального результата (произведения фактических операндов с плавающей запятой, а не того, что операнды должны представлять ). Людям проще рассуждать с точки зрения относительной точности.

Интервальная арифметика удваивает количество операций, но обеспечивает гарантированные границы реального результата. Если в вычисленном интервале есть только одно целое число, молодец! В противном случае начните снова с более высокой точностью.

Наконец, вы спрашиваете о скорости. Если у вас действительно есть только умножения, распараллелить вычисления тривиально, потому что умножение ассоциативно.

person Pascal Cuoq    schedule 31.08.2013
comment
Спасибо Паскаль. Я очень ценю ваши комментарии выше об относительных достоинствах quad-double по сравнению с GMP. - person John M; 31.08.2013