Вычисление квадратного корня для чрезвычайно больших чисел в C

Решаю какие-то задачи из школьных олимпиад и застрял на одном вопросе. Я нашел решение задачи, но мое решение требует извлечения квадратного корня. Мой код отлично работает для первых 12 входов, но затем дает неправильные ответы. Я предполагаю, что это связано с чрезвычайно большими входными данными, которые могут достигать 10 ^ 400000. Поэтому я хотел бы знать, есть ли способы вычислить целые части квадратных корней этих чрезвычайно больших входных данных в C. Вот код:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int main(){
    long long n;
    scanf("%lld", &n);
    long long ans;
    ans = sqrtl(n-1);
    long long result;
    result = ans+1-llabs(n-ans*ans-(ans+1));
    printf("%lld\n", result);
    return 0;
}

c algorithm math limits
person ar kang    schedule 09.01.2018    source источник
comment
Определите чрезвычайно большой. Вы имеете в виду больше, чем 2 ^ 64? Если это так, вы не можете сделать это с помощью long long, и вам понадобится какая-нибудь библиотека bignum.   -  person tadman    schedule 09.01.2018
comment
Идея такой задачи состоит не в том, чтобы использовать встроенные sqrt функции, а в том, чтобы использовать собственный алгоритм.   -  person Eugene Sh.    schedule 09.01.2018
comment
@tadman: 10 ** 400000, вероятно, больше :)   -  person Jean-François Fabre    schedule 09.01.2018
comment
@tadman в задаче сказано, что ввод может достигать 10 ^ 400000   -  person ar kang    schedule 09.01.2018
comment
@ Jean-FrançoisFabre Может быть, я не силен в математике, но я думаю, что очень высока вероятность того, что она будет слишком большой для 64-битного int.   -  person tadman    schedule 09.01.2018
comment
очень высокий, как 100% :)   -  person Jean-François Fabre    schedule 09.01.2018
comment
Вам придется исследовать алгоритмы извлечения квадратного корня и реализовывать собственное решение, если вам не разрешено использовать сторонние библиотеки. См. также этот подход.   -  person tadman    schedule 09.01.2018
comment
@ Jean-FrançoisFabre Я собираюсь использовать 99,99999999...%, просто на всякий случай.   -  person tadman    schedule 09.01.2018
comment
@tadman: лучше перестраховаться, чем сожалеть. Тем не менее, sqrt(10**400000) = 10**200000.   -  person Jean-François Fabre    schedule 09.01.2018
comment
10 ** 400000 примерно в 542101086242752217003726400434970855712890625000[...399930 zeroes redacted...]000 раз больше, чем максимальное значение, подходящее для uint64_t.   -  person Antti Haapala    schedule 09.01.2018
comment
Такой большой, как 10^400000?! Вы уверены, что не имеете в виду 10^40? Большие значения не могут быть представлены в нативных типах, даже long double. Вам придется использовать стороннюю библиотеку bignum или научиться реализовывать свою собственную.   -  person John Bode    schedule 09.01.2018
comment
@chrisz нет, 10 ^ 400000 - это просто ограничение, ввод может быть любым числом от 1 до 10 ^ 400000   -  person ar kang    schedule 09.01.2018
comment
@JohnBode Я бы даже спросил, как это можно использовать в качестве входных данных ..   -  person Eugene Sh.    schedule 09.01.2018
comment
@ЕвгенийШ. 400 тысяч цифр? Это легко вписывается в строку.   -  person melpomene    schedule 09.01.2018
comment
@EugeneSh.: Разве у всех нас нет пары часов, чтобы набрать до 400000 цифр?   -  person John Bode    schedule 09.01.2018
comment
@JohnBode К сожалению, это 10 ^ 400000.   -  person ar kang    schedule 09.01.2018
comment
@arkang: Йи-ха. Вы захотите просмотреть это   -  person John Bode    schedule 09.01.2018
comment
Число выражается в виде 10^n? Если это так, это может быть довольно легко.   -  person tadman    schedule 09.01.2018
comment
@tadman нет, если бы это было 10 ^ n, это действительно было бы легко   -  person ar kang    schedule 09.01.2018
comment
Даже если вам придется свернуть свой собственный, я бы абсолютно уверен, что сверюсь с эталонной реализацией, такой как GMP.   -  person tadman    schedule 09.01.2018
comment
@tadman я обязательно проверю   -  person ar kang    schedule 09.01.2018
comment
@tadman Как вы думаете, сколько времени займет такой расчет с GMP (просто любопытно, никогда не работал с ним)? В любом случае, я почти уверен, что ОП неправильно понял задание.   -  person Eugene Sh.    schedule 09.01.2018
comment
@ЕвгенийШ. Мое предположение было бы мгновенным. Не понимаю, что такого диковинного в задании.   -  person melpomene    schedule 09.01.2018
comment
@melpomene Это зависит от используемого алгоритма и эффективности представления bignum. Существует подход бинарного поиска, который не должен быть слишком суровым.   -  person tadman    schedule 09.01.2018
comment
@tadman А? Это просто mpz_sqrt(result, input);.   -  person melpomene    schedule 09.01.2018
comment
но тогда он дает неправильные ответы. --› Опубликовать введенное число, результат и ожидаемый результат.   -  person chux - Reinstate Monica    schedule 10.01.2018
comment
@chux проблема в том, что входные данные неизвестны   -  person ar kang    schedule 10.01.2018
comment
Примеры сообщений из моего кода отлично работают для первых 12 входных данных, особенно тех, которые дают неправильные ответы.   -  person chux - Reinstate Monica    schedule 10.01.2018
comment
@chux пользователь может видеть результаты ввода (правильно, ошибка ограничения времени или неправильный ответ) и время, затраченное на выполнение, но не сам ввод или ответ.   -  person ar kang    schedule 10.01.2018
comment
Почему в коде используется abs(int) вместо правильного llabs(long long int j)? В этом проблема?   -  person chux - Reinstate Monica    schedule 10.01.2018
comment
@arkang Ваши цели кодирования должны иметь некоторое описание синтаксиса, диапазона входных данных и ожидаемых результатов.   -  person chux - Reinstate Monica    schedule 10.01.2018
comment
о, я забыл исправить это здесь, потому что я скопировал из блокнота, но когда я отправил ответ, я использовал llabs, так что это не проблема   -  person ar kang    schedule 10.01.2018
comment
@arkang Любой другой вымышленный код? - Опубликуйте свой истинный код. предложить вырезать и вставить.   -  person chux - Reinstate Monica    schedule 10.01.2018
comment
@chux Думаешь, это поможет? Потому что цель вопроса не в том, чтобы получить решение задачи, которую я делаю, а просто в том, чтобы получить некоторые идеи о том, как бороться с этими сумасшедшими числами.   -  person ar kang    schedule 10.01.2018
comment
@arkang Да, это поможет. Проблема в том, что вы только описали сумасшедшие цифры и не опубликовали ни их результаты, ни ожидаемый результат. Публикация истинных входных данных, выходных данных и ожидаемых выходных данных очень помогает. Без этого посту не хватает полезной информации.   -  person chux - Reinstate Monica    schedule 10.01.2018

Ответы (1)


arrow_upward
0
arrow_downward

В двух словах, вы можете свернуть алгоритм длинного квадратного корня дихотомическим методом следующим образом:

  • выбрать представление длинного числа (массив целых чисел без знака);

  • реализовать длинное сложение и вычитание (довольно тривиально, за исключением переносов);

  • реализовать халвинг (также требует ухода за керри);

  • реализовать длинное сравнение (аналогично вычитанию).

[Обратите внимание, что сложение позволяет реализовать удвоение и учетверение, а деление пополам также дает деление на четыре.]

Затем установите d= 1 и многократно удваивайте d до d² > N. (Каждый раз, когда вы удваиваете d, вы учетверяете d².)

Далее установите a= 0 так, чтобы инвариант

a² ≤ N < (a + d)²

устанавливается, и многократно уменьшайте вдвое d, сохраняя инвариант. Это достигается за счет

d= d/2; если N < (a + d)², установить a= a + d; в противном случае оставьте a без изменений.

В конце концов, вы сузитесь до

a² ≤ N < (a + 1)²

так что a является целым квадратным корнем.

Для оценки состояния

N < (a + d)² = a² + 2ad + d²,

or

N - a² < 2ad + d²,

достаточно отслеживать термины N - a², 2ad и d² и обновлять их по мере изменения d или a. Это требует только вышеупомянутых примитивных операций.

person Yves Daoust    schedule 09.01.2018