Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Общие вопросы по .NET и C# > квадратный корень из большого числа

Автор: motorway 7.12.2009, 19:11

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

Автор: source777 7.12.2009, 20:00

Вообще-то есть куча более разумных алгоритмов вычисления квадратного корня, чем поиск по таблице квадратов, вот парочка методов из http://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D1%8C#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D1.8B_.D0.BD.D0.B0.D1.85.D0.BE.D0.B6.D0.B4.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BA.D0.B2.D0.B0.D0.B4.D1.80.D0.B0.D1.82.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BA.D0.BE.D1.80.D0.BD.D1.8F, хотя я советую использовать метод Ньютона, не зря он на уровне процессора используется, ибо очень быстрая сходимость у него.

Автор: motorway 7.12.2009, 20:11

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

Автор: source777 7.12.2009, 21:49

Цитата(motorway @  7.12.2009,  20:11 ) Меня интересует самый быстрый метод из имеющихся в наличии готовых.  "Самый быстрый" это не математическое понятие, понятно же, что многое зависит от числа, корень которого надо найти. Но http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 определённо один из самых быстрых для больших N. Кроме того он подходит для поиска действительных корней практически любого уравнения, а уравнение для вычисления квадратного корня x*x - N = 0  это лишь частный случай. Вот пример применения этого метода конкретно для вычисления квадратного кода: http://e-maxx.ru/algo/roots_newton

Автор: motorway 7.12.2009, 22:14

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

Автор: source777 7.12.2009, 22:44

Цитата(motorway @  7.12.2009,  22:14 ) Еще бы понять, как переделать этот алгоритм на C# с использованием имеющихся в распоряжении функций.  Ты видимо имел в виду "записать", что-то переделывать там нет необходимости. А уж записать готовый алгоритм на известном тебе языке программирования... что может быть проще? Разве что только тупой копи-паст, но это уже недостойное занятие для программиста.    Цитата(motorway @  7.12.2009,  22:14 ) Спасибо. Пожалуйста, не забываем плюсовать и помечать тему как решённую.

Автор: motorway 7.12.2009, 22:49

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

Автор: source777 7.12.2009, 23:16

Цитата(motorway @  7.12.2009,  22:49 ) В любом случае, пока этот пример мне не очень помог, т.к. он на другом языке, а возможности BigInteger в C# позволяют делать только определенные вещи. Ну это уже не серьёзно, ты документацию читать никогда не пробовал?  http://msdn.microsoft.com/en-us/library/system.numerics.biginteger_members%28VS.100%29.aspx    или если в .NET метод называется LeftShift, а не ShiftLeft, то это делает его абсолютно невидимым???

Автор: motorway 7.12.2009, 23:32

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

Автор: motorway 7.12.2009, 23:50

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

Автор: diadiavova 7.12.2009, 23:55

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

Автор: motorway 8.12.2009, 00:01

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

Автор: diadiavova 8.12.2009, 00:03

Цитата(motorway @  8.12.2009,  00:01 ) Но там же можно возводить только в целую степень!  Но ведь 10 может быть int

Автор: motorway 8.12.2009, 00:06

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

Автор: diadiavova 8.12.2009, 00:11

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

Автор: source777 8.12.2009, 12:25

Цитата(motorway @  7.12.2009,  23:32 ) И все-таки гуру сварганит этот небольшой код за гораздо меньшее время, чем я  smile   И что с того? Даже если я могу написать этот код в 1000 раз быстрее тебя, это ни разу не повод лишать тебя возможности сделать это самому. Тебе и так уже всё разжевали и в рот положили... А если ты самостоятельно думать совсем не способен и учиться этому не желаешь, то тут уж тебе никто не поможет... Добавлено через 2 минуты и 1 секунду Цитата(motorway @  7.12.2009,  23:50 ) Пока что вообще не понял, как использовать этот оператор ShiftLeft  А http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.op_leftshift%28VS.100%29.aspx религия не позволяет посмотреть?

Автор: motorway 8.12.2009, 18:16

Это понятно, просто там на Яве было, а я ее практически не знаю. Можно, конечно, начать делать методом подбора, но это не оч. эффективно. Примеры использования я смотрел, но при вставке этот код не работал. В общем, я протестировал одну функцию корня на C#, и оказалось, что на PHP в 2 раза все быстрее делается. Так что пока для этих целей он лучше подходит. Добавлено через 1 минуту и 6 секунд И умножение на PHP тоже быстрее, и другие операции, видимо, тоже.

Автор: ДобренькийПапаша 8.12.2009, 19:19

Если вам нужно производить очень сложные и очень быстрые алгебраические операции, то .NET не лучший выбор. Лучше С++ и использование численных методов, думается. Геморроя много, но достичь желаемого результата можно. А вот в скорости выполнения операции на .NET я сумлеваюсь))) (если она вам так сильно при сильно нужна...)

Автор: PashaPash 8.12.2009, 19:48

Проблема решена, насколько я понял: http://social.msdn.microsoft.com/Forums/ru-RU/csharpru/thread/f9aca8c2-af21-40e4-b5bb-c9613b9db4ca

Автор: source777 8.12.2009, 19:57

Цитата(motorway @  8.12.2009,  18:16 ) В общем, я протестировал одну функцию корня на C#, и оказалось, что на PHP в 2 раза все быстрее делается. Так что пока для этих целей он лучше подходит. И умножение на PHP тоже быстрее, и другие операции, видимо, тоже.  Редкостный маразм. Интерпретируемые языки по определению на порядок медленнее, чем компилируемые. http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=all&box=1 Цитата(motorway @  8.12.2009,  18:16 ) Это понятно, просто там на Яве было, а я ее практически не знаю. Там ещё по-русски описание алгоритма есть или русский язык ты тоже практически не знаешь? Добавлено через 14 минут и 45 секунд Цитата(PashaPash @  8.12.2009,  19:48 ) Проблема решена, насколько я понял: http://social.msdn.microsoft.com/Forums/ru...bb-c9613b9db4ca  Вот он оказывается какой негодник, вместо того чтобы самому хоть немного подумать, выцыганил готовое решение на другом форуме. Ладно хоть ему там не самый оптимальный вариант дали.

Автор: motorway 8.12.2009, 22:01

Цитата Редкостный маразм. Интерпретируемые языки по определению на порядок медленнее, чем компилируемые. пример вменяемых замеров производительности Для каких-то задач они и медленнее, а здесь на первый план выходит скорость вычислений с большими числами. И делается это путем вызовов функций соотв. библиотек, так что от самого языка не сильно зависит, если тратится 99% времени на вычисления такие. В PHP это получается быстрее по моим тестам, а в C# налицо более медленные вычисления. В том тесте могли тестировать на других программах. У меня же большую часть времени производятся операции с большими числами. А значит, просто BigInteger в C# сделан медленнее, чем в PHP. Цитата Там ещё по-русски описание алгоритма есть или русский язык ты тоже практически не знаешь? В первую очередь я хотел найти готовое стандартное решение проблемы. Такую функцию как корень писать самому - изобретать велосипед. Это должны были сделать раньше.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)