《编程原本 》一2.4 轨道规模的度量

2.4 轨道规模的度量

对于类型T上的轨道,有关规模o,h和c的自然类型应该是一个足以记录类型T中所有不同的值的个数的整数计数类型.如果类型T占了k位,它至多有2k 个值,所以一个k位的计数类型将不能表示从0到2k 的所有计数值.但在使用距离类型时有一种表示这些规模的方法.
一条轨道有可能包含某类型的所有值,这时o就可能无法存入相应的距离类型.对不同形状的轨道,h或c也可能无法存入.然而对ρ-形轨道,h和c一定能存入.对所有情况下面几个量都可以存入:o.1(轨道中的最大距离),h.1(柄里的最大距离),以及c.1(环里的最大距离).这使我们可以实现一个过程,它返回一个三元组来表示轨道的完整结构,其三个成员分别是:

template<typename F> requires(Transformation(F))
triple<DistanceType(F), DistanceType(F), Domain(F)>
orbit structure nonterminating orbit(const Domain(F)& x, F f)
{ typedef DistanceType(F) N; Domain(F) y = connection point nonterminating orbit(x, f); return triple<N, N, Domain(F)>(distance(x, y, f), distance(f(y), y, f), y);
}

template<typename F, typename P> requires(Transformation(F) &&
UnaryPredicate(P) && Domain(F) == Domain(P)) triple<DistanceType(F), DistanceType(F), Domain(F)> orbit structure(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
typedef DistanceType(F) N;Domain(F) y = connection point(x, f, p);N m = distance(x, y, f);N n(0);if (p(y)) n = distance(f(y), y, f);
//终止时:m=h.1∧n=0//否则:m=h∧n=c.1
return triple<N, N, Domain(F)>(m, n, y);
}

练习2.4请推导出本章各算法中使用不同操作(f,p,相等)的次数的公式.
练习2.5用orbitstructurenonterminatingorbit确定在你所使用的平台上的伪随机数生成器对不同种子值的平均柄规模和环路规模.