ときどきの雑記帖 RE* (新南口)

90億の神の御名

イ

日本一名前の長い植物・短い植物 ｜ 蒲田で接待にも使える鉄板焼き店なら鉄板焼　野澤

CDC6600

実際にコンピューターに計算させる前に色々あったんじゃないかという気がするけど それはさておき問題の式は

275 + 945 + 1105 + 1335 = 1445

で、右辺にある144の5乗ってどのくらいの大きさだろうと思ったので計算してみた。

(expt 144 5)
61917364224

ふむ。 が、この表記ではよくわからないのでもうちょっと工夫して

(log (expt 144 5) 10)
10.79181
(log (expt 144 5) 2)
35.84962

32bit integerには収まらないぐらいと。 つぎに、計算させたCDC 6600って(聞き覚えのある名前ではあったけど)どんな機械だっけと調べると

アーキテクチャ的には、CDC6600はCPUと周辺装置を制御する10台のPPUからなるヘテロマルチプロセサのシステムである。 CPUは1語60bitで、レジスタは整数と浮動小数点数で共用されていた。CDCは1文字を6bitで表わしており、 PPUは2文字を格納できる12bit語のプロセサであった。

浮動小数点数はさておき、60bitなら144^5も問題なく格納できるということですか。

↑のC#プログラムをほぼそのままCに置き換えて (ところで各forループの条件判定が <なので、n=200だと 199までの数値が対象になりますな)

#include <stdio.h>

int
main()
{
  const int n = 200;

  for (long long a = 1; a<n; a+=1)
    for (long long b = 1; b<n; b+=1)
      for (long long c = 1; c<n; c+=1)
        for (long long d = 1; d<n; d+=1)
          for (long long e = 1; e<n; e+=1) {
            if ((a*a*a*a*a + b*b*b*b*b + c*c*c*c*c + d*d*d*d*d) == (e*e*e*e*e)) {
              printf("%lld, %lld, %lld, %lld, %lld\n", a, b, c, d, e);
            }
          }
  return 0;
}

これをコンパイル&実行してみたところ…

kbk@toybox4:/mnt/c/Users/kbk/home/junk.test$ gcc cdc.c

kbk@toybox4:/mnt/c/Users/kbk/home/junk.test$ ./a
27, 84, 110, 133, 144
27, 84, 133, 110, 144
27, 110, 84, 133, 144
27, 110, 133, 84, 144
27, 133, 84, 110, 144
27, 133, 110, 84, 144
^C

6個目を出力した後しばらく待っても続きが出てくる気配がなかったので強制終了してしまったけど、 考えてみれば27, 84, 110, 133 の順序違いが出てきているのだから 次は 84, 27, 110, 133 で、そのあとも続けていって133, 110, 84, 27 までとなると どんだけ時間がかかるのか。

ということでちょっと考えて、 同じ組み合わせの別の並びを探す(試す)必要はなく、 また、4つの数字で同じものが現れることはない(だよね?)ので、 ループをこう書き換えてみた。

なんとなく学生時代のFORTRANを思い出したり。

#include <stdio.h>

int
main()
{
  const int n = 200;

  for (long long a = 1; a<n; a+=1)
    for (long long b = a+1; b<n; b+=1)
      for (long long c = b+1; c<n; c+=1)
        for (long long d = c+1; d<n; d+=1)
          for (long long e = 1; e<n; e+=1) {
            if ((a*a*a*a*a + b*b*b*b*b + c*c*c*c*c + d*d*d*d*d) == (e*e*e*e*e)) {
              printf("%lld, %lld, %lld, %lld, %lld\n", a, b, c, d, e);
            }
          }
    return 0;
}

これを実行するとこんな感じ。

kbk@toybox4:/mnt/c/Users/kbk/home/junk.test$ time ./a
27, 84, 110, 133, 144

real    1m35.077s
user    0m0.000s
sys     0m0.000s

これで済ませてもよいのだけど、ちょっと考えればeも1から計算する必要はないので (なんで1からにしたんだ＞自分)、

for (long long e = 1; e<n; e+=1) {

を

for (long long e = d+1; e<n; e+=1) {

とすると実行時間は

kbk@toybox4:/mnt/c/Users/kbk/home/junk.test$ time ./a
27, 84, 110, 133, 144

real    0m18.879s
user    0m0.000s
sys     0m0.000s

だいぶ速くなった😄

ここでふと、どんなコードを出力していたのか気になったので -Sオプションをつけてアセンブリ言語の出力をさせてみた。

main:
        pushq        %rbp
        .seh_pushreg        %rbp
        movq        %rsp, %rbp
        .seh_setframe        %rbp, 0
        subq        $96, %rsp
        .seh_stackalloc        96
        .seh_endprologue
        call        __main
        movl        $200, -44(%rbp)
        movq        $1, -8(%rbp)
        jmp         .L2
.L12:
        movq        -8(%rbp), %rax
        addq        $1, %rax
        movq        %rax, -16(%rbp)
        jmp         .L3
.L11:
        movq        -16(%rbp), %rax
        addq        $1, %rax
        movq        %rax, -24(%rbp)
        jmp         .L4
.L10:
        movq        -24(%rbp), %rax
        addq        $1, %rax
        movq        %rax, -32(%rbp)
        jmp         .L5
.L9:
        movq        $1, -40(%rbp)
        jmp         .L6
.L8:
        movq        -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        movq        %rax, %rdx
        movq        -16(%rbp), %rax
        imulq       -16(%rbp), %rax
        imulq       -16(%rbp), %rax
        imulq       -16(%rbp), %rax
        imulq       -16(%rbp), %rax
        addq        %rax, %rdx
        movq        -24(%rbp), %rax
        imulq       -24(%rbp), %rax
        imulq       -24(%rbp), %rax
        imulq       -24(%rbp), %rax
        imulq       -24(%rbp), %rax
        addq        %rax, %rdx
        movq        -32(%rbp), %rax
        imulq       -32(%rbp), %rax
        imulq       -32(%rbp), %rax
        imulq       -32(%rbp), %rax
        imulq       -32(%rbp), %rax
        addq        %rax, %rdx
        movq        -40(%rbp), %rax
        imulq       -40(%rbp), %rax
        imulq       -40(%rbp), %rax
        imulq       -40(%rbp), %rax
        imulq       -40(%rbp), %rax
        cmpq        %rax, %rdx
        jne         .L7
        movq        -24(%rbp), %r8
        movq        -16(%rbp), %rcx
        movq        -8(%rbp), %rax
        movq        -40(%rbp), %rdx
        movq        %rdx, 40(%rsp)
        movq        -32(%rbp), %rdx
        movq        %rdx, 32(%rsp)
        movq        %r8, %r9
        movq        %rcx, %r8
        movq        %rax, %rdx
        leaq        .LC0(%rip), %rcx
        call        printf
.L7:
        addq        $1, -40(%rbp)
.L6:
        movl        -44(%rbp), %eax
        cltq
        cmpq        %rax, -40(%rbp)
        jl          .L8
        addq        $1, -32(%rbp)
.L5:
        movl        -44(%rbp), %eax
        cltq
        cmpq        %rax, -32(%rbp)
        jl          .L9
        addq        $1, -24(%rbp)
.L4:
        movl        -44(%rbp), %eax
        cltq
        cmpq        %rax, -24(%rbp)
        jl          .L10
        addq        $1, -16(%rbp)
.L3:
        movl        -44(%rbp), %eax
        cltq
        cmpq        %rax, -16(%rbp)
        jl          .L11
        addq        $1, -8(%rbp)
.L2:
        movl        -44(%rbp), %eax
        cltq
        cmpq        %rax, -8(%rbp)
        jl          .L12
        movl        $0, %eax
        addq        $96, %rsp
        popq        %rbp
        ret

最適化オプションをつけないでもそこそこの最適化をするものだと思ってたけど、 なんか今一つなコードな感じ? たとえばa, b, c, d のそれぞれの5乗の計算は最内のループからは追い出してくれているかと期待していたけど そうではないっぽい。

ということで最適化(-O2)を指定したものを見ると

main:
        pushq        %r15
        .seh_pushreg        %r15
        pushq        %r14
        .seh_pushreg        %r14
        pushq        %r13
        .seh_pushreg        %r13
        pushq        %r12
        .seh_pushreg        %r12
        pushq        %rbp
        .seh_pushreg        %rbp
        pushq        %rdi
        .seh_pushreg        %rdi
        pushq        %rsi
        .seh_pushreg        %rsi
        pushq        %rbx
        .seh_pushreg        %rbx
        subq        $88, %rsp
        .seh_stackalloc        88
        .seh_endprologue
        movl        $1, %ebp
        movl        $2, %esi
        leaq        .LC0(%rip), %r12
        call        __main
        movq        $2, 48(%rsp)
.L2:
        leaq        1(%rsi), %rdi
        cmpq        $200, %rdi
        movq        %rdi, 56(%rsp)
        je          .L4
        movq        %rbp, %rax
        imulq       %rbp, %rax
        imulq       %rax, %rax
        imulq       %rbp, %rax
        movq        %rax, %rdx
        movq        %rsi, %rax
        imulq       %rsi, %rax
        imulq       %rax, %rax
        imulq       %rsi, %rax
        addq        %rdx, %rax
        movq        %rax, 72(%rsp)
.L10:
        leaq        1(%rdi), %rbx
        cmpq        $200, %rbx
        movq        %rbx, 64(%rsp)
        je          .L5
        movq        %rdi, %rax
        movq        72(%rsp), %r13
        imulq       %rdi, %rax
        imulq       %rax, %rax
        imulq       %rdi, %rax
        addq        %rax, %r13
        .p2align 4,,10
.L9:
        movq        %rbx, %r15
        movl        $1, %r14d
        imulq       %rbx, %r15
        imulq       %r15, %r15
        imulq       %rbx, %r15
        addq        %r13, %r15
        .p2align 4,,10
.L6:
        addq        $1, %r14
        cmpq        $200, %r14
        je          .L17
.L8:
        movq        %r14, %rax
        imulq       %r14, %rax
        imulq       %rax, %rax
        imulq       %r14, %rax
        cmpq        %rax, %r15
        jne         .L6
        movq        %r14, 40(%rsp)
        movq        %rdi, %r9
        movq        %rsi, %r8
        movq        %rbp, %rdx
        movq        %rbx, 32(%rsp)
        movq        %r12, %rcx
        addq        $1, %r14
        call        printf
        cmpq        $200, %r14
        jne         .L8
.L17:
        addq        $1, %rbx
        cmpq        $200, %rbx
        jne         .L9
        movq        64(%rsp), %rdi
        jmp         .L10
.L4:
        movq        48(%rsp), %rbp
        leaq        1(%rbp), %rax
        cmpq        $200, %rax
        movq        %rax, 56(%rsp)
        je          .L3
        movq        %rax, 48(%rsp)
.L5:
        movq        56(%rsp), %rsi
        jmp         .L2
.L3:
        xorl        %eax, %eax
        addq        $88, %rsp
        popq        %rbx
        popq        %rsi
        popq        %rdi
        popq        %rbp
        popq        %r12
        popq        %r13
        popq        %r14
        popq        %r15
        ret

最内のループで全部の5乗を計算することはしなくなった模様。 5乗の計算自体も

        movq        -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax
        imulq       -8(%rbp), %rax

が

        movq        %rbp, %rax
        imulq       %rbp, %rax
        imulq       %rax, %rax
        imulq       %rbp, %rax

のように「最適化」されてますな。

これの実行結果はこう。

kbk@toybox4:/mnt/c/Users/kbk/home/junk.test$ time ./a
27, 84, 110, 133, 144

real    0m3.431s
user    0m0.000s
sys     0m0.000s

Python版の方も「高速化」してみようかと思ったけど、 日和って(謎)Rubyで書いてみた。

require 'benchmark'
require 'pp'

result = Benchmark.realtime do
  nums = [*1..200]
  powerof5 = nums.map{|e| e ** 5}.unshift 1
  nums.combination(5).each do |ary|
    if powerof5[ary[0]]+powerof5[ary[1]]+powerof5[ary[2]]+powerof5[ary[3]] == powerof5[ary[4]]
      pp ary
    end
  end
end

puts "処理時間 #{result}s"

n=200で20分ちょっとかかった。 nを150にすると5分くらいで終わるので、組み合わせ爆発すげーな(笑)

>ruby cdc.rb
[27, 84, 110, 133, 144]
処理時間 307.90137129998766s

>ruby cdc.rb
[27, 84, 110, 133, 144]
処理時間 1247.452383099997s

しまった。nをコマンドライン引数で指定できるようにすべきだった。

index

名前に省略形を使うなというのは異論ないのだけど、 「index」は「そのままでは使えない(使えなかった)」 という印象があって、むしろindxとかidxで使いたいと個人的には思う。

例えば

Search Functions (The GNU C Library) 5.9.1 Compatibility String Search Functions

Function: char * index (const char *string, int c)

Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

index is another name for strchr; they are exactly the same. New code should always use strchr since this name is defined in ISO C while index is a BSD invention which never was available on System V derived systems.

これとか。

まあこれに引っかかるようなことはさすがにもうないんじゃないかと思うけど、 わりと色々なところでindexという名前を持った関数やメソッドに遭遇するような気がする (ので、「変数名」には使いづらい)。

five finger salute

ブログ: UNIXの誕生 (ブライアン・カーニハン)

そしてもう一つ、パンチカードは残念ながら大文字しか使えませんでした。つまり、あなたができる5本の指の敬礼は小文字になりますが、 誰もそんなことはしませんでした。だから大文字だったのです。

なんじゃそりゃという訳文だったので原文を見ると

And the one other thing it did… punch cards were unfortunately only upper case. I mean, you five finger salutes that you could do that would get a lowercase, but nobody ever did them. So it was uppercase.

five finger salute という言葉になんかあるんじゃないかと思って調べてみると なんか曲のタイトルにも使われているようで見つけるのに苦労したけど、 やっぱり単なる「5本の指でする敬礼」ではないようだ。

Urban Dictionary: five finger salute

A hand shake done by two people that are really cool opening the palms of their hands and spreading their fingers, then slapping the back part of your hands together.

ふむ。

これを踏まえて件の文を訳すと

≪ prev ファウンデーションの彼方へ
next ≫ Albedo 0.39