BASICでのhex文字toバイナリ変換テクニック [その他]
twitterのTLにBASICで16進文字を2進数4文字へ変換するテクニックとして
という手法が懐かしさを込めて紹介されていました。
更に、awkを使って検証した結果も紹介されていました。ブログへのツイートの埋め込みは著作権上問題が無いようなので判り易いように該当ツイートを貼らさせて頂きます。
★変更 2021/10/06
ツイート埋め込みではなくリンクに変更
https://twitter.com/houmei/status/1444776993673957382
このような探索系の問題は興味をそそられますね。
少し考えてみると 0..F の16個の文字の順列問題のように思えます。perlであればMath::Combinatoricsを使えば順列問題を解けますが、並べる初期段階でも今回の問題の答えとして大丈夫なのかチェックすることで探索範囲を枝刈りするために再起呼び出しにより自前で順列処理するようにしました。
作成したperlのソースは下記になります。Search()内でデータチェックしつつ再起呼び出しで順列を作っています。
★変更 2021/10/06
Ver 0.02 変換元及び変換先を変更可能とし、若干高速化したバージョンにソースを差換え
★変更 2021/10/07
Ver 0.03a 最適化して高速化 32進数 ⇒ 2進数 の処理の実行時間が 22.1sec ⇒ 5.4sec
★変更 2021/10/08
Ver 0.03b 若干高速化 32進数 ⇒ 2進数 の処理の実行時間が 5.4sec ⇒ 4.6sec
★変更 2021/10/08
Ver 0.03c 15進数の場合等でエラーが発生するようになったので修正。実行時間: 4.7sec
出力結果は下記のように256通りのデータペアが検出されました。
因みに上記ソースの$MaxLenを16から8に変更すると下記のような8進数用の変換データが出力されます。
★追記 2021/10/04
$MaxLenを4に変更して調べてみると下記のように4通りのデータペアが検出されました。
このことからN進数のバイナリ変換用データペア数は 2^(N/2) と推測されますが、これを証明するのはかなり難しいと思われます。
数学での新たな難問として「N進数バイナリ変換データペア数予想」を提案させていただきますw
同様に16進数から4進数への変換の場合の検証結果も貼っておきます。データベア数は
331776 = (2^12)*(3^4)
になっています。一見すると不思議な数字ですが、先に書いた4進数から4進数への変換は4文字の順列であったことを加味して考えると、規則性が見えてきます。
つまり、変換データペア数の算出には順列計算(階乗)が関連していて、N進数からM進数への変換の場合の変換データペア数は
( M! ) ^ ( N / M )
となり、更に一般化した「N進数からM進数への変換データペア数予想」へ展開できました。最初の頃は予想の式内に '2' というマジックナンバーが何故でてくるのか気になっていましたが、今回の一般化でマジックナンバーはなくなり、簡潔で美しい式になりました。
★追記 2021/10/05
素因数分解はWindowsの電卓を使って手作業でやっていましたがweb上で高速に素因数分解できるサイトがあったのでリンクを貼っておきます。
★追記 2021/10/06
9進数から3進数への変換の場合のデータペア数を確認してみた結果を下記に示します。
予想通り 216 = ( 3! ) ^ ( 9 / 3 ) でした。
また、10進数から2進数や6進数から3進数への変換の場合は解がありませんでした。変換元の最大値を変換先進数に変換後、+1すると桁数が増える場合、つまり
N=M^L L:自然数
の時だけ解がある本予想が成立するものと推測されます。★訂正 2021/10/06
★追記 2021/10/06
変換元として2進数から16進数までを2進数に変換する場合のデータペア数を確認しましたので追記します。
★追記 2021/10/08 17~33を追加
★追記 2021/11/09
27進数から3進数への変換に関するTwiiterに投函したメッセージを貼っておきます。
P=INSTR("36DA5B7FEC924801", H$) |
B$=MID$("0011010111100100001", P, 4) |
という手法が懐かしさを込めて紹介されていました。
更に、awkを使って検証した結果も紹介されていました。ブログへのツイートの埋め込みは著作権上問題が無いようなので
★変更 2021/10/06
ツイート埋め込みではなくリンクに変更
https://twitter.com/houmei/status/1444776993673957382
このような探索系の問題は興味をそそられますね。
少し考えてみると 0..F の16個の文字の順列問題のように思えます。perlであればMath::Combinatoricsを使えば順列問題を解けますが、並べる初期段階でも今回の問題の答えとして大丈夫なのかチェックすることで探索範囲を枝刈りするために再起呼び出しにより自前で順列処理するようにしました。
作成したperlのソースは下記になります。Search()内でデータチェックしつつ再起呼び出しで順列を作っています。
変換用データ生成プログラム(perl) |
|
★変更 2021/10/06
Ver 0.02 変換元及び変換先を変更可能とし、若干高速化したバージョンにソースを差換え
★変更 2021/10/07
Ver 0.03a 最適化して高速化 32進数 ⇒ 2進数 の処理の実行時間が 22.1sec ⇒ 5.4sec
★変更 2021/10/08
Ver 0.03b 若干高速化 32進数 ⇒ 2進数 の処理の実行時間が 5.4sec ⇒ 4.6sec
★変更 2021/10/08
Ver 0.03c 15進数の場合等でエラーが発生するようになったので修正。実行時間: 4.7sec
出力結果は下記のように256通りのデータペアが検出されました。
変換用データ生成プログラムの実行結果 |
|
因みに上記ソースの$MaxLenを16から8に変更すると下記のような8進数用の変換データが出力されます。
8進数の変換用データの出力結果 |
|
★追記 2021/10/04
$MaxLenを4に変更して調べてみると下記のように4通りのデータペアが検出されました。
このことからN進数のバイナリ変換用データペア数は 2^(N/2) と推測されますが、これを証明するのはかなり難しいと思われます。
数学での新たな難問として「N進数バイナリ変換データペア数予想」を提案させていただきますw
4進数の変換用データの出力結果 |
|
★追記 2021/10/05
32進数の場合について確かめてみました。16以降の表現は16進数を踏襲して'G'から'V'までのアルファベットを割り振っています。
「N進数バイナリ変換データペア数予想」では 65536(=2^(32/2) 通りのデータペアがあるはずですが結果は下記の通り、予想と一致していました。
32進数の場合について確かめてみました。16以降の表現は16進数を踏襲して'G'から'V'までのアルファベットを割り振っています。
「N進数バイナリ変換データペア数予想」では 65536(=2^(32/2) 通りのデータペアがあるはずですが結果は下記の通り、予想と一致していました。
32進数の変換用データの出力結果 |
|
★追記 2021/10/05
今まで変換先を2進数とした場合についてのみ考えてきましたがM進数への変換を考えてみました。
4進数から4進数への変換を検証すると下記のように24通りのデータペアが出力されました。よく見てみると(考えて見れば当然ですが)0..3の4文字の順列になっていることが判ります。
今まで変換先を2進数とした場合についてのみ考えてきましたがM進数への変換を考えてみました。
4進数から4進数への変換を検証すると下記のように24通りのデータペアが出力されました。よく見てみると(考えて見れば当然ですが)0..3の4文字の順列になっていることが判ります。
4進数から4進数への変換用データの出力結果 |
|
同様に16進数から4進数への変換の場合の検証結果も貼っておきます。データベア数は
331776 = (2^12)*(3^4)
になっています。一見すると不思議な数字ですが、先に書いた4進数から4進数への変換は4文字の順列であったことを加味して考えると、規則性が見えてきます。
つまり、変換データペア数の算出には順列計算(階乗)が関連していて、N進数からM進数への変換の場合の変換データペア数は
( M! ) ^ ( N / M )
となり、更に一般化した「N進数からM進数への変換データペア数予想」へ展開できました。最初の頃は予想の式内に '2' というマジックナンバーが何故でてくるのか気になっていましたが、今回の一般化でマジックナンバーはなくなり、簡潔で美しい式になりました。
16進数から4進数への変換用データの出力結果 |
|
★追記 2021/10/05
素因数分解はWindowsの電卓を使って手作業でやっていましたがweb上で高速に素因数分解できるサイトがあったのでリンクを貼っておきます。
★追記 2021/10/06
9進数から3進数への変換の場合のデータペア数を確認してみた結果を下記に示します。
予想通り 216 = ( 3! ) ^ ( 9 / 3 ) でした。
また、10進数から2進数や6進数から3進数への変換の場合は解がありませんでした。変換元の最大値を変換先進数に変換後、+1すると桁数が増える場合、つまり
N=M^L L:自然数
の時だけ
9進数から3進数への変換用データの出力結果 |
|
★追記 2021/10/06
変換元として2進数から16進数までを2進数に変換する場合のデータペア数を確認しましたので追記します。
★追記 2021/10/08 17~33を追加
|
|
★追記 2021/11/09
27進数から3進数への変換に関するTwiiterに投函したメッセージを貼っておきます。
27進数から3進数への変換用データペア数のオレオレ予想では
— skyriver (@wcinp) October 9, 2021
10077696 = (3!)^(27/3)
プログラムで検証した結果、最後のデータは
No.10077696
QPNHOK7MEGLB6J5FI14DCA39028
22212202112102012001110100022
流石に結構時間が掛かった
コメント 0