Last active
February 11, 2019 10:25
-
-
Save enshahar/e8afc41ebe8852e219dabfa6e300ddc2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* | |
* 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") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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?