LongIntegerAddition.mac

/* Some list helper functions */

elementOrVal (l, idx, v) := block(
  [res],
  if length(l) >= idx and idx > 0 then
    res: l[idx]
  else
    res: v,
  res
);
 
/* Primitive arithmetics on single digits */
   
   
halfAdder (a,b,c) := block(
  [sum, carry, res],
  res: divide(a + b + c,10),
  carry: res[1],
  sum: res[2],
  [carry, sum]
);
halfSubtracter (a,b,c) := block(
  [diff, carry, res],
  res: divide(10 - ((b + c)-a), 10),
  diff: res[2],
  carry: (1 - res[1]),
  [carry, diff]
);

/* -------------add and subtract functions for unsigned lists: ------------------*/
   
addList (x,y) := block(
  [res, idx, len, xlen, ylen, sum],
  xlen: length(x),
  ylen: length(y),
  len: max( xlen, ylen ),
  res: [],
  sum: [0,0],
  idx: len,
  for idx: len step -1 thru 1 do (
     sum: halfAdder(
       elementOrVal(x, max(0,idx-(len-xlen)), 0), 
       elementOrVal(y, max(0,idx-(len-ylen)), 0), 
       sum[1]
     ),
     res: cons(sum[2], res)
  ),
  res
);
 
subtractList (x,y) := block(
  [res, idx, len, xlen, ylen, sum],
  xlen: length(x),
  ylen: length(y),
  len: max( xlen, ylen ),
  res: [],
  sum: [0,0],
  idx: len,
  for idx: len step -1 thru 1 do (
     sum: halfSubtracter(
       elementOrVal(x, max(0,idx-(len-xlen)), 0), 
       elementOrVal(y, max(0,idx-(len-ylen)), 0), 
       sum[1]
     ),
     res: cons(sum[2], res)
  ),
  res
);