Вопрос состоит из 2 частей, т.к. отсутствие одного пути влечет за собой переход к другому.

В C# есть такая штука: структура System.Numerics.BigInteger для работы с большими числами. Вот только там нет среди методов функции взятия корня. Степени только целые есть.
И какой же метод использовать, если нужно взять корень?
Ну допустим, что корня нет. Тогда мы можем сделать таблицу со значениями квадратов чисел. И дальше искать по ней на совпадение.
Например, если число имеется в таблице, то мы знаем, что корень из него - целое число.
Насколько быстр поиск по такой отсортированной таблице?
Например, у меня есть таблица квадратов чисел от 1 до миллиарда, и мне нужно проверить, есть ли там это число.
Как лучше такую таблицу хранить в C#, и как искать по ней? Быстрее ли это будет, чем брать корень?

Вообще-то есть куча более разумных алгоритмов вычисления квадратного корня, чем поиск по таблице квадратов, вот парочка методов из
википедии, хотя я советую использовать метод Ньютона, не зря он на уровне процессора используется, ибо очень быстрая сходимость у него.

Это сообщение отредактировал(а) source777 - 7.12.2009, 20:03

Меня интересует самый быстрый метод из имеющихся в наличии готовых. Насколько сильно отличается быстродействие поиска по таблице и таких методов? Вы знаете готовые функции извлечения корня?
Кстати, понадобится могут и другие корни, не только квадратные.

Добавлено через 3 минуты и 22 секунды
По сути, проверка по таблице квадратов позволяет проверить, целый ли корень, а само число не обязательно нужно. Мне так и нужно для начала.

"Самый быстрый" это не математическое понятие, понятно же, что многое зависит от числа, корень которого надо найти.
Но метод Ньютона определённо один из самых быстрых для больших N. Кроме того он подходит для поиска действительных корней практически любого уравнения, а уравнение для вычисления квадратного корня x*x - N = 0  это лишь частный случай.
Вот пример применения этого метода конкретно для вычисления квадратного кода: http://e-maxx.ru/algo/roots_newton


Это сообщение отредактировал(а) source777 - 7.12.2009, 21:53

Спасибо. Еще бы понять, как переделать этот алгоритм на C# с использованием имеющихся в распоряжении функций.

Ты видимо имел в виду "записать", что-то переделывать там нет необходимости. А уж записать готовый алгоритм на известном тебе языке программирования... что может быть проще? Разве что только тупой копи-паст, но это уже недостойное занятие для программиста.   


Пожалуйста, не забываем плюсовать и помечать тему как решённую.

Дело в том, что опыт кодирования на C# у меня не очень большой, тем более с использованием BigInteger. И сразу написать это не получится, т.к. в Visual Studio нужные методы не показываются. Типа ShiftLeft, как в том примере на Java.
Пока что для меня этот алгоритм - один из вариантов, и, наверно, буду еще смотреть, как решать эту задачу.
В любом случае, пока этот пример мне не очень помог, т.к. он на другом языке, а возможности BigInteger в C# позволяют делать только определенные вещи.

Это сообщение отредактировал(а) motorway - 7.12.2009, 23:02

Ну это уже не серьёзно, ты документацию читать никогда не пробовал? 
System.Numerics.BigInteger members   
или если в .NET метод называется LeftShift, а не ShiftLeft, то это делает его абсолютно невидимым???

Это сообщение отредактировал(а) source777 - 7.12.2009, 23:16

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

Добавлено через 41 секунду
Ну и в VS его не видно было

Добавлено через 1 минуту и 59 секунд
И все-таки гуру сварганит этот небольшой код за гораздо меньшее время, чем я   

Пока что вообще не понял, как использовать этот оператор ShiftLeft

motorway, вообще-то в типе BigInteger есть ещё логарифмы. Все операции со степенями можно и через логарифмы выразить. Например возьмём десятичные логарифмы(хоть это и необязательно). Любое число n можно представить как
10^lg(n)
Здесь ^ - оператор возведения в степень

Стало быть если тебе надо получить квадратный корень - раздели показатель на 2 и будет тебе счастье
То есть твоё число будет равно 10^(0.5*lg(n))



Это сообщение отредактировал(а) diadiavova - 7.12.2009, 23:55

Но там же можно возводить только в целую степень!

Но ведь 10 может быть int  

Если корень из моего числа также большое число BigInteger, то проблема остается.

Ну это конечно. Хотя если немного помозговать с логарифмами, то и эту проблему решить видимо можно. В любом случае мой способ даст тебе первые 15 или 16 цифр результата и порядок. А уточнить результат можно и методом касательных, о котором упоминал source777, только для более быстрой сходимости его обычно комбинируют с методом хорд(поищи в том же источнике).Хотя это в математике работет быстрее, а на компе - фиг знает