ベジェ曲線とArduino速度の問題、パート2

私たちは通り過ぎます-さらに

以前の投稿で、ベジエ曲線（KB）上のポイントの計算速度を改善する方法を示しました。

1. 計算式の変換-最大3倍の加速。
2. PTからFTへの移行はほとんどありません-加速はほとんどありませんが、3を許可します。
3. 乗算とシフトによる除算の置換操作は、さらに40％の加速です。

言及された投稿の終わりに、私は計算をさらに速く行うことができると言ったが、「少年は言った-少年はした」。



KBのポイントを計算するために取得した式をもう一度思い出させてください

$$

$$P =（A1 *および+ B1）*および+ C（=> 2 * 2 +）$$

速度の次の増加は、問題の特性に関連しています-パラメーター「and」のさまざまな値でKBの値を計算するだけでなく、既知の、さらに固定値（この場合、ケースユニット）、以下で説明する手法を使用できます。 私の時間では、それは計算の差分法と呼ばれていました（記憶が私に正しいなら、少なくともそれは講義で呼ばれたものでした）、インターネット全体があなたの自由です、おそらく（確かに）、別の名前があります。



P = A *および（=> 1 *）の場合を考え、引数u0を持つP0の値を知っていると仮定します。 次に、次の引数u0 + 1を持つ値は、P = A *（u0 + 1）= A * u0 + A = P0 + A（=> 1+）として計算できます。 精度を損なうことなく、乗算演算を加算演算に置き換えることができました。これははるかに高速です。



より複雑な例P = A * and * and（=> 2 *）、類推によりP = A *（and + 1）*（and + 1）= A *（and * and + 2 * and + 1） = A *および*および+ 2 * A *および+ A = P0 + 2 * A *および+ A（=> 2 * 2 +）。 一見、私たちは何も勝ちませんでしたが、事前にA '= 2 * Aを計算すると、（=> 1 * 2 +）が得られ、勝つことができます。 しかし、達成された結果と得られた式A '*で停止せず、既知の手法を適用すると、2つの変数で2つの操作が得られます。P= P + A' + A; A '= A' + A（=> 3+）。 Aの初期値をAでさらに処理できることを考慮すると、通常、2回の乗算ではなく2回の加算のみが残ります。 はい、2つの追加の変数を取得する必要がありましたが、これは古典的な交換です。



正しい初期値を計算するためだけに残りますが、これは反復の開始時に一度だけ行われ、パラメーターの初期値がu = 0の場合、通常は簡単なP = 0、A '= Aです。 数回の反復でメソッドをテストします（これは完全に冗長であり、正しく適用された数学は間違った答えを与えることはできません）が、何が起こっているかをよりよく理解することができます。 だから

反復0：and = 0; P = 0（真）; A '= A; A '' = 2 * A;

反復1：および= 1; P = 0 + A '= 0 + A = A（true）; A '= A' + A '' = A + 2 * A = 3 * A;

反復2：および= 2; P = A + 3 * A = 4 * A（true）; A '= 3 * A + 2 * A = 5 * A;

反復3：および= 3; P = 9 * A（真）; A '= 7 * Aなど。



得られた式と、既知の値を持つ点の近くにある関数の値を計算するためのニュートン法との関係に注意してください。 さらに、関数が2次であり、3番目から始まるすべての導関数がゼロに等しい場合、近似等号を正確な等号に安全に置き換えることができます。 この方法との唯一の違いは、元の定式化で乗算演算を実行するのを避けるために、新しい近傍を構築する点に対して常にポイントを移動することです。



KBの元の式を拡張形式で書き換えます

$$

$$P = A1 *および*および+ B1 *および+ C$$

この方法を使用した計算では、最初の項（および2つの変数）に2 +、2番目の項（および1つの変数）に1+、すべてを加算する（=> 5+）に2+が必要です。 この（間違った）アプローチでさえ、2 * 2 +と比較してゲインが得られることが期待できますが、すべてがはるかに優れています。 明らかに、加算操作は加算的です（ありがとう、キャプテン）。したがって、用語をグループ化し、定数の用語を新しい式に置き換えることができます。これにより、次のアルゴリズムが得られます。



1. P = Cの初期値。 A '= A1 + B1; A '' = 2 * A1;

2.次のステップでP = P + A '; A '= A' + A ''（=> 2+）、これは間違いなくホーナーのスキームよりも高速です。



アルゴリズムをプログラムの形式で実装します（簡単にするためにシフトの必要性を忘れたため、見かけほど簡単ではありませんが、それほど複雑ではありません... 20分間）、計算の複雑さ（=> 2 + 1 >>）を取得し、測定します速度-サイクルあたり140サイクル（速度が3倍に増加）でしたが、これはほぼ理想的な結果です。 （ある意味で）理想的なオプションを得るために私たちがしなければならないことは、式のオペランドの次元に注意を払うことです。 ここで、すべての操作を長い（32ビット）整数で実行しますが、これは場所によっては不要な場合があります。 オペランドの容量を必要最小限に減らすと、20から25パーセントのゲインが得られますが、これにはアセンブラーに切り替えて（Cにはそのような操作に適した手段がない）、元の問題のデータを慎重に分析する必要があります。 これを行うかどうかを判断するのは読者次第ですが、「単純な」アプローチと比較して、1900/140 = 13倍以上の計算をすでに高速化しています。



アルゴリズムの実装に関する最後の注意点は、除算演算を定数乗算によって変更することで除外することです。初期データを生成し、8の定数倍だけシフトするときに考慮します。これは、 。



ただし、1つの問題がまったく予期せずに発生しました-32ビット数で2つの加算演算が明らかに発生し、4 + 4 = 8クロックサイクル、オペランド送信に8 * 3 * 2 = 48クロックサイクル、シフト結果の受信に4クロックサイクル、4計算手順を呼び出して戻るためのクロックサイクルと、サイクルを編成するための4クロックサイクル（別の60クロックサイクルの発生元）は不明です。 以前は、数百クロックサイクルのバックグラウンドに対してこれに気づいていませんでしたが、注意を払うことができます。 過剰な対策が簡単に見つかりました-サイクルには不必要なデバッグ操作があり、すべてを慎重にクリーンアップすると、120の対策しか残っておらず、それぞれの目的は非常に理解可能です（まあ、完全に理解できるようにではなく、まだ）。 次に、空のサイクルの実行時間を確認します-22メジャー、彼らはこの間ずっと何をしているのでしょうか、まあ、98サイクルになる実際の計算時間をクリアします。 取得された作業加速度の評価は変化することに注意してください：1900/140 = 13の代わりに（1900-50）/（140-40）= 19倍になります。サイクルはまだ必要なので、実際には意味がありませんが、さらに上げることができます自尊心。



そして最後の発言-わかりやすいように、大きな鹿のカブトムシを扱い、その（ノミ）の存在が明らかになり、さらに重要になったときにのみ、ノミの検索と除去を開始しました。 パフォーマンスの観点からプログラムを最適化するときは、まさにこのアプローチを強くお勧めします（そして、この推奨事項で私だけではありません）。



結論として、「ある意味で」というメモについて-パラメーターを変更するときに（時間を表す）設計局の次の点の座標を順番に計算することについて話している場合、提案されたアルゴリズム（すべての最適化後）は改善できなくなります。 しかし、タスクを再定式化し、たとえば、画面にデザインビューローを構築するという目標を設定する場合（時間を参照せずに）、非常に有望な方法、キーワード「Brezenheim」がありますが、「これは完全に異なるストーリーです」 （おそらく姉が気にしないならいつか）。