ときどきの雑記帖 RE* (新南口)
The Hunt for Red October
今週のしずえさん
「バナナの斑点」
バイト&ワードの風にのって
ところでふとN-BASIC時代の16進文字→2進4文字の変換テクニックとか思い出した。コードサイズを小さくするやつで。
— 29#色々作るひと (@MyCPU8) October 2, 2021
P=INSTR("36DA5B7FEC924801", H$) ;
B$=MID$("0011010111100100001", P, 4)
みたいなの。なつかしい。
これ知らんかったのでawkで検証してみたら256通りあった。なお小文字a-fも含むパターンでもやってみたけど見つからなかった。https://t.co/wTs4v8ytju https://t.co/PjHnhlVol1
— ほうめい マイコンで遊んでばっかりで (@houmei) October 3, 2021
BASICでのhex1文字をバイナリ文字列に変換するテクニックである
— skyriver (@wcinp) October 4, 2021
P=INSTR("36DA5B7FEC924801", H$) ;
B$=MID$("0011010111100100001", P, 4)
用のデータペアがいくつあるかの問題は面白そうですね
perlで検証してみました
更に8進数用のデータペアは16通りでしたhttps://t.co/tWcvwZa9at https://t.co/7NmDKf5cAc
16進数の場合256通り、8進数の場合16通りで、4進数で調べたら4通りだった
— skyriver (@wcinp) October 4, 2021
このことからN進数の場合のデータペア数は
2^(N/2)通り
と推測されるがこの証明はかなり難しいと思われる
新たな難問である「N進数バイナリ変換データペア数予測」を提案できたよw https://t.co/VKoiAI75Xh
BASICでのhex文字toバイナリ変換テクニック:PICマイコンは面白い:So-netブログ
という話題に関連したことをつらつらと。 わたしの記憶が確かならば(というフレーズがどのくらいの人に通じるのか🤔)
の中にこの種の文字列を求めるものがありました。 家のどこかにこの本まだあるはずなんですが、すぐに出せそうにないので確認できません。 ということで記憶を掘り起こしながら書くと、まずは
0---1---2---3---4---5---6---7---8---9---A---B---C---D---E---F---
0000000100100011010001010110011110001001101010111100110111101111
という埋め草つきの文字列から始めます。
ぱっと見ですぐに短くできそうなのは先頭のここですね。
012--3---4---5---6---7---8---9---A---B---C---D---E---F---
000100011010001010110011110001001101010111100110111101111
もうひとつは末尾のここ(順番の入れ替えがありますが)。
012--3---4---5---6---8---9---A---B---C---D---E--7F---
00001001101000101011010001001101010111100110111101111
ほかにもいくつかできるところが見つけられますが それはまあ止めておいて。
記事ではここから、最短の列を求めるアルゴリズムを紹介していました。 たしか最初に4ビット(16進一桁)くらいの「種」を用意して、 そこからビット演算(xorだったような気がする)を使って求めるというものだったと思います。
古い本なので図書館にもないだろうなと思いつつも検索してみると、 国会図書館と都立中央図書館(の多摩の方)にはあるようです。 ただどちらも時節柄ふらっと行くのも面倒そうです (都立中央、広尾の方なら会社帰りにでも行けなくはなかった。 あと国会図書館の方、デジタル閲覧はできないのかな)。
さてこの本の問題の記事ですが、 バイト&ワードの風にのって―だれでも読める小さなコンピュータの話 | 林 晴比古 |本 | 通販 | Amazon の説明に
月刊Oh!PCで好評連載中のパソコン・エッセイに前シリーズ「ちょっと一服」ほか、オリジナル・ショートショートを加えて再構成。 筆者がユニークな視点から描く小さなコンピュータの大きな世界に、また新しい発見が!
とある通り、書き下ろしのものではなく 元々は雑誌(Oh!PC)に掲載されたものだと思われます。 本の発行が
出版社: ソフトバンククリエイティブ (1986/9/1)
発売日: 1986/9/1
単行本: 286ページ
ISBN-10: 4930795486
ISBN-13: 978-4930795489
本の発売が1986年なので、収録されている記事が掲載された号の発行は80年代前半でしょうか。 パソコン(マイコン)雑誌についてはアスキーやI/Oなら 国会図書館や都立中央図書館にありますが(何度か閲覧と複写にいったことがあります)、 「Oh!なんちゃら」の類は (MZとかFMとか含め) なかったような気がするなあ。
それと大元のツイートでは「N-BASIC」とありますから、 おそらく同様の記事が これよりも先行してあったのではないかと思いますが、 探すのはちょっと骨が折れそうですね(情報求む)。
また、海の向こうのBYTE誌 (Byte (magazine) - Wikipedia) やDr. Dobb’s Journal (Dr. Dobb’s Journal - Wikipedia)辺りでも 取り上げていそうな気がします(が、調べるあてはない)。
ということだけで片づけてはイマイチなので色々と検索してみると、 なかなか興味深い(と自分は思った)結果が得られました。
ということで以下に検索の時系列に沿って書いていきます。
256?
と書いておいてなんですが、まずは与太話的な話題から。
さて、先のツイートやそこから派生したblog記事では 「256種類」という数字が出ていましたが、 果たしてそうでしょうか?
たとえば0124936DA5B7FEC8
を例にとります。
これを一文字ずつローテ―トしていくと
0124936DA5B7FEC8
124936DA5B7FEC80
24936DA5B7FEC801
4936DA5B7FEC8012
936DA5B7FEC80124
36DA5B7FEC801249
6DA5B7FEC8012493
DA5B7FEC80124936
A5B7FEC80124936D
5B7FEC80124936DA
B7FEC80124936DA5
7FEC80124936DA5B
FEC80124936DA5B7
EC80124936DA5B7F
C80124936DA5B7FE
80124936DA5B7FEC
となりますが、ローテート結果と同じものがすべて256個の中に見つかります。 そこで
DATA.each_line do |line|
line.chomp!
#puts line
pos = line.index('0')
if pos == 0 then
puts line
else
puts line[pos..-1] + line[0..pos-1]
end
end
__END__
0124936DA5B7FEC8
0124937FEDA5B6C8
0125A4936DB7FEC8
0125A4937FEDB6C8
以下略
のようなやっつけスクリプトで 256個のパターンすべてについて 0が先頭に来るようにローテートした上で 重複を取り除くと
>ruby rotate.rb | sort | uniq -c
16 0124936DA5B7FEC8
16 0124937FEDA5B6C8
16 0125A4936DB7FEC8
16 0125A4937FEDB6C8
16 0125B6C937FEDA48
16 0125B6DA4937FEC8
16 0125B7FEC936DA48
16 0125B7FEDA4936C8
16 0136C925B7FEDA48
16 0136DA4925B7FEC8
16 0136DA5B7FEC9248
16 0136DB7FEC925A48
16 0137FEC925B6DA48
16 0137FEDA4925B6C8
16 0137FEDA5B6C9248
16 0137FEDB6C925A48
こうなりました。
DATA.each_line do |line|
line.chomp!
pos = line.index('0')
if pos == 0 then
printf "%s %s\n", line, line
else
printf "%s %s\n", line[pos..-1] + line[0..pos-1], line
end
end
__END__
まあローテートして同じになるものを「同一のもの」とみなすかどうか という立ち位置次第なのですけど。
検索
ひょっとしてどこかに問題の文字列生成のアルゴリズムが書かれた記事があるのではないかと 検索しても、見つかるのは
- How to convert a hexadecimal string to a binary string in C - Stack Overflow
- c++ - Convert strings between hex format and binary format - Stack Overflow
- java - Convert hexadecimal string (hex) to a binary string - Stack Overflow
こういうものばかり。 それでも挫けず色々検索ワードを変えたり GoogleじゃなくBingを使ったりしてみると
- A easy way to transform Hex to Bin by two string. · GitHub
- Hexadecimal Sprite Thing - Cemetech | Forum | Your Projects [Topic]
- 八进制和十六进制与二进制的转换及对应字符串_z_wenqian的专栏-CSDN博客
- Conversion of octal and hexadecimal to binary and corresponding strings(Others-Community)
生成アルゴリズムには至らないものの、いくつか (言語がBASICでないものも含め)同じロジックを使ったものが見つかり、 そこから
Binary Circles
という記事にたどり着きました。 この記事に手作業で問題の文字列(のパターンの一つ)を求める手順がありますので、 興味のある方は是非手を動かして確かめてみてください😄
そしてこの記事で新しいキーワード「Binary Circles」 が見つかったのでそれを使うと、 Project Eulerにとても関係ありそうな問題が見つかりました。
Project Euler #265
この265番の問題はこうです(上記のリンク先からの転載。図は省略)
2^N binary digits can be placed in a circle so that all the N-digit clockwise subsequences are distinct.
For N=3, two such circular arrangements are possible, ignoring rotations:
For the first arrangement, the 3-digit subsequences, in clockwise order, are:
000, 001, 010, 101, 011, 111, 110 and 100. Each circular arrangement can be encoded as a number by concatenating the binary digits starting with the subsequence of all zeros as the most significant bits and proceeding clockwise. The two arrangements for N=3 are thus represented as 23 and 29:
00010111 2 = 23
00011101 2 = 29Calling S(N) the sum of the unique numeric representations, we can see that S(3) = 23 + 29 = 52.
Find S(5).
2&sup{N}; の2進数の数字は, 時計回りに N 桁連続する数字全てで網羅するように円状に並べることができる.
例えば N=3 では, 回転を無視すると2 つの円状の配置が可能である.
p_265_BinaryCircles.gif最初の配置では, 時計回りの3桁の数列は: 000, 001, 010, 101, 011, 111, 110, 100 である.
それぞれの円形の配置は, 全部が 0 であるような数列を最上位にして時計回りに数字をつなげることで, 1 つの数に変換できる.
N=3 の 2つの配置は 23 と 29 になる:
00010111 &sub{2}; = 23
00011101 &sub{2}; = 29S(N) を異なる変換した数の合計とすると, S(3) = 23 + 29 = 52 となる.
S(5) を求めよ.
「プロジェクトオイラー 265」、「Project Euler 265」で検索すると、 解法や解説が色々見つかります。
- project euler 265 - Bing
- プロジェクトオイラー問265 - sinapusu2002 @ ウィキ - atwiki(アットウィキ)
- 265:Binary Circles - ichirin2501’s diary
- Project Euler 265(1) - inamori’s diary
- Project Euler 265(2) - inamori’s diary
- Project Euler - PukiWiki
- Project-Euler-solutions/p265.py at master · nayuki/Project-Euler-solutions · GitHub
- Project Euler 265 / 2進円 - mathematicaで遊ぼう
また、和田先生のblogにも関係ありそうな記事が見つかりました。
de Bruijn
最も右のビットの位置を知る法
TAOCPにある第二の方法はde Bruijnサイクルを利用するものだ.
4ビットのde Bruijnサイクルは例えば次のようなものである.
TAOCPにあたるのはとりあえず後回しにして (そもそもどの巻なんだろう…)、 TAPLの読書会でも散々目にした「de Bruijn」の名前がここで登場したので
追記
Volume 4Aでした。 日本語版だと295ページからです。
「de Bruijn サイクル」、「de Bruijn cycle」、「de Bruijn 列」、 「de Bruijn シーケンス」、「de Bruijn sequence」 等々で検索すると…
De Bruijn sequence (De Bruijn 列)
- de Bruijn sequence - Wikipedia
- 補足 - 繰り返しのない列
- 『系列Mをまわせ』
- De Bruijn sequence を列挙するコード - 当面C#と.NETな記録
- Perturbations of Binary de Bruijn Sequences
- MathémagieMathémagie et audelàet aude
- De Bruijn Sequence - roki.log
- de Bruijn列でBSR32をO(1)で実装できる理由
- De Bruijn列 - Thoth Children
- de Bruijn 族のグラフの分解及び情報散布への応用に関する研究
といったものが見つかります。
ラスボス(de Bruijn)に遭遇したし、もうこの辺でいいですよね?😄
おまけ
なお小文字a-fも含むパターンでもやってみたけど見つからなかった。
小文字のa-fも大文字のA-Fと同じビットパターンとすると全単射じゃなくなるので そもそもそんなパターンは存在しないんじゃなかろうかと思うのですが、 (大小文字で別のビットパターンになる)10+6+6個の「文字」とすれば その「最短」を求められなくもなさそうです。 (「A」と「a」で別のビットパターンになってしまうので)それに意味があるかどうかは別の話ですが。
いじょ。
アナログ・コンピューター
2021年式アナログ・コンピューター、Anabrid「The Analog Thing」がデビュー…… 小型で安価、しかし本格的なアナログコンピュータ - ICON
この記事中に
1940年代のアナログ・コンピューター、“Colossus”
という記述があるんだけど、コロッサス(Colossus)ってアナログマシンだったっけ?
にはそんな記述は見落としていなければないと思うんだけどどこから湧いて出たんだろう?>「アナログ・コンピューター」
ちなみに Colossus - Wikipedia によれば、デジタルマシンで間違いないようです。
Colossus はプログラム可能な電子デジタルマシンだが、そのプログラム機能は次のような点で限定されたものだった[4]。
- プログラムは内蔵式ではない。新たなタスクを設定するには、オペレータがプラグ盤とスイッチ群を操作して配線を変更する。
- 汎用性はなく、計数とブール演算という暗号解読に特化した設計である。
したがって、ある程度の柔軟性はあるが、自由にプログラム可能とは言えず、ある種の専用計算機である、ということになる。
「世界初のコンピュータはどれか」という議論(本質は「コンピュータ」の定義次第であるが)で本機とよく比較される機械について以下に述べる。 コンラート・ツーゼの Zuse Z3 は世界初のプログラム制御式の完全機能するコンピュータであり、 ベル研究所でジョージ・スティビッツらによって1930年代後半に開発されたマシンと同様、電気機械式リレーを使用していた。 アタナソフ&ベリー・コンピュータは電子式で2進数を使用していたが、プログラム可能ではなかった。 ヴァネヴァー・ブッシュらが1930年代以前から開発していたアナログコンピュータは半プログラム可能であった。 チャールズ・バベッジの解析機関はこれら全てに先行していたし(19世紀中盤)、デジタル式でプログラム可能だったが、 部分的にしか制作されず、当時は機能しなかった(ただし、階差機関のレプリカは1991年に製作され動作した)。 Colossus は、「デジタル」式で「プログラム可能」で「電子」式であるという組合せでは世界初であるが、汎用性は低かった。 より高い汎用性は1946年に開発されたENIACで実現された。いずれにしろプログラム内蔵方式ではなく、 同方式により実現されるような柔軟なプログラム可能性もない。