mul_u30_u60_hi_lo.basm

/*
  Multiplication using U15 Arithmetic
  X = a*2^15 + b
  Y = c*2^15 + d
  Z = X*Y = e*2^45+f*2^30+g*2^15+h


  Solve for e,f,g,h such that e,f,g,h are each less than 2^15
  h = (b*d).lo
  g = ((a*d).lo+(b*d).hi)+(b*c).lo
  f = ((((a*d).lo+(b*c).lo+(b*d).hi).carry+(b*c).hi)+(a*d).hi)+(a*c).lo

  e = (a*c).hi + carries from f

  then find Z.hi and Z.lo

*/

<13371337>#X
<69696969>#Y

//X = a*2^15 + b
{X}
OP_SPLIT_U30#a,b 

//Y = c*2^15 + d
{Y}
OP_SPLIT_U30#c,d

[b]
[d]
OP_MUL_U15_HI_LO#(b*d).hi,(b*d).lo
{(b*d).lo}#h
OP_TOALTSTACK // save h to alt stack

[a]
{d}
OP_MUL_U15_HI_LO#(a*d).hi,(a*d).lo
{(a*d).lo}
{(b*d).hi}
OP_ADD_U15_CARRY#carry1,((a*d).lo+(b*d).hi)
[c]
{b}
OP_MUL_U15_HI_LO#(b*c).hi,(b*c).lo
{(b*c).lo}
{((a*d).lo+(b*d).hi)}
OP_ADD_U15_CARRY#carry2,((a*d).lo+(b*d).hi)+(b*c).lo)
{((a*d).lo+(b*d).hi)+(b*c).lo)}#g 
OP_TOALTSTACK //save g to alt stack
{carry1}
{carry2}
OP_ADD#((a*d).lo+(b*c).lo+(b*d).hi).carry
{((a*d).lo+(b*c).lo+(b*d).hi).carry}
{(b*c).hi}
OP_ADD_U15_CARRY#carry3,(((a*d).lo+(b*c).lo+(b*d).hi).carry+(b*c).hi)
{(((a*d).lo+(b*c).lo+(b*d).hi).carry+(b*c).hi)}
{(a*d).hi}
OP_ADD_U15_CARRY#carry4,((((a*d).lo+(b*c).lo+(b*d).hi).carry+(b*c).hi)+(a*d).hi)
{a}
{c}
OP_MUL_U15_HI_LO#(a*c).hi,(a*c).lo
{(a*c).lo}
{((((a*d).lo+(b*c).lo+(b*d).hi).carry+(b*c).hi)+(a*d).hi)}
OP_ADD_U15_CARRY#carry5,f
{f}
OP_TOALTSTACK // push f to alt stack
OP_ADD
OP_ADD
OP_ADD#e

OP_FROMALTSTACK
OP_FROMALTSTACK
OP_FROMALTSTACK


{h}
{g}
OP_JOIN_U15_HI_LO#Z.lo


{f}
{e}
OP_JOIN_U15_HI_LO#Z.hi