まずは簡単なYul言語の例から見ていきます。

https://docs.soliditylang.org/en/latest/yul.html#simple-example

実装

上記のコードは、baseで受け取った値をexponentで受け取った値乗するpower関数を定義しています。
この関数は、指数を使ったべき乗計算を行う再帰的なアルゴリズムを使用しており、効率的な「繰り返し二乗法」を実装しています。

関数定義

• function power(base, exponent) -> result:
  • 関数名
    • power。
  • 関数の引数
    • (base, exponent)
    • ここではbaseが底となる数値、exponentが指数です。
  • 関数の出力
    • -> result
    • 計算されたべき乗の結果がresultに格納されます。

制御構造と計算

• switch exponent
  • exponent（指数）の値に基づいて異なるケースを処理します。
  • case 0 { result := 1 }
    • 指数が0の場合、どんな数を0乗しても結果は1になるため、resultを1に設定します。
  • case 1 { result := base }
    • 指数が1の場合、結果は底と同じになるので、resultをbaseに設定します。
  • default
    • 指数が0や1以外の場合、再帰的にべき乗を計算します。
  • result := power(mul(base, base), div(exponent, 2))
    • baseの2乗と、指数を2で割った値（整数除算）を再帰的にpower関数に渡します。
    • これにより、計算を効率的に行うことができます。
• switch mod(exponent, 2)
  • 指数を2で割った余りに基づいて、さらに処理を行います。
  • case 1 { result := mul(base, result) }
    • 余りが1の場合（つまり、指数が奇数の場合）、現在のresultにbaseを掛けます。
    • これにより、べき乗の計算が正しく行われます。

効率的な計算のためのアプローチ

このコードは「繰り返し二乗法」というアプローチを使用しており、大きな指数に対しても効率的にべき乗を計算できるようにしています。
基本的には、指数を半分にして再帰的に問題を小さくし（それにより計算回数を減らす）、指数が奇数の場合は余分にbaseを掛けることで正しい結果を取得しています。

実装（シンプル）

上記のコードは、先のほどの実装コードでfor文を用いたシンプルなアプローチを採用しています。

関数定義

• function power(base, exponent) -> result
  • これはpowerという名前の関数を定義しており、base（底）とexponent（指数）を引数として受け取り、計算されたべき乗の結果をresultに返します。

初期化

• result := 1
  最初にresultを1に設定します。
  これは、べき乗の計算で使用される累積積の初期値です。

ループ構造

• for { let i := 0 } lt(i, exponent) { i := add(i, 1) } { ... }
  • このforループは、iが0から始まりexponent未満の間、iを1ずつ増やしながらループします。
• 初期化
  • { let i := 0 }はループの初めに一度だけ実行され、ループカウンタiを0に設定します。
• 条件
  • lt(i, exponent)はループの継続条件で、iがexponentより小さい間はループを続けることを意味します（ltは"less than"の略）。
• 後処理
  • { i := add(i, 1) }はループの各繰り返し後に実行され、iを1増やします。

べき乗の計算

• result := mul(result, base)
  • ループの本体で、resultにbaseを掛けたものをresultに再代入しています。
  • これにより、exponentの回数だけbaseを掛けることで、べき乗の計算が行われます。

効率性

このコードは非常に直感的で理解しやすいべき乗の計算方法を採用していますが、大きな指数に対しては効率が良くないです。
各繰り返しで1回の乗算を行い、指数の大きさに比例する回数の乗算が必要になります。
より大きな指数で効率的に計算を行うには、繰り返し二乗法などのアルゴリズムが推奨されます。