pow.nim

proc isEven(x:Tinteger): bool =
  (x and 1) == 0

proc isOdd(x:Tinteger): bool =
  not isEven(x)

proc maybeMod[T:Tinteger](x: T, module:Natural): T = 
  if module > 0: result = x mod module 
  else: result = x

proc returnPow[T:Tinteger](base, exp, value: T, module: T = 0): T = 
  result = value
  when T is TSignedInt:
    if base < 0.T and isOdd(exp):
      result = -result
  if module > 0.T:
    result = result mod module

proc generalPow[T:Tinteger](base: T, exp, module:Natural = 0): T =
  when T is TSignedInt:
    const bits = base.sizeOf() * 8 - 1
    let absBase = abs(base)
  else:
    const bits = base.sizeOf() * 8
    let absBase = base
    
  case absBase:
    of 0: return if exp == 0: 1 else: 0
    of 1: return returnPow(base, exp, 1)
    of 2: 
      if exp < bits: 
        return returnPow(base, exp, 1.T shl exp, module).maybeMod(module)
    else: discard
  
  var b = base.maybeMod(module)
  var e = exp
  result = 1
  
  while e > 0:
    if isOdd(e):
      result *= b
      result = result.maybeMod(module)
    e = e shr 1
    b *= b
    b = b.maybeMod(module)