2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Точно квадратные алгоритмы
Сообщение30.01.2011, 20:00 
Может, кто-нибудь знает быстрые целочисленные алгоритмы:
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.$$

 
 
 
 Re: Точно квадратные алгоритмы
Сообщение30.01.2011, 22:23 
Аватара пользователя
arseniiv в сообщении #406751 писал(а):
Итерационный метод Ньютона для (2) даёт пол, потолок или «нормальное» округление?
Потолок.

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

Xaositect в сообщении #406847 писал(а):
Потолок.
Так, это я не подумав сказал - раз метод Ньютона справа подходит, то и этот потолок найдет. На самом деле этот метод находит пол.

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

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

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group