powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / C++ [игнор отключен] [закрыт для гостей] / Счастливые числа
12 сообщений из 37, страница 2 из 2
Счастливые числа
    #40063822
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

petravВот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.

Ну да, в этом случае код можно было бы сократить до "return false".

Почему же? Это же классическое округление.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063827
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИМХО плавающая точка тут не самый лучший вариант. Целое не может быть более 52-х бит (размер мантиссы в double), больше приведет к ошибкам.

Тут можно обойтись целыми, применить бинарный поиск. Для 64-битного числа результат будет нечетное в диапазоне 1...2 32 -1, т.е. максимум за 31 шаг найдется корень если он есть. Возможно это будет даже быстрее чем std::sqrt()
...
Рейтинг: 0 / 0
Счастливые числа
    #40063831
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petravПочему же? Это же классическое округление.

Потому что именно для данной функции оно даст неверный результат.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063835
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Ну да, в этом случае код можно было бы сократить до "return false".
Немного изменил иходный пример кода. Исходную функцию переименовал в isSquare_01, вторую назвал isSquare_02, в ней добавил сложение с 0.5F, чтобы сравнить результаты их выполнения. Сошлось на всем диапазоне двухбайтных целых беззнаковых чисел. Для 4-байтных (uint32_t) не дождался результата. И шаблонизацию убрал, чтобы впечатлительных не смущало.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
#include <iostream>
#include <limits>

using numberType = unsigned;

void findNumbers(numberType From, numberType To) {
    auto isSquare_01 = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };

    auto isSquare_02 = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value) + 0.5F);
        return Sqrt * Sqrt == Value;
    };

    for (auto i = From; i <= To; ++i) {
        if (isSquare_01(i) != isSquare_02(i)) {
            std::cout << i << std::endl;
        }
    }
}

int main() {
    findNumbers(1, /*std::numeric_limits<numberType>::max()*/std::numeric_limits<uint16_t>::max());
    return 0;
}
...
Рейтинг: 0 / 0
Счастливые числа
    #40063849
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для четырехбайтных надо брать не максимальное значение, а чуть меньше, чтобы не перескочить через ноль в цикле. Но на моей машине это все равно долго.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063862
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

petravПочему же? Это же классическое округление.

Потому что именно для данной функции оно даст неверный результат.

Ты имхо чего-то не досмотрел. Ну или пруф в студию. Одно верное входное число для которого будет неверный результат.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063873
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKadДля 4-байтных (uint32_t) не дождался результата.

Это из-за корня. Он медленный.

petravТы имхо чего-то не досмотрел.

Да, я недосмотрел, что умножение в return идёт в целых.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063876
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Проверка на целых
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
bool is_square(uint64_t n) {
	uint64_t l = 1, r = 0xFFFFFFFF;
	while (l < r) {
		uint64_t m = l + (r - l) / 2;
		uint64_t m2 = m*m;

		if (m2 == n)
			return true;

		if (m2 > n)
			r = m;
		else
			l = m+1;
	}
	return l*l == n;
}
...
Рейтинг: 0 / 0
Счастливые числа
    #40063889
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

...
Это из-за корня. Он медленный.
...

Корень - единственная из функций, вычисление которой было стандартизировано в самой исходной версии IEEE
Поэтому он и быстрый - используются алгоритмы, обладающие не меньше, чем квадратичной сходимостью,
с общей зависимостью скорости вычисления результата от входного значения, не хуже log(N),
и самый гарантированно точный - точность представимого результата в 0.5ulp

Так что медленно не потому, что корень медленный, а потому, что его используют в квадрат лишнее количество раз,
вместо того, чтобы просто оценить только края, что и требуется в именно этой задаче.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064002
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Проверка на целых
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
bool is_square(uint64_t n) {
	uint64_t l = 1, r = 0xFFFFFFFF;
	while (l < r) {
		uint64_t m = l + (r - l) / 2;
		uint64_t m2 = m*m;

		if (m2 == n)
			return true;

		if (m2 > n)
			r = m;
		else
			l = m+1;
	}
	return l*l == n;
}


В качестве начального приближения здесь выбирают половину разрядной сетки от максимального значения
аргумента.

Можно перевести аргумент в double (если экспонента позволяет) и использовать уже
расчитанный вещественный корень как первое приближение и потом быстро конвертнуть обратно
в arbitrary и уже сделать парочку контрольных выстрелов до достижения точности.

Точности снизу или сверху кому как удобно.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064054
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Открываем "Алгоритмические трюки" Генри Уоррена-младшего:
Глава 11. Некоторые элементарные функции
11.1. Целочисленный квадратный корень.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064102
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из наших экспериментов 15 года с простыми числами. Это и была копи-паста из Генри Уоррена.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
uint64_t isqrt64(uint64_t x) {	
	uint64_t x1;
	uint64_t s, g0, g1;
	if (x <= 1) return x;
	s = 1;
	x1 = x - 1;
      if (x1 > 0x100000000 - 1)     { s+=16; x1>>=32;}
	if (x1 > 0x10000     - 1)     { s+=8;  x1>>=16;}
	if (x1 > 0x100       - 1)     { s+=4;  x1>>=8; }
	if (x1 > 0x10        - 1)     { s+=2;  x1>>=4; }
	if (x1 > 3)                   { s+=1; }
	g0 = 1<<s;
	g1 = (g0 + (x >> s)) >> 1;
	while(g1 < g0) {
		g0 = g1;
		g1 = (g0 + (x/g0)) >> 1;
	}
	return g0;
}
...
Рейтинг: 0 / 0
12 сообщений из 37, страница 2 из 2
Форумы / C++ [игнор отключен] [закрыт для гостей] / Счастливые числа
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]