Add an iterative rational implementation for exact results

[taywrobel]

Adds an implementation in golang using rational number types to get exact results, and an iterative algorithm for performance improvement compared to recursive approaches.

Outputs to CSV for easy data integration with tooling.

[taywrobel]

Performance on this is decent, tho the numerators and denominators get big fast, which starts to be a bottle neck in performance to maintain exactness. I can calculate all expected values for n up to 1,000 in ~12.5s on my MacBook.

There's a cool way to structure this concurrently that I may implement, which should optimize the runtime a bit, tho it'll be the same time complexity.

[AustinTSchaffer]

Hey, Matt's never going to merge any of these PRs, but figured I'd review some of them anyway.

I did some math that I shared over on Issue #1. If performance is your goal, you can get much better performance if you use the equation at the bottom of the image that I posted. Even with Python, I'm seeing ~0.05 seconds to generate all of the expected values between 0 and 1000, with no recursion, no concurrency, and no caching.

time python3 - <<EOF
def expected_hops(pads):
    if pads <= 0: return 0
    return sum((1/n for n in range(1, pads+1)))

x = [expected_hops(i) for i in range(1001)]

print('Expected hops for 1:', x[1])
print('Expected hops for 10:', x[10])       
print('Expected hops for 100:', x[100])
print('Expected hops for 1000:', x[1000])
EOF

# Expected hops for 1: 1.0
# Expected hops for 10: 2.9289682539682538
# Expected hops for 100: 5.187377517639621
# Expected hops for 1000: 7.485470860550343
# 
# real  0m0.042s
# user  0m0.034s
# sys   0m0.009s

[AustinTSchaffer]

Realizing that precision is also your goal, I did the same thing using Python's decimal library, which took about a third of a second to generate all expected values for starting values between 0 and 1000.

Again, this is Python, which is nowhere near Go in terms of performance.

time python3 - <<EOF
import decimal
def expected_hops(pads):
    if pads <= 0: return 0
    return sum((decimal.Decimal(1) / decimal.Decimal(n) for n in range(1, pads+1)))

x = [expected_hops(i) for i in range(1001)]
print(x[1000])                                   
EOF

# 7.485470860550344912656518202
# 
# real  0m0.314s
# user  0m0.306s
# sys   0m0.008s

[taywrobel]

Thanks for the suggestion! Went ahead and updated the algorithm, and it's much quicker, 10ms or so for frog(1000)

time ./frog 1000
Frog(1000) = 53362913282294785045591045624042980409652472280384260097101349248456268889497101757506097901985035691409088731550468098378442172117885009464302344326566022502100278425632852081405544941210442510142672770294774712708917963967779610453224692426866468888281582071984897105110796873249319155529397017508931564519976085734473014183284011724412280649074307703736683170055800293659235088589360235285852808160759574737836655413175508131522517/7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000 == 7.4854708606
        0.01 real         0.01 user         0.00 sys