前書き

TypeScript のお勉強を始めたのですが, 言語になれるために AtCoder の簡単な問題を解いていました

ABC293E - Geometric Progression を解いていてシフト演算子を使ったら謎のバグでハマったときの話です

本文

こんなコードを書いていました

// judge
const lineit = (function* () { for (const line of require("fs").readFileSync("/dev/stdin", "utf8").split('\n')) yield line; })();
// local
// const lineit = (function* () { for (const line of require("fs").readFileSync("./dev/stdin", "utf8").split('\r\n')) yield line; })();
const wordit = (function* () { while (true) { let line = lineit.next(); if (line.done) break; for (const word of String(line.value).split(' ')) yield word; } })();
const charit = (function* () { while (true) { let word = wordit.next(); if (word.done) break; for (const char of String(word.value).split('')) yield char; } })();
const readline = () => String((lineit.next()).value);
const read = () => String((wordit.next()).value);
const readchar = () => String((charit.next()).value);


function main() : void {
  const a : bigint = BigInt(read());
  const x : number = Number(read());
  const m : bigint = BigInt(read());
  /*
  [a, 1] ^ x
  [0, 1]
  */

  const b = pow([a, 1n, 0n, 1n], x - 1, m);
  
  console.log(((b[0] + b[1]) % m).toString());
}

function mul(a:bigint[], b:bigint[], m:bigint) {
  const c:bigint[] = [0n, 0n, 0n, 0n];
  for(let i = 0; i < 2; ++i){
    for(let j = 0; j < 2; ++j){
      for(let k = 0; k < 2; ++k){
        c[i * 2 + j] += a[i * 2 + k] * b[k * 2 + j];
        c[i * 2 + j] %= m;
      }
    }
  }
  return c;
}

function pow(a:bigint[], n:number, m:bigint) {
  let res = [1n, 0n, 0n, 1n];
  while(n > 0){
    if(n % 2 == 1) res = mul(res, a, m);
    a = mul(a, a, m);
    n >>= 1;
  }
  return res;
}

main();

function range(s : number, t : number) : number[] {
  return (s < t) ? Array.from(Array(t - s), (val, idx) => s + idx) : [];
}

なんかよくわからんことしてると思いますが, 今回注目したいのはこの部分です

function pow(a:bigint[], n:number, m:bigint) {
  let res = [1n, 0n, 0n, 1n];
  while(n > 0){
    if(n % 2 == 1) res = mul(res, a, m);
    a = mul(a, a, m);
    n >>= 1;
  }
  return res;
}

所謂繰り返し二乗法というやつを書いていたのですが, n を半分にしていきたいということで n >>= 1 としています

すると, サンプル 1, 2 は会いましたがサンプル 3 が全然合いません

方針が間違ってるのかと思っていろいろと試してみたのですが全くうまくいかず, まさかと思ってこのように修正してみると答えが合いました

function pow(a:bigint[], n:number, m:bigint) {
  let res = [1n, 0n, 0n, 1n];
  while(n > 0){
    if(n % 2 == 1) res = mul(res, a, m);
    a = mul(a, a, m);
    n = Math.floor(n/2);
  }
  return res;
}

提出結果

なんでや右シフト一回したら同じことやろ！！！！！！！！！！！！

と思って調べてみたのですが, 冷静になって考えてみると JS/TS の number は整数型じゃありません 64bit浮動小数点数です

じゃあどうやってビット演算なんてやってるんだと思ったところ, なんと 32bit 整数に変換してから行っているようです (符号の有無は >> か >>> かで変わる)

ということで, 今回の制約では 32bit 整数だと余裕でオーバーフローする値が突っ込まれるので死亡していたということでした

そもそもデフォルトが固定小数点数じゃない時点でだいぶ違和感がありましたが, この仕様にはかなり驚きました

もし似たようなハマり方をした人がいたら (いるか？) 参考にしてください

JavaScript のビット演算がカスだった話

前書き

本文

参考文献