ベジェ曲線、Arduinoの速度、1つの興味深いサイト、または週末の過ごし方について

「誰でもイルカと一緒に灰色のパラドックスを解決できます。そして、あなたはイルカなしでそれをやろうとします。 」

実際、私は週末を少し違った方法で過ごして、ヘリコプターハックに行くことを計画しました（私はヘリコプターのファンだったのではなく、若者が発明したものを見て、そのようにたむろしていました）が、姉は断固として反対しました。 もちろん、私は主張しました（つまり、何度か笑いながら、「まあ、とにかく...それはとにかく楽しいかもしれません」と言った）が、彼女は容赦なく、妻が彼女の側にいたとき、旅行のチャンスはなかった。 まあ、「本当に欲しくなかった」のですが、私は自分で発明したプログラミング分野の面白いパズルを少し座って報告しました。

（必要な注意-前の週末は意図されていた、それは常にそのようなものです-プログラムの作成には数時間かかり、それに関するレポートを作成し、公共交通機関での5日間の旅行は完了しません。）

最近の投稿で、著者は（とりわけ）MKのベジエ曲線（KB）の計算を比較的弱いパラメーターで加速する問題を検討しました。 実際、これらのパラメーターは70年代の平均的なメインフレームのレベルですが、現時点では明らかに不十分であると考えられています。 特定のアクションの結果として、著者は計算をやや高速化することができたので、私の意見では明らかに十分ではないので、最初の近似としてこれをどのように行うべきかを書くことにしました。 スピードで問題を解決するための普遍的なレシピを完全に知っています-より高い頻度でMKを使用するか、別の家族に切り替えるために、私はそれを研究したときから、それが何であるか、単に何もなかったから、言葉からまったく来ませんでした。 現時点では、このアプローチは時代遅れですが、Habrの現代の読者には無関心ではないように思えました。

問題を定式化します—極値AとB、および仮想焦点Cで定義されるベジェ曲線上の点の座標をできるだけ早く計算します。曲線上の点Pの計算式は、

$$

$$（1）P = T * T * B + 2 * T *（1-T）* C +（1-T）*（1-T）* A$$

ここで、Tは0から1まで変化します。 （Wikiでは、この公式はかつて秘密であり、奇妙なことでしたが、何でも可能だと書いています）。 複雑な形式ではなく、X座標とY座標を個別に検索することは明らかです。この式で算術演算の符号の数を数えるだけで、計算の複雑さを推定します-7回の乗算と5回の加算（=> 7 * 5 + ） 優れたコンパイラー（そして今ではすべてのコンパイラーが優れており、明示的に禁止しない場合は完全に最適化されます）は、コストを7 * 3 +に削減する可能性がありますが、事前に（1-T）を計算することで支援する方が良いでしょう 一般的に言えば、優れたコンパイラーは一般に、式のすべての値が定数で表されているのかどうか疑問に思うことがありますが、すべての値が静的に未定義であると仮定します。

パート1、数学

最適化プロセスを開始し、ブラケットを開き、Tで用語をグループ化します（いつかコンパイラーがこれを行うことができるかもしれませんが、これまでのところ、作業のこの部分は自然知能に割り当てられています）

$$

$$（2）P = T * T *（B + A-2 * C）+ T * 2 *（C-A）+ A$$

=> 5 * 5 +。これは、初期値の7 * 5 +よりも明らかに優れていますが、比較的改善された7 * 3 +を引き続き検討する必要があります。

加算演算を1つとして完了するのに時間がかかる場合、乗算を完了するのにかかる時間は、原則として正確に1つ以上になりますが、その程度はMKの実装に依存します（最初に書いた-アーキテクチャについてですが、これは完全に真実ではありません）。 クリスタルにハードウェア乗算器がない場合、乗算実行時間は1の10倍（30+）倍になり、存在する場合は数倍（1-6）になります。 したがって、乗算を加算で置き換えると、ほぼ常に実行時間の増加（そして重要な場合が多い）が得られると安全に想定できます。 さて、固定小数点数から浮動小数点への移行（この事実の証拠は残しておきます）により、加算の実行時間が20倍以上増加します（ここでの調整は非常に影響力があります）が、乗算ではわずかに増加するだけです。 。 したがって、浮動小数点数の場合、加算と乗算の時間は、特に相対的な観点ではほとんど異なりませんが（最大2倍と予測できます）、それらは依然として異なり、乗算を支持しません。そのため、ここにゲインがあります。

前のパラグラフに戻ると、PTの場合、5 * 5 +の格付けは7 * 3 +に比べて大きな利点はないはずですが、引当金は残っています。 パラメーターTが変化し、曲線の他のすべてのパラメーターが固定されている場合（ただし、定数ではないが申し訳ありません）、ベジェ曲線上の点のセットを計算する必要があるという事実に注意してください。その後、式の残りの部分を事前に計算して取得することができます

$$

$$（3）P = T * T * A1 + T * B1 + A$$

=> 3 * 2 +、ここで $$$A1 = A + B-2 * C$そして $$$B1 = 2 *（C-A）$すでに良いですが、ホーナーのスキームを思い出して書くと

$$

$$（4）P = T *（T * A1 + B1）+ A$$

=> 2 * 2 +、「額」の決定と比較すると、2回以上、ほぼ3回勝つ必要があり、これらの最適化は完全に明白です。

理論を実際に確認してみましょう（これは完全に冗長ですが、見積もりには自信がありますが、突然コンパイラーを過小評価しました）。実際のハードウェアでのさまざまなオプションの実行のリアルタイムを測定する必要があります。 まあ、たまたま自宅でさまざまな会社のMK用のさまざまなデバッグボードを持っていることがあります（Luminary MicroやIntel Edissonのデバッグなどの珍しいものを今すぐ購入してみてください）が、Arduinoボードは1つではありません（パイナップルはありません」）。 それは行き止まりのように思えますが、オプションがあります-非常に興味深いサイトtinkercad.comが私たちの助けになります.Arduinoモジュールを使用してブレッドボード上に回路を構築し、スケッチを書いてすぐに実行できます。 同時に、ブレークポイントの設定、プログラムのステップ実行、および（実際のArduinoにとっては前例のない）ブレークダウン時の変数の値を表示することもできます。

このサイトに目を向け、測定を開始します。 まず、操作の実行時間に関する想定を確認し、周囲の状況をクリアした後、整数について次のデータを取得します。

8 + 8 => 8-1ビート、16 + 16 => 16-2、
8 * 8 => 16-2、16 * 16 => 16-14（予想外であることが判明した唯一のものは、4 * 2 + 4 * 2 = 16が得られると思い、興味深い最適化があります）、
8/8 => 8-230、16 / 16 => 16-230。

最後の2桁に注意してください。本当にすぐにカウントしたい場合、除算操作が禁止されていることは明らかです。 （最終的に）24ビットの仮数を持つPTの数で操作を実行するのにかかる時間を測定します
a + b-126（オペランドに大きく依存）、a * b-140、a / b-482。
得られたデータは、理論上の仮定とよく相関しています。このMKに搭載されているハードウェア実装は、乗算ではなく、除算ではなく、演算であるPTであることがわかります。

今、私たちは完全な計算の時間を測定し始めます。 値A = 140、B = 120、C = 70を設定し、設計局に170の均等に分布したポイントを作成します。 なぜこれらの値と正確に一致するのか-パフォーマンスを評価するときに指定された投稿でそれらが与えられました。 以下は、アルゴリズムと対応するテスト実行時間です。

式（1）=> 20msまたはサンプルあたり1,900クロックサイクル
式（1）=> 18msまたはサンプルあたり1660クロックサイクル（個別に1-Tを考慮）
式（2）=> 16msまたはサンプルあたり1540クロックサイクル
式（3）=> 10msまたはサンプルあたり923クロックサイクル
式（4）=> 8msまたはカウントあたり762メジャー

結果の実行時間の短縮（20ミリ秒から8ミリ秒）は予想とよく相関しており、計算を2倍以上高速化できたことがわかります。 完全に明白な考慮事項と数学に加えて、高校のコースを超えていないことに注意してください、私たちは必要ありませんでした。

次に、結果が十分でない場合の対処方法について説明します。計算式からすべてを絞り出しています。 彼らはここで（別の投稿へのコメントで）私に書いて、一般にどんな問題もFTでの計算に減らすことができ、仮定の明らかな論争にもかかわらず（これをNavier-Stokes方程式の数値解法で試してみてください）、この特定の場合、この勧告は適用可能ですしかし、いつものように、微妙な違いがあります。

パート2、コンピューティング

アルゴリズムの変更が完了すると、データ構造のみが残り、固定小数点数の土壌に入ります。 ここでは、PTについて考えていなかった多くの落とし穴を見つけます-範囲と精度（一般的に、PTについてはこれらの問題について考える必要がありますが、ここではすべてが簡単で、多くのことが行われています）。 FTの必要な表現を決定するために問題の小さな研究を行う必要があります（前述のポスト9.7で選択され、結果から判断すると明らかに不十分です）が、私はわずかに異なる道を取ることを提案します。 ちなみに、間隔で170ステップではなく、128（このステップを禁止する理由はないと思います）を採用した場合、この考えは完全に適合します。 KBを定義する定数が整数で与えられるという事実を考慮し、唯一のパラメーターTがフォームの一部および/で表されることができ、画面上のレンダリングに結果を使用する場合、つまり整数座標に変換する場合、整数ですべてを行うだけで、処理がはるかに高速になります。

最後の式のみを使用し、新しい表記で書き直します

$$

$$（5）P = u / U *（u / U * A1 + B1）+ A$$

（=> 2 * 2 + 2 /）、ここでA1とB1はPTと同じ方法で計算されます。 明らかに、すべての数値は整数であり、対応する操作ははるかに高速に実行する必要があります。 整数除算（2/3 = 1！= 1.5）の操作中に精度を失わず、最後の瞬間に除算を実行するために、式をわずかに形式に変換します

$$

$$（6）P =（（および* A1 + B1 * And）/ And * And + A * And）/ And$$

（=> 4 * 2 + 2 /）。 すべてのFT番号。したがって、このアルゴリズムを実装して...ここにいるのはおばあさんで、ユーリエフの日... 1869サイクルですが、これはFTの場合よりもはるかに悪いです。

デブリーフィングを開始すると、変数のタイプを変更するだけでは不十分であることがわかりました。 まず、8または16ではなく32ビットの数値を使用する必要があります。そうしないと、オーバーフローが発生しますが、PTよりも高速ですが、アルゴリズムの欠陥を補うのに十分ではない長い数値が発生します。再び各メジャーで定数が計算されました-予備計算でそれらを削除しますB2 = B1 * I、A2 = A * I * I それから

$$

$$（7）P =（（および* A1 + B2）*および+ A2）/および/および$$

（=> 2 * 2 + 2 /）1684の結果は前のものよりも優れていますが、それでもこの点には従いませんでした。

もう1つの定数And2 = And *の計算を除外すると、

$$

$$（8）P =（（および* A1 + B2）*および+ A2）/ II$$

（=> 2 * 2 + 1 /）、実行サイクルは956サイクルです-しかし、これは興味深いですが、1つの操作を除いて生産性が大幅に向上しました。

それは私たちを遅くするものです-分割、それは非常に時間がかかる操作であるためですが、私たちはそれに対処するための興味深いトリックを持っています。 式1 /を計算するには、要素変換1 /= 1 /*（/）= 1 *（/）/を実行します。 2の次数をHとして選択した場合、Hによる除算をシフトに置き換えることができ、指数が8の倍数である場合、偶数のシフトは必要ありません。 そして、N / Aの値は正直に計算する必要がありますが、計算サイクルでは乗算のみが残ります。

完全に正しくない変換を行い、N / Aを丸められた値Kに置き換えて、整数のみの演算に移行することに注意してください。 不正確さは、精度の低下にあり、このアプローチの本件への適用性を証明するために追加の調査を実施する必要があります。 H / Iを（K * I + d）/ I = K +（d / I）の形式で記述します。ここで、qはI未満です。H/ IからKへの絶対誤差はd / Iになり、相対誤差はd / IになりますI /（K + d / I）> = d / I /（K + 1）〜d / I / K、ただし、K >> 1（これはシフトではない）。 絶対計算誤差はA * d / I / K> = A * 1 / N / Iに等しいため、Hの値はできるだけ大きく選択する必要があります。 エラーを1以上にしたくない場合は、条件A / K <= 1、K> = Aに耐える必要があり、K * I> = A * Iに変換します。つまり、H> = A * Iを意味し、精度が低下します。 この場合、A <= 256およびI <= 256の場合、H> = 2 ** 16になりますが、これはまったく問題ありません。 明らかに、上記の式では、元の数値のモジュールを使用する必要があります。

将来に注意してください。切り捨てるのではなく、最も近い整数に向かっていくと、要件はいくらか減り、ニュアンスはありますが、Hは半分になります。

いずれの場合でも、必要な精度を確保し、次のアルゴリズムを取得できます。H = 2 ** 16; K = [N / A]（I <256）; 0 <=および<= AND;

$$

$$（9）P =（（（（および* A1 + B2）*および+ A2）* K）>> 16）* K）>> 16$$

（=> 4 * 2 + 2 >> 16）ここで、すべての操作は長整数で実行されます。 このアルゴリズムを実装すると、583クロックサイクルが得られますが、これはすでに理想に近づいていますが、まだ理想的ではありません。

次に、特定のMKの小さな設定があります-グローバル変数の操作はより高速です。 ローカルのものよりも、ローカルのものを登録するとさらに高速になり、時間は506クロックサイクルに短縮されます。

さらに、シフト前の最後の乗算は16ビット数で実行できることに注意してください。これにより、504が得られます。

合計で、1900/504の「額」の実装と比較して計算を3倍以上高速化しました。正確に言葉を失うことはありませんでした。 これは、私が時間の最適化と呼ぶ結果であり、元の投稿で受け取った20％ではありません。

さらに良い指標を達成することは可能ですか？-可能ですが、これは次の投稿のトピックです。