ときどきの雑記帖 RE* (新南口)
90億の神の御名
イ
日本一名前の長い植物・短い植物 | 蒲田で接待にも使える鉄板焼き店なら鉄板焼 野澤
CDC6600
【オイラー予想】
— 数学を愛する会 (@mathlava) August 5, 2021
オイラーはフェルマーの最終定理を拡張して『x⁵+y⁵+z⁵+w⁵=v⁵を満たす自然末の組み合わせは存在しない』と予想しました。200年後、たった2行の論文がそれを覆しました。 pic.twitter.com/u9PQ2aOdbE
ちなみに続きがありますが、二文で終わる論文として有名です。 pic.twitter.com/igiI2cuSUr
— 数学を愛する会 (@mathlava) August 5, 2021
実際にコンピューターに計算させる前に色々あったんじゃないかという気がするけど それはさておき問題の式は
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って(聞き覚えのある名前ではあったけど)どんな機械だっけと調べると
- CDC 6600 - Wikipedia
- コンピュータアーキテクチャの話(380) スパコンの天才が作ったIBM Stretchの3倍の性能を持つ「CDC 6600」 | TECH+
- コンピュータアーキテクチャの話(381) 約40万のシリコントランジスタを使ったCDC 6600スパコン | TECH+
- コンピュータアーキテクチャの話(382) RISCの元祖とも言われる「CDC6600」 | TECH+
アーキテクチャ的には、CDC6600はCPUと周辺装置を制御する10台のPPUからなるヘテロマルチプロセサのシステムである。 CPUは1語60bitで、レジスタは整数と浮動小数点数で共用されていた。CDCは1文字を6bitで表わしており、 PPUは2文字を格納できる12bit語のプロセサであった。
浮動小数点数はさておき、60bitなら144^5も問題なく格納できるということですか。
適当に書いたら返ってこないな……(10分経過) https://t.co/ULUyOuTZEO pic.twitter.com/1nxapL1TMq
— ところてん (@tokoroten) August 5, 2021
C# で適当に回したら出てきた
— ところてん (@tokoroten) August 5, 2021
(intで書いてたら、32bit超えてバグった) pic.twitter.com/8K5utQeSy1
↑の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
変数名の付け方。好みもあるとは思うけど、僕は
— Piro🎉"シス管系女子"シリーズ累計5万部突破!!🎉 (@piro_or) August 4, 2021
index→idx
format→fmt
みたいな省略は、原則としてしない方がよりリーダブルだと思ってる。理由は主に2つ。
名前に省略形を使うなというのは異論ないのだけど、 「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
そしてもう一つ、パンチカードは残念ながら大文字しか使えませんでした。つまり、あなたができる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.
ふむ。
これを踏まえて件の文を訳すと