FromMathToGenerics_Chapter1.kts

/**
 *
 * https://playcointeam.atlassian.net/wiki/spaces/PAYM/pages/3571732/PLC+Specification
 *
 * @author Hyunsok Oh
 */

var n_addition = 0
var n_shift = 0
var n_oddCompare = 0
var n_oneCompare = 0
var n_ftCall = 0

fun calcAndReport(a:Long, b:Long, f: (Long,Long)->Long, desc:String) {
    fun init() { n_addition = 0; n_shift = 0; n_oddCompare = 0; n_oneCompare = 0; n_ftCall = 0 }
    fun report(v:Long) {
        println("${desc}: ${a} * ${b} = ${v}")
        println("${desc}: ${n_addition} additions + ${n_shift} shifts")
        println("${desc}: ${n_oddCompare} odd check + ${n_oneCompare} one check + ${n_ftCall} ft call")
    }

    init()
    report(f(a,b))
}

fun odd(n:Long):Boolean { n_oddCompare++; return n % 2L == 1L }

fun one(n:Long):Boolean { n_oneCompare++; return n == 1L }

fun half(n:Long):Long { n_shift++; return n shr 1 }

fun plusWithMeter(a:Long, b:Long):Long {
    n_addition++
    return a+b
}

fun multiply1(n:Long, a:Long):Long {
    n_ftCall++
    return (
        if (one(n))
            a
        else {
            val result = multiply1(half(n), plusWithMeter(a, a))
            if (odd(n))
                plusWithMeter(result, a)
            else
                result
        }
    )
}

fun multiply_by_15(a:Long):Long {
    val b = (a + a) + a
    val c = b + b
    return (c + c) + b
}

fun mult_acc0(r:Long, n:Long, a:Long):Long {
    n_ftCall++
    return (
        if (one(n))
            plusWithMeter(r, a)
        else if (odd(n))
            mult_acc0(plusWithMeter(r, a), half(n), plusWithMeter(a, a))
        else
            mult_acc0(r, half(n), a)
    )
}

fun mult_acc1(r:Long, n:Long, a:Long):Long {
    n_ftCall++
    return (
        if (one(n))
            plusWithMeter(r, a)
        else
            mult_acc1(
                if (odd(n)) plusWithMeter(r, a) else r,
                half(n),
                plusWithMeter(a, a)
            )
    )
}

fun mult_acc2(r:Long, n:Long, a:Long):Long {
    n_ftCall++
    return (
        if (odd(n)) {
            val r2 = plusWithMeter(r, a)
            if (one(n))
                r2
            else
                mult_acc0(r2, half(n), plusWithMeter(a, a))
        } else
            mult_acc0(r, half(n), a)
    )
}

fun mult_acc3(r:Long, n:Long, a:Long):Long {
    n_ftCall++
    var r2 = r
    var n2 = n
    var a2 = a
    fun mult_acc3_1(): Long {
        n_ftCall++
        if(odd(n2)) {
            r2 = plusWithMeter(r2,a2)
            if(one(n2)) return r2
        }
        n2 = half(n2)
        a2 = plusWithMeter(a2,a2)
        return mult_acc3_1()
    }
    return mult_acc3_1()
}

fun mult_acc4(r:Long, n:Long, a:Long):Long {
    n_ftCall++
    var r2 = r
    var n2 = n
    var a2 = a
    while (true) {
        if(odd(n2)) {
            r2 = plusWithMeter(r2,a2)
            if(one(n2)) return r2
        }
        n2 = half(n2)
        a2 = plusWithMeter(a2,a2)
    }
}

fun multiply2(n:Long, a:Long):Long {
    n_ftCall++
    return (
        if (one(n))
            a
        else {
            mult_acc4(a, n - 1, a)
        }
    )
}

fun multiply3(n:Long, a:Long):Long  {
    n_ftCall++

    var a2 = a
    var n2 = n

    while(!odd(n2)) {
        a2 = plusWithMeter(a2, a2)
        n2 = half(n2)
    }

    return(if (one(n2))
        a2
    else
        mult_acc4(a2, n2-1, a2))
}

fun multiply4(n:Long, a:Long):Long  {
    n_ftCall++

    var a2 = a
    var n2 = n

    while(!odd(n2)) {
        a2 = plusWithMeter(a2, a2)
        n2 = half(n2)
    }

    return(
        if (one(n2))
            a2
        else
            // here, n2 must be odd and n2 >= 3
            // so do one iteration of mult_acc4 in here
            mult_acc4(a2, half(n2-1), plusWithMeter(a2, a2))
    )
}

println("15*59 = ${multiply_by_15(59)}")

calcAndReport(41, 59, ::multiply1, "multiply1")
calcAndReport(41, 59, ::multiply2, "multiply2")
calcAndReport(41, 59, ::multiply3, "multiply3")
calcAndReport(41, 59, ::multiply4, "multiply4")

calcAndReport(4132, 597434, ::multiply1, "multiply1")
calcAndReport(4132, 597434, ::multiply2, "multiply2")
calcAndReport(4132, 597434, ::multiply3, "multiply3")
calcAndReport(4132, 597434, ::multiply4, "multiply4")

multiply1: 41 * 59 = 2419
multiply1: 7 additions + 5 shifts
multiply1: 5 odd check + 6 one check + 6 ft call
multiply2: 41 * 59 = 2419
multiply2: 7 additions + 5 shifts
multiply2: 6 odd check + 3 one check + 2 ft call
multiply3: 41 * 59 = 2419
multiply3: 7 additions + 5 shifts
multiply3: 7 odd check + 3 one check + 2 ft call
multiply4: 41 * 59 = 2419
multiply4: 7 additions + 5 shifts
multiply4: 6 odd check + 3 one check + 2 ft call
multiply1: 4132 * 597434 = 2468597288
multiply1: 14 additions + 12 shifts
multiply1: 12 odd check + 13 one check + 13 ft call
multiply2: 4132 * 597434 = 2468597288
multiply2: 16 additions + 12 shifts
multiply2: 13 odd check + 5 one check + 2 ft call
multiply3: 4132 * 597434 = 2468597288
multiply3: 14 additions + 12 shifts
multiply3: 14 odd check + 3 one check + 2 ft call
multiply4: 4132 * 597434 = 2468597288
multiply4: 14 additions + 12 shifts
multiply4: 13 odd check + 3 one check + 2 ft call

0.0
Premature optimisation is the root of all evil?