深度1432（因此2 ^ 1432项）足以使真实总和超出计算总和两倍。
我对如何确定所需的术语数量少于两个的想法有个想法。
我们使用动态编程来回答以下问题：给定深度d和目标浮点和s，具有成对和的2^d非负float16s的最大真和是s多少？
让那个数量成为T(d, s)。我们复发
T(0, s) = s, for all s.
T(d, s) = max (T(d-1, a) + T(d-1, b)), for all d, s.
a, b : float16(a + b) = s
重复执行的每个步骤都涉及遍历大约2^29组合（因为我们可以假设a ≤ b，并且负浮点数和特殊值超出了限制），并且所需的深度不会超过10^4Hans和您的答案。在我看来可行。
DP代码：
#include <algorithm>
#include <cstdio>
#include <vector>
using Float16 = int;
using Fixed = unsigned long long;
static constexpr int kExponentBits = 5;
static constexpr int kFractionBits = 10;
static constexpr Float16 kInfinity = ((1 << kExponentBits) - 1)
<< kFractionBits;
Fixed FixedFromFloat16(Float16 a) {
int exponent = a >> kFractionBits;
if (exponent == 0) {
return a;
}
Float16 fraction = a - (exponent << kFractionBits);
Float16 significand = (1 << kFractionBits) + fraction;
return static_cast<Fixed>(significand) << (exponent - 1);
}
bool Plus(Float16 a, Float16 b, Float16* c) {
Fixed exact_sum = FixedFromFloat16(a) + FixedFromFloat16(b);
int exponent = 64 - kFractionBits - __builtin_clzll(exact_sum);
if (exponent <= 0) {
*c = static_cast<Float16>(exact_sum);
return true;
}
Fixed ulp = Fixed{1} << (exponent - 1);
Fixed remainder = exact_sum & (ulp - 1);
Fixed rounded_sum = exact_sum - remainder;
if (2 * remainder > ulp ||
(2 * remainder == ulp && (rounded_sum & ulp) != 0)) {
rounded_sum += ulp;
}
exponent = 64 - kFractionBits - __builtin_clzll(rounded_sum);
if (exponent >= (1 << kExponentBits) - 1) {
return false;
}
Float16 significand = rounded_sum >> (exponent - 1);
Float16 fraction = significand - (Float16{1} << kFractionBits);
*c = (exponent << kFractionBits) + fraction;
return true;
}
int main() {
std::vector<Fixed> greatest0(kInfinity);
for (Float16 a = 0; a < kInfinity; a++) {
greatest0[a] = FixedFromFloat16(a);
}
for (int depth = 1; true; depth++) {
auto greatest1 = greatest0;
for (Float16 a = 1; a < kInfinity; a++) {
Fixed greatest0_a = greatest0[a];
for (Float16 b = a; b < kInfinity; b++) {
Float16 c;
if (!Plus(a, b, &c)) {
continue;
}
Fixed& value = greatest1[c];
value = std::max(value, greatest0_a + greatest0[b]);
}
}
std::vector<double> ratios;
ratios.reserve(kInfinity - 1);
for (Float16 a = 1; a < kInfinity; a++) {
ratios.push_back(greatest1[a] / static_cast<double>(FixedFromFloat16(a)));
}
std::printf("depth %d, ratio = %.17g\n", depth,
*std::max_element(ratios.begin(), ratios.end()));
greatest0.swap(greatest1);
}
}
我将运行它并在完成后发布更新。
602392714
清零编程群