| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм проверки извлечения квадратного корня |
| Автор: corpsehunter 27.6.2011, 13:27 |
| Нужно алгоритм проверки, является ли натуральное число квадратом какого-нибудь так же натурального числа. п.с. Вообще, в целом нужно проверить, является ли заданное число Х решением уравнения эллиптической кривой в натуральных числах: y^2 = x^3 + a*x + c, а если нет, то найти ближайшее к нему Х (пожалуй, в верхнюю сторону), которое будет таковым. |
| Автор: Akina 27.6.2011, 13:48 |
| Простейший - извлечь кв. корень, полученное возвесть в квадрат и сравнить с исходным. Если исходное в достаточной степени случайно - можно сначала проверять последние 1-2 цифры на предмет того, может ли это быть точным квадратом. |
| Автор: corpsehunter 27.6.2011, 14:01 | ||||
нельзя извлекать корень - я оперирую исключительно с натуральными числами а результат извлечения корня - уже вещественное число.
вот это не понял? можно поподробнее? |
| Автор: Akina 27.6.2011, 14:06 | ||||
Не понял... извлекай на множестве натуральных, кто мешает... более того - ведь именно это тебе и нужно.
Чего тут непонятного? Может ли быть квадратом число, последняя цифра которого - двойка? или последние две цифры которого - 55? |
| Автор: baldina 27.6.2011, 14:16 | ||||
подставить
решаете задачу дискретного логарифмирования? ах, оставьте...  |
| Автор: corpsehunter 27.6.2011, 14:27 | ||||
а как мне его извлечь на множестве натуральных чисел? о_О почитал на википедии статью "Квадратный корень" - отличный способ "арифметическое извлечение" но он будет очень долгим, т.к. я буду оперировать с очень длинными целым и числами.
ну это я еще из предыдущего поста понял, что нужно смотреть последние числа - нужно какое-нибудь общее правило? оно вообще есть? |
| Автор: baldina 27.6.2011, 14:42 |
| вы технически не можете использовать ничего кроме целых, или это религиозные убеждения? если технически, используйте блочный алгоритм, похожий на деление в столбик типа http://comp-science.narod.ru/DL-AR/koren.html потребуется хранить таблицу квадратов небольших чисел. можно приспособить к двоичному представлению |
