Блог

Я пытался решить задачу Advent of Code 2020, день 13, часть 2. Я нашел много подсказок, говорящих о чем-то, называемом китайской теоремой об остатках. Я пробовал некоторые реализации, следующие за nodejs-chinesse-remainders от npm, но эта реализация кажется довольно старой (2014), а также требует дополнительных библиотек для больших случаев Int.

Как я мог бы реализовать модульную мультипликативную обратную? Как я мог бы реорганизовать алгоритм CRT, определенный в модуле npm, для которого я предоставил ссылку?

В качестве самостоятельного ответа и с целью создания вики, чтобы найти это решение для тех, кому в будущем понадобится реализация CRT на javascript / typescript:

Сначала подумайте о том, чтобы реализовать модульную мультипликативную обратную, для этой задачи мы пытаемся найти x такое, что: a*x % modulus = 1

 const modularMultiplicativeInverse = (a: bigint, modulus: bigint) => {
  // Calculate current value of a mod modulus
  const b = BigInt(a % modulus);
    
    // We brute force the search for the smaller hipothesis, as we know that the number must exist between the current given modulus and 1
    for (let hipothesis = 1n; hipothesis <= modulus; hipothesis  ) {
        if ((b * hipothesis) % modulus == 1n) return hipothesis;
    }
      // If we do not find it, we return 1
    return 1n;
}
 

Затем, следуя статье и приведенному вами образцу кода:

 const solveCRT = (remainders: bigint[], modules: bigint[]) => {
    // Multiply all the modulus
    const prod : bigint = modules.reduce((acc: bigint, val) => acc * val, 1n);
    
    return modules.reduce((sum, mod, index) => {
        // Find the modular multiplicative inverse and calculate the sum
    // SUM( remainder * productOfAllModulus/modulus * MMI ) (mod productOfAllModulus) 
        const p = prod / mod;
        return sum   (remainders[index] * modularMultiplicativeInverse(p, mod) * p);
    }, 0n) % prod;
}
 

Таким образом, вы используете функции ES6, такие как reduce

Чтобы это работало с bigints, массив остатков и модулей должен соответствовать BigInt в ES2020

Например:

   x mod 5 = 1
  x mod 59 = 13
  x mod 24 = 7
 

 // Declare the problem and execute function
// You can not parse them to BigInt here, but TypeScript will complain of operations between int and bigint
const remainders : bigint[] = [1, 13, 7].map(BigInt)
const modules: bigint[] = [5, 59, 24].map(BigInt)

solveCRT(remainders, modules) // 6031