Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
Dimitry Sibiryakov

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

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

Почему же? Это же классическое округление.
19 апр 21, 13:24    [22310914]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dima T
Member

Откуда:
Сообщений: 15795
ИМХО плавающая точка тут не самый лучший вариант. Целое не может быть более 52-х бит (размер мантиссы в double), больше приведет к ошибкам.

Тут можно обойтись целыми, применить бинарный поиск. Для 64-битного числа результат будет нечетное в диапазоне 1...232-1, т.е. максимум за 31 шаг найдется корень если он есть. Возможно это будет даже быстрее чем std::sqrt()

Сообщение было отредактировано: 19 апр 21, 13:23
19 апр 21, 13:31    [22310920]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394

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

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

Posted via ActualForum NNTP Server 1.5

19 апр 21, 13:35    [22310926]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
Dimitry Sibiryakov
Ну да, в этом случае код можно было бы сократить до "return false".
Немного изменил иходный пример кода. Исходную функцию переименовал в isSquare_01, вторую назвал isSquare_02, в ней добавил сложение с 0.5F, чтобы сравнить результаты их выполнения. Сошлось на всем диапазоне двухбайтных целых беззнаковых чисел. Для 4-байтных (uint32_t) не дождался результата. И шаблонизацию убрал, чтобы впечатлительных не смущало.
#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;
}


Сообщение было отредактировано: 19 апр 21, 13:36
19 апр 21, 13:39    [22310931]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
Для четырехбайтных надо брать не максимальное значение, а чуть меньше, чтобы не перескочить через ноль в цикле. Но на моей машине это все равно долго.
19 апр 21, 13:55    [22310950]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
Dimitry Sibiryakov

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

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

Ты имхо чего-то не досмотрел. Ну или пруф в студию. Одно верное входное число для которого будет неверный результат.
19 апр 21, 14:13    [22310969]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394

AmKad
Для 4-байтных (uint32_t) не дождался результата.

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

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

Да, я недосмотрел, что умножение в return идёт в целых.

Posted via ActualForum NNTP Server 1.5

19 апр 21, 14:31    [22310987]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dima T
Member

Откуда:
Сообщений: 15795
Проверка на целых
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;
}
19 апр 21, 14:36    [22310991]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
booby
Member

Откуда:
Сообщений: 2534
Dimitry Sibiryakov

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

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

Так что медленно не потому, что корень медленный, а потому, что его используют в квадрат лишнее количество раз,
вместо того, чтобы просто оценить только края, что и требуется в именно этой задаче.
19 апр 21, 14:50    [22311012]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Dima T
Проверка на целых
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 и уже сделать парочку контрольных выстрелов до достижения точности.

Точности снизу или сверху кому как удобно.
19 апр 21, 19:54    [22311228]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 11020
Открываем "Алгоритмические трюки" Генри Уоррена-младшего:
Глава 11. Некоторые элементарные функции
11.1. Целочисленный квадратный корень.
20 апр 21, 06:31    [22311300]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Из наших экспериментов 15 года с простыми числами. Это и была копи-паста из Генри Уоррена.

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;
}
20 апр 21, 10:54    [22311370]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / C++ Ответить