ロシア農民の掛け算をKotlinでやってみた

「[ロシア農民の掛け算をJavaScriptでやってみた](https://qiita.com/stonee/items/345a833c7d4a175d6a8f)」を Kotlin でやってみた。

## シンプル版

```Kotlin
/**
 * 「ロシア農民の掛け算」を行い結果のリストを返す。
 * 結果のリストの全要素の和が、引数 a と b の積となる。
 *
 * @param a 掛けられる数。
 * @param b 掛ける数。
 * @return 結果のリスト。全要素の和が、引数 a と b の積と一致する。
 */
fun times(a: Int, b: Int): List<Int> =
    if (b == 1) {
        listOf(a)
    } else {
        when (b % 2) {
            0 -> times(a shl 1, b shr 1)
            1 -> listOf(a) + times(a, b - 1)
            else -> throw AssertionError()
        }
    }
```

### 使用例

```Kotlin
fun main() {
    val a = 34227
    val b = 36070
    val result = times(a, b)

    println("  $a * $b")
    println("= ${result.joinToString(" + ")}")
    println("= ${result.sum()}")
}
```

出力結果

```plaintext
  34227 * 36070
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 1121550336
= 1234567890
```
</div>
</details>


## リスト再利用・末尾再帰版

```Kotlin
/**
 * 「ロシア農民の掛け算」を行い結果のリストを返す。
 * 結果のリストの全要素の和が、引数 a と b の積となる。
 *
 * @param a 掛けられる数。
 * @param b 掛ける数。
 * @return 結果のリスト。全要素の和が、引数 a と b の積と一致する。
 */
fun times(a: Int, b: Int): List<Int> =
    mutableListOf<Int>().also {
        times(it, a, b)
    }

/**
 * 再帰的に「ロシア農民の掛け算」を行う。
 *
 * 計算過程は n0 + n1 + ... + ni + a * b というような形になる。
 *
 * @param list
 *  入力：計算過程の n0, n1, ..., ni を要素に持つリスト。
 *      再帰的に呼び出していない、初回の呼び出しでは空。
 *  出力：結果のリスト。全要素の和が、引数 a と b の積と一致する。
 * @param a 計算過程の a。
 * @param b 計算過程の b。
 */
private tailrec fun times(list: MutableList<Int>, a: Int, b: Int) {
    if (b == 1) {
        list += a
        return
    }

    when (b % 2) {
        0 -> times(list, a shl 1, b shr 1)
        1 -> {
            list += a
            times(list, a, b - 1)
        }
        else -> throw AssertionError()
    }
}
```

### 使用例

```Kotlin
fun main() {
    val a = 34227
    val b = 36070
    val result = times(a, b)

    println("  $a * $b")
    println("= ${result.joinToString(" + ")}")
    println("= ${result.sum()}")
}
```

出力結果

```plaintext
  34227 * 36070
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 1121550336
= 1234567890
```

## 計算過程出力・末尾再帰版

```Kotlin
/**
 * 「ロシア農民の掛け算」を行い結果を返す。
 *
 * 計算過程は n0 + n1 + ... + ni + a * b というような形になる。
 *
 * @param a 掛けられる数。
 * @param b 掛ける数。
 * @param action 計算過程を監視するためのコールバック関数。
 *  引数は次のとおり：
 *  - index : 計算過程のインデックス。0 始まり。
 *      0 のときは計算前の状態であり、引数 list は空、
 *      a, b は関数 [times] に与えられた引数 a, b と一致する。
 *  - list : 計算過程の n0, n1, ..., ni を要素に持つリスト。
 *  - a : 計算過程の a。
 *  - b : 計算過程の b。
 * @return 積。
 */
fun times(
    a: Int,
    b: Int,
    action: (index: Int, list: List<Int>, a: Int, b: Int) -> Unit =
        { _, _, _, _ -> /* 何もしない */ }
): Int = times(0, emptyList(), a, b, action)

/**
 * 再帰的に「ロシア農民の掛け算」を行い結果を返す。
 *
 * 計算過程は n0 + n1 + ... + ni + a * b というような形になる。
 *
 * @param index 再帰呼び出しの深さ。0 始まり。
 *  再帰的に呼び出していない、初回の呼び出しでは 0。
 * @param list 計算過程の n0, n1, ..., ni を要素に持つリスト。
 *  再帰的に呼び出していない、初回の呼び出しでは空。
 * @param a 計算過程の a。
 * @param b 計算過程の b。
 * @param action 計算過程を監視するためのコールバック関数。
 *  関数 [times] に渡された引数がそのまま渡される。
 * @return 積。
 */
private tailrec fun times(
    index: Int,
    list: List<Int>,
    a: Int,
    b: Int,
    action: (index: Int, list: List<Int>, a: Int, b: Int) -> Unit
): Int {
    action(index, list, a, b)

    if (b == 1) {
        return (list + a).sum()
    }

    return when (b % 2) {
        0 -> times(index + 1, list, a shl 1, b shr 1, action)
        1 -> times(index + 1, list + a, a, b - 1, action)
        else -> throw AssertionError()
    }
}
```

### 使用例

```Kotlin
fun main() {
    times(34227, 36070) { index, list, a, b ->
        // 計算過程を出力する。

        // 行頭の "= " を出力する。
        // ただし index が 0 の場合は代わりに "  " を出力する。
        print(
            if (index == 0) "  "
            else "= "
        )
        // 足し算の部分を出力する。
        print(
            list.takeUnless { it.isEmpty() }
                ?.joinToString(" + ", postfix = " + ")
                ?: ""
        )
        // 掛け算の部分を出力する。
        println("$a * $b")
    }.also {
        // 計算結果を出力する。
        println("= $it")
    }
}
```

<details>
<summary>出力結果</summary>
<div>

```plaintext
  34227 * 36070
= 68454 * 18035
= 68454 + 68454 * 18034
= 68454 + 136908 * 9017
= 68454 + 136908 + 136908 * 9016
= 68454 + 136908 + 273816 * 4508
= 68454 + 136908 + 547632 * 2254
= 68454 + 136908 + 1095264 * 1127
= 68454 + 136908 + 1095264 + 1095264 * 1126
= 68454 + 136908 + 1095264 + 2190528 * 563
= 68454 + 136908 + 1095264 + 2190528 + 2190528 * 562
= 68454 + 136908 + 1095264 + 2190528 + 4381056 * 281
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 4381056 * 280
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 8762112 * 140
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 17524224 * 70
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 * 35
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 35048448 * 34
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 * 17
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 70096896 * 16
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 140193792 * 8
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 280387584 * 4
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 560775168 * 2
= 68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 1121550336 * 1
= 1234567890
```
</div>
</details>