最近有一道编程题一直在愁我, 希望有人能帮我一下.

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2027 天前的主题，其中的信息可能已经有所发展或是发生改变。

题面很简单, 但是我没有在数较大的情况下优化的经验, 所以计算时间较长

有这样一个数列,第一项是 1, 第二项是 3.
递推公式和 fibonacci 数列是一样的, 但有一个额外的条件, 每个数要取模(余数).
例如 mod=127 的前 15 项如下

i=1,r=1 i=2,r=3 i=3,r=4 i=4,r=7 i=5,r=11 i=6,r=18 i=7,r=29 i=8,r=47 i=9,r=76 i=10,r=123 i=11,r=72 i=12,r=68 i=13,r=13 i=14,r=81 i=15,r=94

要求的是 f(index,mod) , 给定 index 和 mod, 输出结果
比如 f(10,127)=123, f(6,127)=18

真正的问题来了, index 和 mod 会是很大的数, 我就懵了.

请用这个数据检验:

index = 2**110502 mod = 2**110503-1 f(index,mod)=0

目前 python mbp-i9 用时 79.48 秒

mod

index

余数

数列

19 条回复 2020-04-04 21:11:07 +08:00

lance6716

2020-04-04 12:05:15 +08:00 via Android

矩阵乘法计算斐波那契，然后快速幂的优化

yinsky

2020-04-04 12:05:53 +08:00

动态规划？

YUX

PRO

2020-04-04 12:08:27 +08:00

@lance6716 #1 如果先把数列算出来再取模数就太大了, 边算边 mod 数就不会超过 mod

YUX

PRO

2020-04-04 12:09:47 +08:00

@yinsky #2 python 的话远超最大递归限制了

yinsky

2020-04-04 12:17:20 +08:00

@YUX 本身类似斐波那契数列就没有啥好的方法，基数太大肯定慢呀，不好搞。

zh4710jj

2020-04-04 12:20:10 +08:00 via Android

斐波那契数列有通项公式的吧，模运算的部分是否可以放到最后再算，最后就是一个大数模 127

YUX

PRO

2020-04-04 12:24:35 +08:00

@zh4710jj #6 是有通项公式, 但是公式里有根号 5 这个无理数, 算的时候计算精度不够

litmxs

2020-04-04 12:28:30 +08:00

矩阵快速幂

litmxs

2020-04-04 12:29:03 +08:00

https://www.cnblogs.com/ranjiewen/p/8998112.html

gwy15

2020-04-04 14:18:10 +08:00

我优化到了在 numba.jit 程度下 1.5s 左右，但是算出来并不是 0 。如果楼主确定这个是 0，那我估计可能是 numba 的问题，我得换 c++ 重新写下

YUX

PRO

2020-04-04 14:27:57 +08:00 via iPhone

@gwy15 numba 在 2^64 之后就溢出了

fx050622

2020-04-04 16:45:28 +08:00

我觉得你想复杂了，取模应该不影响 An 的计算的.
mod(A(n+1))=mod(mod(A(n))*A)
array=[1,1,1,0]
我自己 PC 试了下 782736251 次 5.3s

def multiply(array: Array[Int], times: Int, mode: Int = 127):Unit = {
if (times > 0) {
val t1 = array(0)
val t2 = array(1)
val t3 = array(2)
val t4 = array(3)
array(0) = (t1 + t2) % mode
array(1) = t1
array(2) = (t3 + t4) % mode
array(3) = t3
multiply(array, times - 1)
}
}

YUX

PRO

2020-04-04 16:49:22 +08:00

@fx050622 #12 计算我给出的那个数据,用了多少时间? 结果是 0 吧? 谢了

BiteTheDust

2020-04-04 16:54:38 +08:00

这是一个典型的矩阵快速幂优化线性递推
当然也可以直接用 Reeds Sloane 算法

liyunlong41

2020-04-04 16:59:09 +08:00 via iPhone

递推应该可以用矩阵快速幂来优化

gwy15

2020-04-04 17:00:53 +08:00

用 rust 和 c++ 重新写了一遍，rust 的高精度库实现不太好，还是得用 GMP 。

复杂度是 log(index) log(mod) log(log(mod))，
也就是，N=110503 的情况下，N^2 log(N)。算出来是 204e9 数量级，大概就是要一百秒的样子。我用 c++ + GMP 跑出来是 95s，4.0G 主频

YUX

PRO

2020-04-04 17:03:03 +08:00

@gwy15 #16 看来是不能再快了,我用的是 python+gmp, 最后结果是 0 吧?

yuruizhe

2020-04-04 19:15:58 +08:00

@YUX 就是 6 楼说的通项公式，公式用二项式定理展开，对根号 5 合并相消，最后应该得到一个整数运算公式
设 Comb()表述组合数公式
最后结果应该是[Comb(1,n)*x^0 + Comb(3,n)*x^2 + Comb(5,n)*x^4 + Comb(7,n)*x^6 + ....]/2^n

superrichman

2020-04-04 21:11:07 +08:00 via iPhone

发现一个有趣的东西，这个数列的值可以这样表达

2*fibb(x) - fibb(x-1)

1=2*1-1
3=2*2-1
4=2*3-2
7=2*5-3
11=2*8-5
18=2*13-8
29=2*21-13