Macr055で二進化他

次の http://parametron.blogspot.jp/2015/02/christopher-stracheygpm_8.html の記事に移って、二進化他。

二進化

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|
    {m55_define|p|`{lt|{1-|$1}|$2}'}}'}
    {m55_define|-1|t}
    {m55_define|$2|f}}'}{m55_dnl}
{m55_define|b|`{{lt|$1|2}|
  {m55_define|t|`{$2|
    {m55_define|$2|`{b|$2|0}$1'}
    {m55_define|0|$1}}'}
  {m55_define|f|`{b|{1-|{1-|$1}}|{1+|$2}}'}}'}{m55_dnl}
{b|0|0}, {b|1|0}, {b|2|0}, {b|3|0}, {b|4|0}
{b|5|0}, {b|6|0}, {b|7|0}, {b|8|0}, {b|9|0}

2項係数

（現状の）M55ではローカル定義のマクロでは再帰的に展開できないため（最初の展開が終わった時点でローカル定義が消えてしまうため）bb というマクロはトップレベルで定義している。

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|+|`{$1|
  {m55_define|$1|`{1+|{+|{1-|$1}|$2}}'}
  {m55_define|0|$2}}'}{m55_dnl}
{m55_define|b|`{$2|
  {m55_define|$2|`{+|{b|{1-|$1}|$2}|{b|{1-|$1}|{1-|$2}}}'}
  {m55_define|0|1}
  {m55_define|$1|1}}'}{m55_dnl}
{m55_define|binom|`{bb|$1|0}'}{m55_dnl}
{m55_define|bb|`{$2|
  {m55_define|$2|`{b|$1|$2}, {bb|$1|{1+|$2}}'}
  {m55_define|$1|1}}'}{m55_dnl}
#{b|4|0}, {b|4|1}, {b|4|2}, {b|4|3}, {b|4|4}
{binom|0}
{binom|1}
{binom|2}
{binom|3}
{binom|4}
{binom|5}

素数テスト

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|-|`{$2|
  {m55_define|$2|`{-|{1-|$1}|{1-|$2}}'}
  {m55_define|0|$1}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|
    {m55_define|p|`{lt|{1-|$1}|$2}'}}'}
  {m55_define|-1|t}
  {m55_define|$2|f}}'}{m55_dnl}
{m55_define|r|`{{lt|$1|$2}|
  {m55_define|t|$1}
  {m55_define|f|`{r|{-|$1|$2}|$2}'}}'}{m55_dnl}
{m55_define|p?|`{p|2|$1}'}{m55_dnl}
{m55_define|p|`{$1|
  {m55_define|$1|`{{r|$2|$1}|
    {m55_define|{r|$2|$1}|`{p|{1+|$1}|$2}'}
    {m55_define|0|f}}'}
  {m55_define|$2|t}}'}{m55_dnl}
{p?|2}
{p?|3}
{p?|4}
{p?|5}
{p?|6}
{p?|7}
{p?|8}
{p?|9}

tarai

途中経過を確認するために、マクロ展開するのではなく出力に直接書き出す特殊マクロ m55_write をM55に追加した。tarai 8 4 0 にするとすぐには待っていられないぐらい時間が掛かるので 6 3 0 としている。

{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|
    {m55_define|p|`{lt|{1-|$1}|$2}'}}'}
  {m55_define|-1|t}
  {m55_define|$2|f}}'}{m55_dnl}
{m55_define|tarai|`{m55_write|tarai $1 $2 $3
}{{lt|$2|$1}|
  {m55_define|f|$2}
  {m55_define|t|`{tarai|{tarai|{1-|$1}|$2|$3}|{tarai|{1-|$2}|$3|$1}|{tarai|{1-|$3}|$1|$2}}'}}'}{m55_dnl}
{tarai|6|3|0}

不要な空白類をstripする手段は現状無いため詰め詰めに書いているが、もし対処するとしたら、どういう仕様の特殊マクロが良いだろうか。