重新缩放浮点数组,使所有项目都近似为整数

计算科学 浮点 缩放
2021-12-21 18:23:04

我有一个浮点值数组F. 我想将我的数组输入到一个只接受整数值的算法中。如何有效地确定最小乘数m这样所有的值mF是给定公差内的整数tol?

2个回答

当然——就拿m=1tol1mini|Fi|1016.

很容易看出,如果你采取m只要足够大,您将始终实现这一目标。为简单起见,假设您的数字都大于 1,并且小数点后最多有 3 位数字,那么如果将它们乘以 1000,则只能得到整数。当然,乘以任何大于一千的东西也可以。如果您不需要精确地达到整数,则可以使用较小的因子,但通常您需要的东西可能与容差上的一成正比。

也就是说,作为一般规则,乘以我上面建议的一些大数当然不是特别有用的东西。如果整数具有物理单位,则它们与任何其他数字一样具有任意性——一、二、三米没有什么特别之处。那么我的问题是你希望这些整数代表什么?

如果我们将输入数组视为d 实数而不是浮点值,那么这是一个最佳同时丢番图逼近的问题。JC Lagarias(第一部分(TAMS)第二部分(Pac. J.Math))在 1982 年的论文中,以及解决方案的复杂性在1985 年的论文 (SIAM J.Comp.)中。

他的结果是,虽然最好的同时上范数逼近问题是 NP 完全的,但 LLL 积分格算法可用于获得一个因子内的多项式时间逼近5d2(d+1)/2的最优误差。

Doug Hensley 有一篇更新的(2005 年)论文详细说明了当一个人从一维推进到更困难时的权衡d2问题。