IBM Research

谜题   IBM-301

由伪随机相似性矩阵计算二次型

IBM Research · Ponder This · 2023 年 5 月

IBM Ponder This #301 · 2023 年 5 月 ​

Lorenzo Gianferrari Pini 与 Radu-Alexandru Todor 提出了这个问题。向量 x∈Rn 长度为 n,分量为 (x0,x1,…,xn−1);A∈Rn×n 是 n×n 矩阵,要求计算 xTAx。

x 在 −1 与 1 之间等间距取值,例如 n=5 时 x=(−1,−0.5,0,0.5,1)。

生成矩阵 A 的方法如下。给定 k∈N,令 a∈R2k 从 0 至 1 等间距排列,即 at=t2k−1,t=0,1,…,2k−1。矩阵 A 的元素从 a 中取。

给出序列 Q0,Q1,…,Qn−1,每个 Qi∈Nk 含 k 个自然数。对两向量定义长度为 k 的比特向量 Qi==Qj:Qi,Qj 的对应分量相等时为 1,否则为 0。令 [Qi==Qj] 为该向量 Qi==Qj 表示的整数,下标 0 为最低位。

例如 Qi=(1,5,7,8) 与 Qj=(2,5,6,8) 得到 Qi==Qj=(0,1,0,1),所以 [Qi==Qj]=10,因为 (0,1,0,1) 对应二进制 1010。定义 Aij=a[Qi==Qj],即 Aij 根据 Qi、Qj 的相似性,从固定的 2k 个值中选择。

Qi 按下式生成:Qi[t]=⌊2k⋅(sin⁡((i+1)⋅(t+1))−⌊sin⁡((i+1)⋅(t+1))⌋)⌋。例如 k=5 时,Q13=(31,8,2,15,24)。

任务:对 k=5,n=220 求 xTAx,四舍五入到三位小数。

附加问题:对 k=5,n=230 求 xTAx,同样保留三位小数。

解答

认真尝试后再打开

待补充。