2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Точно квадратные алгоритмы
Сообщение30.01.2011, 20:00 
Заслуженный участник


27/04/09
28128
Может, кто-нибудь знает быстрые целочисленные алгоритмы:
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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group