Точно квадратные алгоритмы

[arseniiv]

Может, кто-нибудь знает быстрые целочисленные алгоритмы:
1) для проверки, является ли число точным квадратом;
2) для вычисления $\lfloor \sqrt n \rfloor$ и $\lceil \sqrt n \rceil$ (отдельно)?

Вычитание 1, 3, 5, 7 и т. д. не предлагать!

-- Вс янв 30, 2011 23:01:53 --

Итерационный метод Ньютона для (2) даёт пол, потолок или «нормальное» округление?

Я про этот:

$$\left\{ \begin{array}{l} s_0 = N \\ s_{n+1} = (s_n + N / s_n) \operatorname{shr} 1 \end{array} \right.$$

[Xaositect]

arseniiv в сообщении #406751 писал(а):

Итерационный метод Ньютона для (2) даёт пол, потолок или «нормальное» округление?

Потолок.

-- Вс янв 30, 2011 22:29:26 --

Xaositect в сообщении #406847 писал(а):

Потолок.

Так, это я не подумав сказал - раз метод Ньютона справа подходит, то и этот потолок найдет. На самом деле этот метод находит пол.

-- Вс янв 30, 2011 22:33:45 --

Это интересно: http://gmplib.org/manual/Perfect-Square ... -Algorithm

[arseniiv]

Спасибо! А то вот хотел побаловаться факторизацией методом Ферма. (Правда, сегодня передумал, но вдруг передумаю ещё нечётное количество раз.)