Skip to content

Instantly share code, notes, and snippets.

@g-leech

g-leech/pow3.py Secret

Created Jun 4, 2021
Embed
What would you like to do?
import sys, math
MAX = sys.maxsize
MAX_POWER = math.floor(math.log(MAX, 3))
MAX_3 = 3**MAX_POWER
def isPowerOf3(x):
return MAX_3 % x == 0
print(isPowerOf3(27))
print(isPowerOf3(6))
@NunoSempere

This comment has been minimized.

Copy link

@NunoSempere NunoSempere commented Jun 5, 2021

This method isn't actually constant time; the % operator takes longer to execute for different inputs.

Checking this on node:

let MAX = Number.MAX_SAFE_INTEGER
let MAX_POWER = Math.floor(Math.log(MAX, 3))
MAX_3 = 3**MAX_POWER
let isPowerOfThree = x => MAX_3 % x == 0

let timeFunction = (f) => {
  let init = new Date()
  for (i = 0; i < 10**8; i++) {
    f()
  }
  let end = new Date()
  return end-init
}
let f1 = () => isPowerOfThree(1)
let f2 = () => isPowerOfThree(MAX_3-1)
let f3 = () => isPowerOfThree(3**10)

timeFunction(f1) // 246
timeFunction(f2) // 815
timeFunction(f3) // 812
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment