Быстрое целочисленное решение x(x-1)/2 = c

Если вы готовы принять удвоение IEEE с правильным округлением для всех операций, включая квадратный корень, то написанное вами выражение (плюс приведение к удвоению) дает правильный ответ для всех входных данных.

Вот неофициальное доказательство. Поскольку c — это 32-битное целое число без знака, которое преобразуется в тип с плавающей запятой с 53-битным мантиссом, 1 + 8*(double)c является точным, а sqrt(1 + 8*(double)c) правильно округлено. 1 + sqrt(1 + 8*(double)c) является точным с точностью до одной ulp, поскольку последнее слагаемое меньше 2**((32 + 3)/2) = 2**17.5 означает, что единица в последнем разряде последнего слагаемого меньше 1, и, таким образом, (1 + sqrt(1 + 8*(double)c))/2 имеет точность с точностью до одной ulp, поскольку деление на 2 является точным.

Последнее дело – пол. Проблемные случаи здесь возникают, когда (1 + sqrt(1 + 8*(double)c))/2 округляется до целого числа. Это происходит тогда и только тогда, когда sqrt(...) округляется до нечетного целого числа. Поскольку аргумент sqrt является целым числом, наихудшие случаи выглядят как sqrt(z**2 - 1) для положительных нечетных целых чисел z, и мы ограничиваем

z - sqrt(z**2 - 1) = z * (1 - sqrt(1 - 1/z**2)) >= 1/(2*z)

разложением Тейлора. Поскольку z меньше 2**17.5, разрыв до ближайшего целого числа составляет не менее 1/2**18.5 для результата, величина которого меньше 2**17.5, а это означает, что эта ошибка не может возникнуть из-за правильно округленного sqrt.

Принимая упрощение Якка, мы можем написать

(uint32_t)(0.5 + sqrt(0.25 + 2.0*c))

без дополнительной проверки.

Если мы начнем с квадратичной формулы, мы быстро достигнем sqrt(1/4 + 2c), округлив до 1/2 или выше.

Теперь, если вы делаете этот расчет с плавающей запятой, могут быть неточности.

Есть два подхода к устранению этих неточностей. Во-первых, нужно тщательно определить, насколько они велики, определить, достаточно ли расчетное значение близко к половине, чтобы они были важными. Если они не важны, просто верните значение. Если это так, мы все равно можем связать ответ с одним из двух значений. Проверьте эти два значения в целочисленной математике и вернитесь.

Однако мы можем покончить с этим осторожным моментом и отметить, что sqrt(1/4 + 2c) будет иметь ошибку меньше, чем 0.5, если значения 32-битные, и мы используем doubles. (Мы не можем дать эту гарантию с floats, так как 2^31 float не может обрабатывать +0.5 без округления).

По сути, мы используем квадратичную формулу, чтобы свести ее к двум возможностям, а затем проверяем эти две.

uint64_t eval(uint64_t x) {
  return x*(x-1)/2;
}
unsigned solve(unsigned c) {
  double test = sqrt( 0.25 + 2.*c );
  if ( eval(test+1.) <= c )
    return test+1.
  ASSERT( eval(test) <= c );
  return test;
}

Обратите внимание, что преобразование положительного double в целочисленный тип округляет до 0. Вы можете вставить floor, если хотите.

Это может быть немного касательным к вашему вопросу. Но что привлекло мое внимание, так это конкретная формула. Вы пытаетесь найти треугольный корень T_{n - 1} (где T_n — n-е треугольное число).

I.e.:

T_n = n * (n + 1) / 2

и

T_n - n = T_{n - 1} = n * (n - 1) / 2

Из изящного трюка, описанного здесь, для T_n мы имеем:

n = интервал (sqrt (2 * c))

Поиск n такого, что T_{n - 1} ≤ c, в этом случае не меняет определение n по той же причине, что и в исходном вопросе.

В вычислительном отношении это экономит несколько операций, поэтому теоретически это быстрее, чем точное решение (1). На самом деле, наверное, примерно так же.

Однако ни это решение, ни решение, представленное Дэвидом, не являются такими же точными, как ваше (1).

floor((1 + sqrt(1 + 8*c))/2) (синий) vs int(sqrt(2 * c)) (красный) vs Exact (белая линия)

floor((1 + sqrt(1 + 8*c))/2) (синий) vs int(sqrt(0,25 + 2 * c) + 0,5 (красный) vs Exact (белая линия)

На самом деле я хочу сказать, что треугольные числа — это забавный набор чисел, которые связаны с квадратами, треугольником Паскаля, числами Фибоначчи и т. д. др.

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

Особый интерес может представлять то, что T_n + T_{n - 1} = n²

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