Где в решении задачи ошибка?

Никита Подосёнов, цикл гоните с 2, а не с 0. Перед циклом отсортируйте a,b и c,d.

Вызов функции C в другом файле. Как реализовать?

Оберните, пожалуйса, код в тег code - кнопка </> в редакторе. И расставьте отступы.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, Не упускаю я ценность. Просто мне вот вообще не понятно, как эту идею применить к этой задаче (из-за размера и длинной арифметики). Думал, вы что-то знаете, чего не знаю я. Ведь вы такие слова умные говорите. Но вы просто ошиблись на пару десятков порядков.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Просят метод, который работает для некоторого такого числа

Тогда на надо даже никаких таблиц! У меня есть алгоритм - return true; или return false;. Но мы пока не знаем какое именно число нужно, поэтому точнее сказать не могу.

А поиск быстрее вычисления.

В некоторых случаях. Далеко не всегда.

заменить извлечение корня на возведение в степень

Вот только в этой задаче (длинная целочисленная арифметика) умножение двух чисел делается почти также медленно, как и извлечение корня.

А дальше я предложил пример алгоритма, который на интервале использует линейную аппроксимацию

Опять забыв про длинную арифметику. Потому что деление в этой аппроксимации медленнее умножения или всего вычисления корня.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, От длины какого интервала? Входное число может быть от 1e49 до 1e50-1. В вопросе не сказано, "определите, является ли это конкретное число квадратом?". Просят метод, который работает для 100-значного числа (любого).

И для каждого возможного входного числа ваш алгоритм с таблицей должен работать. Если вы не хотите считать все квадраты в этом интервале, что нереально - их 1e49, то вы должны как-то строить таблицу на основе входного числа.

Раз в таблице у вас хранятся квадраты, то в вашем алгоритме надо находить очень близкие к n квадраты или числа очень близкие к корню n. Как это делать вы так и не написали. Но даже если вы это напишете, то смысла в таблице уже нет! Раз вы можете найти очень близкие числа к ответу, то ничего не мешает тупо вычислить сам корень этим же методом.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, Вы явно запутались, да. В том-то и дело, что у вас идея, которая вам как бы ясна, но до деталей вы ее не продумали. И вопрос не поняли до конца (это задача на длинную арифметику).

И я опять повторяю, эта идея с таблицей хорошая и она работет, когда мы разбиваем небольшой интервал на части. В этой же задаче - 10^49 чисел. Никакое разбитие тут не будет работать сколько-нибудь вменяемо.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks,

Иными словами, я покрываю диапазон 2pdp+dp^2=24e50 чисел (а это достаточно много)

Это смехотворно мало. Это диапазон по полным числам, их там 1e100. Вы покрыли 1e-50 часть. Отлично. Как я и говорил, вам надо в таблице 1e50 чисел.

Проблема в том, что интервал [p, p+100] не покрывает корень из заданного мной числа. Этот корень примерно равен 3.489202344376147e+49. Таких интервалов длины 100 вам надо будет отложить еще примерно 2*10^47, прежде чем вы найдете нужный интервал. Если же вы хотите уложиться в хотя бы 10^12 интервалов, то каждый из них должен быть длиной 10^37 чисел. И уже не такая большая разница, считать ли 37 знаков корня, или все 50. Все-равно вычисление корня будет на много порядков быстрее поиска по этой таблице.

> Таким образом можно заменить операцию извлечения корня на более простую операцию деления

Вы вообще представляете, как работает длинная арифметика целых чисел? Извлечение корня, например, методом бинарного поиска, как в моем ответе, работает практически также быстро (если не быстрее) чем деление двух длинных чисел - O(L^2), где L - длина числа. Деление будет быстрее, только если у вас число помещается в регистры процессора целиком и есть аппаратная инструкция для деления. В этой задаче нужна точность все 100 знаков, так что float идет мимо.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, Отлично, Сколько там чисел в этой таблице?!

Вот вам конкретное входное число, целиком заданное - 12174533.....(тут 90 нулей)...42.

Какая у вас таблица там? Если вы думаете, что можно как-то ограничить ее небольшим интервалом вокруг входного числа - то у вас циклическая зависимость. Для этого вам надо будет прикинуть корень из числа. Чем менее точно вы его вычислите, тем больше будет таблица. Чтобы у вас таблица влезла хотябы в терабайт памяти надо подсчитать более 40 знаков корня. В этом случае досчитать оставшиеся 10 тем же методом будет быстрее и проще чем искать по этой террабайтной таблице (не говоря уже о ее вычислении).

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks,

Составим таблицу: 1,9,36,81,169.

Отлично, а теперь берем число 12174533.....(тут 90 цифр)...42. Эта таблица нам нисколько не помогает. Вообще. Можно было и без нее догадаться, что левая граница интервала что-то порядка 50 цифр в числе.

Как использовать таблицы для маленьких чисел и без вашего объяснения очевидно. Вот что делать со сто-значными - вот вопрос.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, нет, мы говорим о конкретном множестве чисел - 100-значные, как в вопросе.

> однако мы можем бесплатно получить интервальную оценку + точку отсчёта для других алгоритмов

Ну приведите конкретный пример уже.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, В вопросе:

является ли некоторое огромное число (от 100 знаков) квадратом

Различных квадратов из 100 цифр примерно 7*10^49. Если нет какого-то дополнительного условия, что проверяемое число лежит в каком-то маленьком диапазоне, то единственный способ хоть как-то использовать таблицы - хранить все квадраты или битовую маску для всего интервала (что совсем ни в какие ворота не лезет). Ну даже если вы придумаете, как хранить лишь 1/10000000 из квадратов, все-равно их остается охренительно много.

И это все только для 100-значных входных чисел. А в вопросе "от 100 знаков".

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, это все очень хорошо, но там 10^49 квадратов. Читайте вопрос внимательнее. 100 цифр в числе. Если по 0.000001 биту на квадрат тратить с офигительным сжатием, то всех хранилищ человечества все-равно не хватит.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Диапазон в сто цифр. Там корней около 7*10^49. Жирная мапа получается.

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

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

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Griboks, и как же грамотно составить таблицу, чтобы ускорить решение для чисел в сто знаков!? Это очень интнресно.

Перевод фото таблицы в матрицу из 0 и 1?

Антон Шаманов, Это я к тому, что этому вопросу место не в "алгоритмы", а в "учимся программировать для самых маленьких".

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

но там же сотня знаков, никакая таблица не справится. И по вашей ссылке вычисление обратного к корню, а не корня, от числа с фиксированной точностью.

Как это работает в c++?

Rsa97, Да, пример лучше работает, когда делим на целую переменную, а не на константу.

Как это работает в c++?

IIggoorrII, Нет. Неявное приведение типов. Еще, например, можно сделать

int a = 10;
double b = (a + 0.0) / 20;  // b == 1/2

Прибавление 0.0 приводит целочисленные типы к соответствующему вещественному. Без +0.0 было бы целочисленное деление и результат был бы 0.

Как можно написать алгоритм, который по первому заданному числу определяет кол-во чисел, которые ты сможешь ввести?

Roman Razumovich, Ну тогда код, который "по заданному числу определяет кол-во чисел, которые ты можешь ввести" - тривиален. Это само заданное число и есть кол-во чисел "которые ты можешь ввести".