uses console
namespace bignum


  '
  int negative
  string remainder
  '
  macro tobin(s,  bb,le) {
  ========================
  int le=len s
  sbyte bb at strptr s
  while le
    bb-=48
    @bb++ : le--
  wend
  }
  macro toasc(s,  bb,le) {
  ========================
  int le=len s
  sbyte bb at strptr s
  while le
    bb+=48
    @bb++ : le--
  wend
  }
  '
  macro tobin2(s,  bb,bu,le) {
  ============================
  int le=len s
  sbyte bb at strptr(s)+len(s)-1
  sbyte bu at @bb-1
  while le
    bb-=48
    le--
    if le then
      bu-=48
      bb=bu*10+bb 'consolidated byte 0..99
      bu=0
      le-- : @bb-=2 : @bu-=2
    end if
  wend
  }
  macro toasc2(s,  bb,bu,le) {
  ============================
  int le=len s
  sbyte bb at strptr(s)+len(s)-1
  sbyte bu at @bb-1
  while le
    le--
    if le then
      bu=bb\10
      bb=edx+48 'remainder edx   
      le-- : @bb-- : @bu-=2
    end if
    bb+=48 : @bb--
  wend
  }
  '
  function PadLeftZeros(string *n1,*n2)
  =====================================
  int l1=len n1
  int l2=len n2
  if l1>l2 then n2=stringbytes(l1-l2,48)+n2 : return
  if l2>l1 then n1=stringbytes(l2-l1,48)+n1 : return
  end function

  function TrimLeftZeros(string *s)
  =================================
  int  ls=len s
  byte bs at strptr s
  while bs<=48
    @bs++
    ls--
  wend
  s = mid s,ls
  end function

  function AlignLeft(string *n1,*n2)
  ===================================
  int l1=len n1
  int l2=len n2
  if l1>l2 then n2+=stringbytes(l1-l2,0) : return
  if l2>l1 then n1+=stringbytes(l2-l1,0) : return
  end function

  function AlignRight(string *n1,*n2)
  ===================================
  int l1=len n1
  int l2=len n2
  if l1>l2 then n2=stringbytes(l1-l2,0)+n2 : return
  if l2>l1 then n1=stringbytes(l2-l1,0)+n1 : return
  end function

  function add(string sa,sb) as string
  ====================================
  string a=sa
  string b=sb
  tobin a
  tobin b
  alignRight a,b
  int la=len a
  int lb=la
  int lr=la
  lr++ 'allow for carry
  string r=nuls lr
  sbyte aa at strptr(a)+la-1
  sbyte bb at strptr(b)+lb-1
  sbyte rr at strptr(r)+lr-1
  sbyte d,carry
  while lr>1
    d=aa+bb+carry
    if d>9 then d-=10 : carry=1 else carry=0
    rr=d
    @aa-- : @bb-- : @rr--
    la-- : lb-- : lr--
  wend
  if carry then
    rr=carry
  else
    if len(r)>1 then r=mid r,2
  end if
  toasc r
  return r
  end function
  '
  function addLTR(string sa,sb) as string
  =======================================
  'left to right addition
  string a=sa
  string b=sb
  tobin a
  tobin b
  alignRight a,b
  int la=len a
  int lb=la
  int lr=la
  lr++ 'allow for carry
  string r=nuls lr
  sbyte aa at strptr(a)
  sbyte bb at strptr(b)
  sbyte rr at strptr(r)
  sbyte d,carry,pd
  int nines,i
  while la>0
    d=aa+bb
    if d>9 then d-=10 : carry=1 else carry=0
    if d=9 then
      nines++
    else
      rr=pd+carry : @rr++ : pd=d
      if nines then
        if carry then d=0 else d=9
        for i=1 to nines : rr=d : @rr++ : next
      endif
    end if
    @aa++ : @bb++
    la--
  wend
  rr=pd : @rr++
  if nines then
    for i=1 to nines : rr=9 : @rr++ : next
  endif
  @rr=strptr r
  if rr=0 then
    if len(r)>1 then r=mid r,2
  end if
  toasc r
  return r
  end function
  '
  function TensComplement(string s)
  =================================
  if not s then return
  int ls=len s
  sbyte ss at strptr(s)+ls-1
  int carry=1
  while ls
    ss=carry+9-ss
    if ss=10 then ss=0 : carry=1 else carry=0
    @ss--
    ls--
  wend
  end function
  '
  function sub(string sa,sb) as string
  ====================================
  negative=0
  if not sa then
    negative=1
    return sb
  elseif not sb then
    return sa
  end if
  string a=sa
  string b=sb
  tobin a
  tobin b
  alignRight a,b
  int la=len a
  int lb=la
  int lr=la
  string r=nuls lr
  byte aa at strptr(a)+la-1
  byte bb at strptr(b)+lb-1
  byte rr at strptr(r)+lr-1
  sbyte d,va,vb,carry
  while lr
    if la<=0 then va=0 else va=aa
    if lb<=0 then vb=0 else vb=bb
    d=va-vb-carry
    if d<0 then d+=10 : carry=1 else carry=0
    rr=d
    @aa-- : @bb-- : @rr--
    la-- : lb-- : lr--
  wend
  if carry then negative=1 : tensComplement r
  toasc r
  return r
  end function
  '
  function mul(string sa,sb) as string
  ====================================
  if not sa then return "0"
  if not sb then return "0"
  string a=sa, b=sb
  tobin a
  tobin b
  int la=len a
  int lb=len b
  int lr=la+lb
  string r=nuls lr
  sbyte aa at strptr(a)+la-1
  sbyte bb at strptr(b)+lb-1
  sbyte rr at strptr(r)+lr-1
  int  ca,cb,va,vb,vr,cy
  sbyte d,carry
  sys pa=@aa, pr=@rr
  cb=lb
  while cb 'multiply A by each digit in B
    ca=la : @aa=pa : @rr=pr
    carry=0
    while ca 'multiply thru by 1 digit from B
      va=aa : vb=bb : vr=rr
      d=aa*bb+rr+carry 'max 99
      if d>=10 then
        carry=d\10 : d=d-carry*10
      else
        carry=0
      end if
      rr=d    
      @aa-- : @rr-- : ca--
    wend
    rr=carry
    @bb-- : cb-- : pr-- 'shift R and B for next multiplier digit
  wend
  toasc r
  if rr>48 then return r else return mid r,2
  end function
  '
  function mul1(string sa,sb) as string
  ====================================
  if not sa then return "0"
  if not sb then return "0"
  'create lookup for multiples of a *1..*9
  int i,j
  static string mtbl[10]
  mtbl[1]=sa
  for i=2 to 9
    j=i-1
    mtbl[i]=add(mtbl[j],mtbl[1])
  next
  for i=1 to 9
    tobin mtbl[i]
  next
  '
  string a=sa, b=sb
  tobin a
  tobin b
  int la=len a
  int lb=len b
  int lr=la+lb
  string r=nuls lr
  byte aa at strptr(a)+la-1
  byte bb at strptr(b)+lb-1
  byte rr at strptr(r)+lr-1
  byte d,carry
  sys pa, pr=@rr
  while lb>0 'multiply A by each digit in B
    i=bb
    carry=0
    if i then 'otherwise omit line add
      la=len(mtbl[i])
      pa=strptr(mtbl[i])+la-1
      @aa=pa : @rr=pr
      while la 'add multiple selected by BB digit
        d=aa+rr+carry
        if d>=10 then
          d-=10 : carry=1
        else
          carry=0
        end if
        rr=d
        @aa-- : @rr-- : la--
      wend
      rr=carry
    end if
    @bb-- : lb-- : pr-- 'shift R and B for next multiplier digit
  wend
  toasc r
  @rr=strptr r
  if rr>48 then return r else return mid r,2
  end function
  '
  function mul2(string sa,sb) as string
  ====================================
  if not sa then return "0"
  if not sb then return "0"
  'create lookup for multiples of a *1..*9
  int i,j
  static string mtbl[100]
  mtbl[1]=sa
  for i=2 to 99
    j=i-1
    mtbl[i]=add(mtbl[j],mtbl[1])
  next
  for i=1 to 99
    tobin2 mtbl[i]
  next
  '
  string a=sa, b=sb
  tobin2 a
  tobin2 b
  int la=len a
  int lb=len b
  int lr=la+lb
  string r=nuls lr
  byte aa at strptr(a)+la-1
  byte bb at strptr(b)+lb-1
  byte rr at strptr(r)+lr-1
  'byte d,carry
  sys pa, pr=@rr
  while lb>0 'multiply A by each digit in B
    i=bb
    'carry=0
    if i then 'otherwise omit line add
      la=len(mtbl[i])
      pa=strptr(mtbl[i])+la-1
      '@aa=pa : @rr=pr
      'while la>0 'add multiple selected by BB digit
      '  d=aa+rr+carry
      'if d>=100 then
      '  d-=100 : carry=1
      '  else
      '    carry=0
      '  end if
      '  rr=d    
      '  @aa-=2 : @rr-=2 : la-=2
      'wend
      'rr=carry
      '
      mov esi,pa
      mov edi,pr
      mov ecx,la
      end namespace
      mov ah,0
      (
        cmp ecx,0
        jle exit 
        mov al,[esi]
        add al,[edi]
        add al,ah
        mov ah,0 'carry
        cmp al,100
        (
          jb exit
          sub al,100
          mov ah,1 'carry
        )
        mov [edi],al
        sub ecx,2
        sub esi,2
        sub edi,2
        repeat
      )
      mov [edi],ah 'carry
      namespace bignum
    end if
    @bb-=2 : lb-=2 : pr-=2 'shift R and B for next multiplier digit
  wend
  toasc2 r
  @rr=strptr r
  if rr>48 then return r else return mid r,2
  end function
  '
  function compare(string a,b) as int
  ===================================
  int la=len a
  int lb=len b
  byte aa at strptr a
  byte bb at strptr b
  while la
    if aa then exit while 'otherwise skip leading zeros
    la-- : @aa++
  wend
  while lb
    if bb then exit while 'otherwise skip leading zeros
    lb-- : @bb++
  wend
  if la>lb then
    return 1
  elseif lb>la
    return -1
  else 'equal length
    while la
      if aa>bb then return 1
      if aa<bb then return -1
      la--
    wend
  end if
  end function
  '
  function compareMid(int i, string a,b) as int
  =============================================
  i-- 'convert to base 0
  int la=len(a)-i
  int lb=len b
  byte aa at i+strptr a
  byte bb at strptr b
  if lb>la
    return -1
  else
    while lb
      if aa>bb then return 1
      if aa<bb then return -1
      lb-- : @aa++ : @bb++
    wend
  end if
  end function
  '
  function nullTrim(string a) as string
  =====================================
  byte aa at strptr a
  int la=len a
  int c=1
  while la
    if aa>0 then return mid a,c
    la-- : c++ : @aa++
  wend
  end function
  '
  function zeroTrim(string a) as string
  =====================================
  byte aa at strptr a
  int la=len a
  int c=1
  while la
    if aa>48 then return mid a,c
    la-- : c++ : @aa++
  wend
  end function
  '
  function div(string sa,sb) as string
  ====================================
  string a="0"+zerotrim(sa)
  int la=len a
  string b="0"+zerotrim(sb)
  int lb=len b
  tobin a : tobin b
  int lo=la-lb+1
  string o=nuls lo
  '
  'CREATE LOOKUP TABLE 1xB 2xB ..9xB
  indexbase 1
  string tbl[9]
  int i,j,k,cy
  sbyte *ti,*tj
  tbl[1]=b : j=1
  for i=2 to 9
    tbl[i]=b
    @ti = strptr(tbl[i])+lb-1
    @tj = strptr(tbl[j])+lb-1
    cy=0
    for k=1 to lb 'add digits
      ti=ti+tj+cy
      if ti>=10 then ti-=10 : cy=1 else cy=0
      @ti-- : @tj--
    next
    j++
  next
  '
  sbyte aa at strptr(a)
  sbyte bb at strptr(b)
  sbyte oo at strptr(o)
  sbyte d,carry
  int i,j,k,c,cb,cm
  sys pa=@aa
  for i = 1 to lo 'setting dividend digits
    c=9 'default digit
    for k=1 to 9
      cm=CompareMid(i,a,tbl[k]) 'lookup multiple of b
      if cm<0 then c=k-1 : exit for 'set digit
    next
    if c then 'perform subtraction
      @aa=pa+i+lb-2
      @bb=strptr(tbl[c])+lb-1
      cb=lb
      carry=0
      for j=1 to lb 'subtraction
        d=aa-bb-carry
        if d<0 then d+=10 : carry=1 else carry=0
        aa=d
        @bb-- : @aa--
      next 'next subtraction digit
    end if 'subtraction
    oo=c 'set dividend digit as subraction count
    @oo++
  next  'next dividend digit
  remainder=nullTrim a
  o=nulltrim o
  if not o then o=chr 0
  toasc o
  toasc remainder
  return o
  end function
  '

'TEST
print "Factorials:" cr cr

string sa,sb,sr
sa=1
int i
for i=1 to 50
  sb=i
  sa=mul sa,sb
  print i tab sa "(" len(sa) " digits)" cr
next

sr=add sa,sa
print "add " tab sr cr
'i=compare(sr,sa)
i=compareMid(1,sr,sa)
print "comp " tab i cr
'i=compare(sa,sr)
i=compareMid(1,sa,sr)
print "comp " tab i cr
sr=sub sr,sa
print "sub " tab sr cr
sr=div sa,40000
'sr=div sa,sa '1
'sr=div sa,1 'sa
'sr=div sa,0 '99999..
print "div " tab sr cr
'
'RECIPROCAL
sa="1"+stringbytes(70,48)
sb="777"
int lb=len sb
sr=div sa,sb
print "1/"+sb tab "0."+string(lb-1,"0") sr cr
print cr cr
'
'SQUARE ROOT
'...

/*
print "fibonacci" cr
sa=0
sb=1
for i=1 to 100
  sr=add sa,sb
  print i tab sr cr
  sa=sb
  sb=sr
next
*/

int nr,n1,n2,sw,np,op,dp1,dp2,dpr
string s1,s2
sa=82340000
sb=2234
n1=1
n2=0
dp1=4
dp2=2
op=47 '43.45,42,47,92

print "signs and decimal places" cr cr
sw=0 : nr=0
if op=43 then
  if n1 then
    if n2 then
      nr=1
    else
      sw=1 : op=45
    end if
  else
    if n2 then
      op=45
    end if
  end if
elseif op=45 then
  if n1 then
    if n2 then
      sw=1
    else
      op=43 : nr=1
    end if
  else 'n1=0
    if n2 then
      op=43
    end if 
  end if
else 'if op=42 or op=47 or op=92
  nr=0 : sw=0
  if n1 then
    if not n2 then nr=1
  else 'noyn1 
    if n2 then nr=1
 end if
end if 'op=?

  
if sw then s1=sb : s2=sa else s1=sa : s2=sb
dpr=dp1
select op
case 45 : sr=sub s1,s2
case 43 : sr=add s1,s2
case 42 : sr=mul s1,s2 : dpr=dp1+dp2
case 47 : sr=div s1,s2
case 92 : sr=div s1,s2
case else : sr="operator unknown"
end select
'
if negative then nr=1-nr : negative=0

macro show(sr)

if dpr then
  i=len(sr)-dpr
  print left(sr,i) + "." mid(sr,i+1)
else
  print sr
end if
if nr then print " (-)"
print cr
end macro


'show sr

printl "Test bignum::add"
string n1,n2,result
n1="56712345646897989899898"
n2="4321078787800789457899799978151512"
PadLeftZeros(n1,n2)
printl "n1 = " n1
printl "n2 = " n2
printl "sum= " add(n1,n2)
print cr
'
printl "Test bignum::mul"
string n1,n2,result
n1="56712345646897989899898"
n2="4321078787800789457899799978151512"
printl "n1 = " n1
printl "n2 = " n2
printl "mult= " mul(n1,n2)
print cr
end namespace

#ifndef karatsuba
  printl "Enter ..."
  waitkey
#endif
