重複のない6桁の数字をIDとして採番するアルゴリズムを教えて下さい。

Question

・カウントアップを利用しその連番数をスクランブルすることで予測の困難な6桁のユニーク値を生成させたい
・アクセスかなにかリクエストのたびにユニークナンバーを発生させたい

下記URLのアルゴリズムでいけるかと思ったのですが
桁数の調節がうまくできません。
どなたかアドバイスお願い致します。

http://q.hatena.ne.jp/1377468971
http://cs.hatenablog.jp/entry/2013/06/19/135527

Answer 1

http://cs.hatenablog.jp/entry/2013/06/19/135527 の中の人です。

• かけ算が桁あふれしないように64ビット整数を使う。
• かけ算したらすぐに % 1000000 する。
• ビットの上下を入れ替える計算は、10進桁の上限を入れ替えるように書くのでもだいたいOK。

これでいけると思います。
奇数の組はもう用意できましたか？

Comments

[aoyahiro777]

お返事頂きありがとうございます。
恐縮ですが数学部分のロジックがきちんと理解できず応用も理解できません。

http://q.hatena.ne.jp/1377468971
のPHPコードに数字を色々といれてみた所、
例えば　１を入れた時に9桁になったんですが（948451296）
これは
桁あふれの影響なのでしょうか？
64ビット整数を使うことで回避できるのでしょうか？

重ねて質問してすみませんがよろしくお願いします。

[yuba]

はてなの方で回答したPHPのコードは、31ビットで意図的に桁あふれさせています。
7FFFFFFF と論理積を取っているところですね。
今回は、代わりに1000000で剰余を取ります。

[aoyahiro777]

ありがとうございます！
参考にした記事かいてる方に答えてもらえてうれしいです！

答えを参考に勉強しながら週末に実装してみようと思います！

[yuba]

// 奇数その1の乗算
$v *= 654321;
$v %= 1000000;

// 桁上下逆転
$v = floor($v / 1000) + (($v % 1000) * 1000);

// 奇数その2（奇数その1の逆数）の乗算
$v *= 81;
$v %= 1000000;

こんな感じです。

[inugadaisuki]

こちらの記事を参考にさせていただいているのですが、わからない部分があり、ご質問させていただきました。
「奇数その2（奇数その1の逆数）」で利用している、「81」という数字ですが、
これはどこから出てきた数字なのでしょうか。

よろしくお願いいたします。

[yuba]

拡張ユークリッドの互除法という手法で求まる、654321の逆数です（10000000を法とした逆数）。

[inugadaisuki]

ご回答ありがとうございます。理解できました。
参考にさせていただきます!!