# Public domain.

import signatures

maxmult = 15
# XXX: tune maxmult for b

def morebitsclear(u,v):
  if u == 0 and v == 0: return False
  while u & 1 == 0 and v & 1 == 0:
    u /= 2
    v /= 2
  if u & 1: return False
  return True

def bottom(m):
  result = 0
  for i in range(maxmult + 1):
    if i & 1:
      if morebitsclear(m - i,m - result): result = i
      if morebitsclear(m + i,m - result): result = -i
  return result

def doublescalarmultwithprecomp(m,Pmults,n,Qmults):
  if m == 0 and n == 0:
    return signatures.groupelt(0)
  if m & 1 == 0 and n & 1 == 0:
    d = doublescalarmultwithprecomp(m / 2,Pmults,n / 2,Qmults)
    return d + d
  mbottom = bottom(m)
  nbottom = bottom(n)
  d = doublescalarmultwithprecomp(m - mbottom,Pmults,n - nbottom,Qmults)
  # XXX: eliminate additions of 0
  if mbottom > 0:
    d = d + Pmults[mbottom]
  if mbottom < 0:
    d = d - Pmults[-mbottom]
  if nbottom > 0:
    d = d + Qmults[nbottom]
  if nbottom < 0:
    d = d - Qmults[-nbottom]
  return d

def precomp(P):
  result = []
  PP = P + P
  for i in range(maxmult + 1):
    if i == 0: result.append(signatures.groupelt(0))
    elif i == 1: result.append(P)
    elif i == 2: result.append(PP)
    elif i & 1: result.append(PP + result[i - 2])
    else: result.append(False)
  return result

def doublescalarmult(m,P,n,Q):
  return doublescalarmultwithprecomp(m,precomp(P),n,precomp(Q))