Calculating of integer logarithm base 2 is pretty easy in near any computer language - you just find the largest '1' in binary representation, and rest becomes zero.
Is is possible to do the same fast trick for other bases, for example 3, - calculate logarithm of base 3 or get the nearest integer from below what is correct 3n?
Yes, using the same method as Find integer log base 10 of an integer we can achieve the same thing. We just replace powers of 10 with powers of 3, log102 with log32, and a multiplication of 1/log32 ≈ ³²³⁄₅₁₂ is used
Here's a simple PoC in JavaScript that you can try live on the browser. See the function ilog3
const POW3 = new Int32Array([ 1, 3, 9, 27, 81, 243, 729,
2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969,
14348907, 43046721, 129140163, 387420489, 1162261467 ])
function ilog2(x) {
// Here floating-point log is used because JavaScript doesn't have
// find-first-set/count-leading-zero/integer-log-2/whatever
// to get the position of the most significant bit.
// On platforms/languages with that feature we should use that instead
return Math.trunc(Math.log2(x))
}
function ilog3(x) {
let t = (ilog2(x) + 1)*323 >>> 9
return t - (x < POW3[t])
}
allOK = true
const Log3 = Math.log(3)
function check(x) {
a = ilog3(x);
b = Math.trunc(Math.log(x)/Log3);
if (a != b) {
console.log([x, a, b])
allOK = false
}
}
function checkAll(x) {
if (x > 1) { check(x - 1) }
check(x)
check(x + 1)
}
POW3.forEach(checkAll)
if (allOK) { console.log("OK") }