Instantly share code, notes, and snippets.

@qwtel /gist:6946573
Last active Dec 25, 2015

Embed
What would you like to do?
case class LoopState(i: Int = 0, acc: Double = 0.0, isCompleted: Boolean = false)
lazy val twoPowers = for (i <- 0 until 50) yield Math.pow(2.0, i)
val Epsilon: Double = 1e-17
val TaskSize = 2500000
def modPow16(exp: Double, m: Double): Double = {
if (exp < 1) Math.pow(16.0, exp)
else {
@tailrec
def step(i: Int, pow2: Double, pow1: Double, acc: Double): Double = {
i match {
case 0 => acc
case _ if pow1 >= pow2 => step(i, pow2, pow1 - pow2, (16.0 * acc) % m)
case _ if pow2 >= 2 => step(i - 1, pow2 / 2, pow1, (acc * acc) % m)
case _ => step(i - 1, pow2 / 2, pow1, acc)
}
}
val i = twoPowers indexWhere (_ > exp)
step(i, twoPowers(i - 1), exp, 1.0)
}
}
def task(m: Int, digitPos: Int, i: Int, acc: Double): LoopState = {
@tailrec
def loop(i: Int, acc: Double): LoopState = {
digitPos - i match {
case -100 => LoopState(i, acc, isCompleted = true) // task complete
case pow => {
val denom = 8 * i + m
val term = modPow16(pow, denom) / denom
if (i >= digitPos && term < Epsilon) LoopState(i, acc, isCompleted = true) // task complete
else {
if (i % TaskSize == 0) LoopState(i + 1, (acc + term) % 1.0, isCompleted = false) // reached limit
else loop(i + 1, (acc + term) % 1.0) // continue
}
}
}
}
loop(i, acc)
}
var TASK_SIZE = 2500000;
var EPSILON = 1e-17;
var twoPowersCache = {};
function twoPowers(i) {
if (!twoPowersCache.hasOwnProperty(i)) twoPowersCache[i] = Math.pow(2.0, i);
return twoPowersCache[i];
}
function modPow16(exp, m) {
var i = 0;
var pow2 = 0;
while(pow2 < exp) {
pow2 = twoPowers(i);
i++;
}
var pow1 = exp;
var acc = 1.0;
if (exp < 1) return Math.pow(16.0, exp);
else {
while (true) {
if (i == 0) return acc;
else if (pow1 >= pow2) {
pow1 = pow1 - pow2;
acc = (16.0 * acc) % m;
} else if (pow2 >= 2) {
i -= 1;
pow2 = pow2 / 2;
acc = (acc * acc) % m;
} else {
i -= 1;
pow2 = pow2 / 2;
}
}
}
}
function task(m, digitPos, i, acc) {
while (true) {
if (digitPos - i == -100) return [i, acc, true]; // task complete
else {
var pow = digitPos - i;
var denom = 8 * i + m;
var term = modPow16(pow, denom) / denom;
if (i >= digitPos && term < EPSILON) return [i, acc, true]; // task complete
else {
if (i % TASK_SIZE == 0) return [i + 1, (acc + term) % 1.0, false]; // reached limit
else {
i++;
acc = (acc + term) % 1.0;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment