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

Сейчас на форуме: zds, UniSoft (+5 невидимых)

Посл.ответ	Сообщение
VodoleY Ранг: 488.1 (мудрец), 272thx Активность: 0.35↘0 Статус: Участник	Создано: 23 декабря 2012 13:36 · Поправил: VodoleY · Личное сообщение · #1 Добрый день всем. Может ктото занимался... Существует ли адаптивный алгоритм, очень быстрый 1. для теста большого числа на то, является ли он квадратом числа 2. если на 1ый вопрос ответа нет, то вычисление остатка от корня. скорость первична АДД. ЧИСЛА БОЛЬШИЕ от 512 бит ----- Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

ZaZa Ранг: 158.5 (ветеран), 219thx Активность: 0.12↘0.01 Статус: Участник	Создано: 23 декабря 2012 13:45 · Поправил: ZaZa · Личное сообщение · #2 Не то, не? --> квадратный корень из BigInteger <-- Или так: Code: //Можно найти квадратный корень числа путем вызова метода Log вместе с методом Math.Exp. //Обратите внимание, что результатом является Double.PositiveInfinity, если значение результата превышает Double.MaxValue. //В следующем примере вычисляется квадратный корень каждого элемента в массиве значений BigInteger. using System; using System.Numerics; public class Example { public static void Main() { BigInteger[] values = { 2, 100, BigInteger.Pow(1000, 100), BigInteger.Pow(2, 64) }; foreach (var value in values) Console.WriteLine("The square root of {0} is {1}", value, Math.Exp(BigInteger.Log(value) / 2)); } } // The example displays the following output: // The square root of 2 is 1.41421356237309 // The square root of 100 is 10 // The square root of 1000000000000000000000000000000000000000000000000000000000000 // 00000000000000000000000000000000000000000000000000000000000000000000000000000000 // 00000000000000000000000000000000000000000000000000000000000000000000000000000000 // 00000000000000000000000000000000000000000000000000000000000000000000000000000000 // is 9.99999999999988E+149 // The square root of 18446744073709551616 is 4294967296 Скорость только проверить осталось )) ----- One death is a tragedy, one million is a statistic.
Ara Ранг: 1288.1 (!!!!), 273thx Активность: 1.29↘0 Статус: Участник	Создано: 23 декабря 2012 13:47 · Личное сообщение · #3 ZaZa пишет: Не то, не? То. Смотреть там, где юзается метод Ньютона.
VodoleY Ранг: 488.1 (мудрец), 272thx Активность: 0.35↘0 Статус: Участник	Создано: 23 декабря 2012 13:50 · Поправил: VodoleY · Личное сообщение · #4 ZaZa нет. я сделал половинным делением с отниманием нечетных. весьма шустр. интересно именно адаптивный вариант. ускоспециализированный и раскачанный по скорости http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi вот тут народ психовал http://www.coderanch.com/forums/banner/redirect/449 есьма интересная разработка но не то все это З.Ы. гораздо оптимален метод вычетов нечетных, чем метод Ньютона (если заранее граничные суммы нечетов подготовить) 64битное большое за 5 вычитов и сравнений считается ----- Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....
ClockMan Ранг: 568.2 (!), 465thx Активность: 0.55↗0.57 Статус: Участник оптимист	Создано: 23 декабря 2012 15:29 · Поправил: ClockMan · Личное сообщение · #5 VodoleY пишет: скорость первична В любом процессоре есть сопроцессор с коммандой FSQRT для вычесления корня квадратного c поддержкой Extended(от 3.37 x 10 * -4932 до 1.18 x 10 * +4932) скорость будет зависть от модели проца ----- Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли. \| Сообщение посчитали полезным: ZaZa
ZaZa Ранг: 158.5 (ветеран), 219thx Активность: 0.12↘0.01 Статус: Участник	Создано: 23 декабря 2012 15:59 · Личное сообщение · #6 А большие числа - это до скольки? [0x0 ... 0xFFFFFFFF] А ограничение результата по точности? Если не секрет, чего ты такого делаешь? ----- One death is a tragedy, one million is a statistic.
Archer Ранг: 2014.5 (!!!!), 1278thx Активность: 1.34↘0.25 Статус: Модератор retired	Создано: 23 декабря 2012 16:22 · Личное сообщение · #7 ZaZa пишет: А большие числа - это до скольки? Можно же маны поглядеть. Операция эта над FPU-регистром. В нём 80 битов. Выше написан примерный диапазон: ClockMan пишет: от 3.37 x 10 * -4932 до 1.18 x 10 * +4932 Но реально в 80 битов это не влезет, конечно, и из-за округления это может не совсем сгодиться.
ZaZa Ранг: 158.5 (ветеран), 219thx Активность: 0.12↘0.01 Статус: Участник	Создано: 23 декабря 2012 16:54 · Поправил: ZaZa · Личное сообщение · #8 Archer пишет: Можно же маны поглядеть. Операция эта над FPU-регистром. В нём 80 битов. Выше написан примерный диапазон: Да я не про это... Маны можно посмотреть, не спорю [даже нужно, иногда]... Возможно необходимости в таком количестве бит и нет совсем? Всегда есть какие-либо границы в вычислениях... tihiy_grom пишет: ну да, для такого диапазона скорость очень критична. Да, да... А вдруг у меня ZX-Spectrum, для которого такие числа, ну ООООчень большие? Тем более я для примера указал... И давайте сосредоточимся на теме... ----- One death is a tragedy, one million is a statistic.
tihiy_grom Ранг: 441.3 (мудрец), 297thx Активность: 0.41↘0.04 Статус: Участник	Создано: 23 декабря 2012 16:56 · Личное сообщение · #9 ZaZa пишет: А большие числа - это до скольки? [0x0 ... 0xFFFFFFFF] ну да, для такого диапазона скорость очень критична.
VodoleY Ранг: 488.1 (мудрец), 272thx Активность: 0.35↘0 Статус: Участник	Создано: 23 декабря 2012 19:02 · Личное сообщение · #10 ZaZa пишет: А большие числа - это до скольки? [0x0 ... 0xFFFFFFFF] А большие числа это больше чем 512 бит. Все поржали? дробная часть вообще не интересует. В вопросе вроде четко указано ТЗ. В идеалии вообщее функа тру/фелс полный квадрат числа или нет ----- Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме.... \| Сообщение посчитали полезным: DimitarSerg
ZaZa Ранг: 158.5 (ветеран), 219thx Активность: 0.12↘0.01 Статус: Участник	Создано: 23 декабря 2012 20:32 · Личное сообщение · #11 VodoleY пишет: Все поржали? Да никто и не ржал, даже не хихикал... Просто решил уточнить, да привел как пример границы... ТЗ именно тем и отличается, что там все детально расписано! ----- One death is a tragedy, one million is a statistic.
ajax Ранг: 337.6 (мудрец), 224thx Активность: 0.21↘0.1 Статус: Участник born to be evil	Создано: 23 декабря 2012 22:01 · Личное сообщение · #12 VodoleY большинство через читает. даже первый пост. для bigint вряд-ли в прессе кто-то продумывал. метод деления отрезка - единственное, что и мне подумалось. что-то должно быть лучше. надо шукать ----- От многой мудрости много скорби, и умножающий знание умножает печаль
VodoleY Ранг: 488.1 (мудрец), 272thx Активность: 0.35↘0 Статус: Участник	Создано: 23 декабря 2012 22:40 · Личное сообщение · #13 Тогда уточняю и добавляю вопрос. Числа от 512 бит, и еще.. Раньше была табличка для профилировки по скорости, где было расписано кол-во тиков проца на выполнения каждой инструкции проца + доп тики на разные параметры комманды (например вычитывание из памяти) я давно в эти дебри не лазил, видимо конвеер еще учитывать прийедься, в ЛС хотелось бы пообщаться с людьми,которые оптимизацией по скорости занимались ----- Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....
ajax Ранг: 337.6 (мудрец), 224thx Активность: 0.21↘0.1 Статус: Участник born to be evil	Создано: 24 декабря 2012 00:40 · Поправил: ajax · Личное сообщение · #14 Power(a,b : Extended) : Extended result=exp(b*ln(a)) square root: sqrt(x) = x в степени 0.5 FGInt сырки, или как-то так. дальше можно оптимизировать. пысы: бухаем-с и тупим-с... ----- От многой мудрости много скорби, и умножающий знание умножает печаль
mysterio Ранг: 307.9 (мудрец), 196thx Активность: 0.18↘0 Статус: Участник	Создано: 24 декабря 2012 04:36 · Личное сообщение · #15 VodoleY На счет алгоритма ХЗ... но если вдруг ..... Нужно что-то такое ? Вбиваем нужный X и играемся ;) ----- Don_t hate the cracker - hate the code.
zabriskie Ранг: 1.9 (гость), 3thx Активность: 0=0 Статус: Участник	Создано: 24 декабря 2012 12:24 · Личное сообщение · #16 VodoleY Оптимизацией команд для Intel занимается Agner Fog. На http://www.agner.org/optimize/ нужный тебе документ под номером 4. \| Сообщение посчитали полезным: VodoleY

Для печати