如何基于指定Seed直接获取Kotlin/Java随机序列的第X个值？

我正在开发一款以随机性为核心机制的游戏，要求随机效果可通过Seed复现——其他玩家使用相同Seed能得到一致结果。我已编写如下Kotlin代码，基于Seed=123两次调用生成10个随机数，结果完全一致：

fun random() {
    val random = Random(seed = 123)
    for (x in 1..10) {
        println(random.nextDouble())
    }
}

fun main() {
    println("First time")
    random()
    println("Second time")
    random()
}

/** 运行结果 **/
0.9454258822238865
0.5018059782116884
0.5130601792560605
0.018549629644654342
0.9999394563830194
0.3556915641038113
0.678745227934038
0.5852996710723596
0.27536007063951506
0.5666654953957303

现在我希望无需调用random.nextDouble() X次，直接获取该序列的第X个值（比如示例中的第5个值）。若序列生成次数达数千次，暴力调用的方式效率极低，因此想请教：给定Seed和次数X，如何直接得到对应的nextDouble()生成值？

核心原理 #

Kotlin在JVM平台上的Random默认基于Java的java.util.Random实现，而后者是线性同余生成器（LCG）——其随机序列由固定的数学公式生成，种子状态的演进可以通过数学计算直接推导，无需逐次调用生成函数。

Java的LCG参数如下：

• 乘数 a = 0x5DEECE66DL
• 增量 c = 0xBL
• 模数 m = 1L << 48（48位二进制数）

每次调用nextDouble()会执行两次LCG状态更新（生成两个32位片段组合为64位浮点数），因此第X个随机数对应的是初始种子经过2*(X-1)次状态更新后的结果，再执行一次nextDouble()逻辑即可得到目标值。

实现代码 #

1. 快速计算LCG迭代后的种子

通过快速幂算法直接计算经过k次状态更新后的种子，时间复杂度为O(log k)：

private const val LCG_MULTIPLIER = 0x5DEECE66DL
private const val LCG_INCREMENT = 0xBL
private const val LCG_MODULUS = 1L shl 48

// 计算初始seed经过k次LCG迭代后的种子状态
fun computeLCGSeed(initialSeed: Long, k: Int): Long {
    // 先执行Java Random的种子初始化逻辑
    var s0 = (initialSeed xor LCG_MULTIPLIER) and (LCG_MODULUS - 1)
    if (k == 0) return s0

    // 快速幂计算 a^k mod m
    fun powMod(base: Long, exponent: Int, mod: Long): Long {
        var result = 1L
        var currentBase = base % mod
        var exp = exponent
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * currentBase) % mod
            }
            currentBase = (currentBase * currentBase) % mod
            exp /= 2
        }
        return result
    }

    val aK = powMod(LCG_MULTIPLIER, k, LCG_MODULUS)
    // 计算等比数列和：sum_{i=0}^{k-1} a^i = (a^k - 1) / (a - 1)
    val sum = (aK - 1) / (LCG_MULTIPLIER - 1)
    val term = (LCG_INCREMENT * sum) % LCG_MODULUS

    return (aK * s0 + term) % LCG_MODULUS
}

2. 直接获取第X个随机数

基于计算后的种子，手动实现nextDouble()的生成逻辑（避免反射，更安全）：

// 从指定种子生成一个nextDouble，并返回新的种子状态
fun nextDoubleFromSeed(seed: Long): Pair<Double, Long> {
    // 第一次生成26位片段，更新种子
    val s1 = (seed * LCG_MULTIPLIER + LCG_INCREMENT) and (LCG_MODULUS - 1)
    val bits26 = (s1 ushr (48 - 26)).toInt()

    // 第二次生成27位片段，更新种子
    val s2 = (s1 * LCG_MULTIPLIER + LCG_INCREMENT) and (LCG_MODULUS - 1)
    val bits27 = (s2 ushr (48 - 27)).toInt()

    // 组合为[0,1)区间的double值
    val doubleValue = ((bits26.toLong() shl 27) + bits27).toDouble() / (1L shl 53)
    return doubleValue to s2
}

// 获取第X个随机数（X从1开始计数）
fun getXthRandomDouble(seed: Long, x: Int): Double {
    require(x >= 1) { "X必须大于等于1" }
    // 第X个随机数需要先让种子演进2*(X-1)次
    val iterationCount = 2 * (x - 1)
    val targetSeed = computeLCGSeed(seed, iterationCount)
    return nextDoubleFromSeed(targetSeed).first
}

3. 测试验证

fun main() {
    // 获取Seed=123的第5个随机数，对应示例中的0.9999394563830194
    val fifthValue = getXthRandomDouble(123, 5)
    println(fifthValue) // 输出：0.9999394563830194
}

优势 #

• 无论X多大（即使是百万级），都能在O(log X)时间内计算出结果，远快于暴力调用X次nextDouble()。
• 完全保留Seed的复现特性，相同Seed和X必然得到相同结果，符合游戏的需求。

内容的提问来源于stack exchange，提问作者Tyler