高速化をするにはどうしたらいいですか？

Question

macOS Mojave , Xcode 10 , Swift 4 を使用しています。
まだ 初心者ですが、方程式を解くプログラムに困っています。

axx + b*x + c = 123456789

a*(x+1)(x+1) + b(x+1) + c = 345678912

a*(x+2)(x+2) + b(x+2) + c = 1023456789

上記、三元二次方程式のa,b,c,xを求めるプログラムを考えた場合
私は、総当たりの下記のプログラム実行しました。
略
For a in 0 ... 100000{
For b in 0 ... 100000{
For c in 0... 100000{
For x in 1 ... 1000{
y1 = axx + bx + c
y2 = a(x+1)(x+1) + b(x+1) + c
y3 = a*(x+2)(x+2) + b(x+2) + c
if y1 == 123456789 && y2 == 345678912 && y3 == 1023456789{
print(a,b,c,x)

略

で実行すると計算量が多く一日で、aの数値が100で終了しません。

行列式、並列化など本を読んでいますが高速化ができません。

何か良い方法があれば御教授下さい。
お願いします。

Comments

[cateye]

a,b,cが共に整数で、整数解が出る保証は有りますか？

[fuzzball]

「アルゴリズム」タグ付けたほうがいいと思います。

Answer 1

総当たりの下記のプログラム実行しました。

総当たりをかける前に、できるだけ範囲を減らしておきましょう。

2番目の式から1番目の式を引けば、(2x+1)a+bの値が出ます。同様に、3番目の式から1番目の式を引くことで、(4x+4)a+2bの値が決まります。この2つの式から、aの値は決まります。

Comments

[Heiretu_ka]

ありがとうございました。
連立方程式の解き方をもう一度勉強します。

Answer 2

こんにちは。

基本はmaisumakunさんも言われている通り、プログラムを設計する段階でなるべく計算量を減らすように設計するべきです。

それを行ってもなお、計算時間を削減したい場合、まずはリリース・ビルドすることです。
たまにデバッグ・ビルドで遅いと嘆いてしまうことがあります。かなり速度が違います。
また、コンパイル・オプションを見直してより最適化レベルを高速化の方に設定すると多少効果が出る場合もあるそうです。（私は実感したことはないですが。）

次に最適化を手で行うことも考えられますが、昨今のコンパイラの最適化性能は高いですから、最適化性能の高いコンパイラを導入した方が良いかもしれません。swiftの性能は把握していませんが、もしかするとC言語の方が最適化性能は高いかもです。wiftではなくC言語で記述するのも手でしょう。

それでダメなら、高速な数値計算ライブラリを使うのが良いと思います。
具体的にどれが良いか把握していませんが、大抵のケースで苦労して自分で高速化するより、より高速化できることを期待できます。

Comments

[Heiretu_ka]

ありがとうございました。
並列化のオプションでCPU使用率３５０%にすることができました。