корень из большого числа BigInteger

[motorway]

Вопрос состоит из 2 частей.

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

[Hollander]

Я бы в Hashtable хранил. Ключ - число, значение - корень.

[motorway]

Похоже, все-таки это не лучший метод - с таблицей. К тому же потестировал скорость вычислений с большими числами, и оказалось, что PHP примерно в 2 раза быстрее C#.

[Hollander]

Вот готовый BigInteger на C#. В нем есть метод sqrt, посмотри как там сделано и напиши свой метод.
http://www.codeproject.com/KB/cs/biginteger.aspx
Документация: http://groups.ist.utl.pt/meic-padi/p...ntegerDoc.html

Если не понравился класс, можешь сам посчитать, вот описания методов:
http://en.wikipedia.org/wiki/Methods...g_square_roots
http://en.wikipedia.org/wiki/Newton's_method

[motorway]

Дело не только в корне - даже умножение более медленное, чем на PHP.

[Hollander]

Ты спрашиваешь, что быстрее или как сделать? Ну возможно, что php быстрее считает, так что? Скорее всего есть другие платформы(возможно Java) где это еще быстрее.