ところてん氏のTwitterを見て、この計算が面白そうだしはじめての言語でもなんとかできそうなのでやってみました。
適当に書いたら返ってこないな……（10分経過） https://t.co/ULUyOuTZEO pic.twitter.com/1nxapL1TMq
— ところてん (@tokoroten) 2021年8月5日
python はなんとか書けるものの、 C、C++ はよくわからないので、それに準ずる速度でメモリー周りがもうちょっと簡単そうな rust にしてみました。
ところてん氏のソースとはちょっと違うのですが、最低限の答えを見つけたらいいであろうと、1解を見つけたら終わるようにしてます。
とりあえず、jupyter 上で python は
import time from functools import lru_cache import itertools @lru_cache(maxsize = None) def five(num): return num**5 n=200 before_time=time.time() for li in itertools.combinations_with_replacement(range(1,n+1),5): if sum([five(i) for i in li[:-1]]) == five(li[-1]): print(li) break print(time.time()-before_time) >>(27, 84, 110, 133, 144) >>1330.7497398853302
22分11秒かかってます。
一方、rust*1は、
use std::time::{Instant}; fn x5(x:i64)->i64 { x.pow(5) } fn main() { let start = Instant::now(); 'outer:for _a in 1..200{ for _b in 1..200{ for _c in 1..200{ for _d in 1..200{ for _e in 1..200{ if x5(_a)+x5(_b)+x5(_c)+x5(_d)==x5(_e){ println!("{},{},{},{},{}",_a,_b,_c,_d,_e); let duration = start.elapsed(); println!("{:?}", duration); break 'outer;} } } } } } } >>cargo run --release >>27,84,110,133,144 >>31.9573485s
32秒弱！
力技のほうが速い上に、単純に1/42弱。
これだけ速いとすごく面白くて、rust でもう少し速く計算できないかと思い、a<=b<=c<=d<=e として計算すると、
use std::time::{Instant}; fn x5(x:i64)->i64 { x.pow(5) } fn main() { let start = Instant::now(); 'outer:for _a in 1..200{ for _b in _a..200{ for _c in _b..200{ for _d in _c..200{ for _e in _d..200{ if x5(_a)+x5(_b)+x5(_c)+x5(_d)==x5(_e){ println!("{},{},{},{},{}",_a,_b,_c,_d,_e); let duration = start.elapsed(); println!("{:?}", duration); break 'outer;} } } } } } } >>cargo run --release >>27,84,110,133,144 >>1.1832002s
こんな感じ。
総当たりの上だと if の回数が4_143_265_864、a<=b<=c<=d<=e の下だと139_696_444*2、上割る下で29.7弱なので、計算時間が約1/27になるのは単純に計算量みたいです。
rust 使ってみてコンピュータって速いんだなぁと感心しましたし、上手い人のあれこれ見習ってやってみるのは結構役立つのだなと再確認しました。
ちなみに、a<=b<=c<=d<=eで python で計算すると、
import time before=time.time() for a in range(1,200): for b in range(a,200): for c in range(b,200): for d in range(c,200): for e in range(d,200): if pow(a,5)+pow(b,5)+pow(c,5)+pow(d,5)==pow(e,5): print(a,b,c,d,e) print(time.time()-before) break else: continue break else: continue break else: continue break else: continue break >>27 84 110 133 144 >>2668.9240584373474
44分28秒なので、rust の約1334倍時間がかかっております、はい。
ついでにこれもまた初めての julia で計算すると、
using BenchmarkTools n=200 runtime = @elapsed begin for a=1:n,b=1:n,c=1:n,d=1:n,e=1:n if a^5+b^5+c^5+d^5==e^5 println(a) println(b) println(c) println(d) println(e) break end end end println(runtime) >>27 >>84 >>110 >>133 >>144 >>11925.231573401
