PromiseでNbit加算器を作るまでの壮大な話(babel replで動かせます。)

PromiseAdder.js

(()=>{
  const timeMap = new Map();
  try{
    console.time();
    console.timeEnd();
  }
  catch(err){
    console.time = function time(str){
      timeMap.set(str, Date.now());
    };
    console.timeEnd = function timeEnd(str){
      const time = timeMap.get(str);
      timeMap.delete(str);
      
      console.log(`${str}: ${Date.now()-time}ms`);
    };
  }
})();

const T = ()=> Promise.resolve(1);
const F = ()=> Promise.reject(0);

(async ()=>{
  const inA_4  = [F,T,T,T].reverse();
  const inB_4  = [F,T,T,T].reverse();
  const inA_32 = [F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T,F,T,T,T,T,T,T,F,T,F,T,F,F,T,F].reverse();
  const inB_32 = [F,F,F,F,F,F,F,F,F,F,F,T,T,T,F,T,F,T,F,F,T,F,T,T,F,T,F,F,F,F,T,F].reverse();
  
  console.time("4bit rippleAdder");
  // 4bit 0d7 + 0d7 = 0d14
  // 4bit 0b0111 + 0b0111 => 0b1110
  const resA = await Promise.all(silent(rippleAdder(4, inA_4, inB_4)));
  console.log(resA.reverse()); // [1,1,1,0]
  console.timeEnd("4bit rippleAdder");
  
  console.time("32bit rippleAdder");
  // 32bit 0d114514 + 0d1919810 => 0d2034324
  // 32bit 0b00000000000000011011111101010010 + 0b00000000000111010100101101000010 => 0b00000000000111110000101010010100
  const resB = await Promise.all(silent(rippleAdder(32, inA_32, inB_32)));
  console.log(resB.reverse()); // [0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0]
  console.timeEnd("32bit rippleAdder");
  
  console.time("4bit lookAheadAdder");
  // 4bit 0d7 + 0d7 = 0d14
  // 4bit 0b0111 + 0b0111 => 0b1110
  const resC = await Promise.all(silent(lookAheadAdder(4, inA_4, inB_4)));
  console.log(resC.reverse()); // [1,1,1,0]
  console.timeEnd("4bit lookAheadAdder");
  
  console.time("32bit lookAheadAdder");
  // 32bit 0d114514 + 0d1919810 => 0d2034324
  // 32bit 0b00000000000000011011111101010010 + 0b00000000000111010100101101000010 => 0b00000000000111110000101010010100
  const resD = await Promise.all(silent(lookAheadAdder(32, inA_32, inB_32)));
  console.log(resD.reverse()); // [0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0]
  console.timeEnd("32bit lookAheadAdder");
})().catch(err=>{
  console.error("error");
  console.error(err);
  console.error(err.stack);
});

function silent(A){
  if(A[Symbol.iterator]){
    return [...A].map(silent);
  }
  return A().catch(reason=>Promise.resolve(reason));
}

function not(A=F){
  return ()=> new Promise((resolve,reject)=>{
    // not回路50msゲート遅延
    setTimeout(()=>{
      A().then(_=>F().catch(reject))
         .catch(_=>T().then(resolve));
    },50);
  });
}

function and(A=F, B=F, ...rest){
  if(rest.length>3){
    throw new TypeError("not supported input length");
  }
  
  return ()=> new Promise((resolve, reject)=>{
    
    // and回路250msゲート遅延
    setTimeout(()=>{
      Promise.all([A,B,...rest].map(item=>item()))
        .then(_=>T().then(resolve))
        .catch(_=>F().catch(reject));
    },250);
  });
}

function nand(...args){
  return not(and(...args));
}

function or(...args){
  return not(nor(...args));
}

function nor(...args){
  return and(...args.map(item=>not(item)));
}

function xor(...args){
  const [A,B,C,D] = args;
  
  if(args.length <= 2){
    return or(and(not(A),B),and(A,not(B)));
  }
  if(args.length === 3){
    return or(
      and(not(A),not(B),C),
      and(not(A),B,not(C)),
      and(A,not(B),not(C)),
      and(A,B,C)
    );
  }
  if(args.length === 4){
    return or(
      or(
        and(not(A),not(B),not(C),D),
        and(not(A),not(B),C,not(D)),
        and(not(A),B,not(C),not(D)),
        and(not(A),B,C,D)
      ),
      or(
        and(A,not(B),not(C),not(D)),
        and(A,not(B),C,D),
        and(A,B,not(C),D),
        and(A,B,C,not(D))
      )
    );
  }
  
  throw new TypeError("not supported input length");
}

function xnor(...args){
  const [A,B,C,D] = args;
  
  if(args.length <= 2){
    // 同じ入力のXORの、Bの論理だけを全て逆転させたもの
    return or(and(not(A),not(B)),and(A,B));
  }
  if(args.length === 3){
    // 同じ入力のXORの、Cの論理だけを全て逆転させたもの
    return or(
      and(not(A),not(B),not(C)),
      and(not(A),B,C),
      and(A,not(B),C),
      and(A,B,not(C))
    );
  }
  if(args.length === 4){
    // 同じ入力のXORの、Dの論理だけを全て逆転させたもの
    return or(
      or(
        and(not(A),not(B),not(C),not(D)),
        and(not(A),not(B),C,D),
        and(not(A),B,not(C),D),
        and(not(A),B,C,not(D))
      ),
      or(
        and(A,not(B),not(C),D),
        and(A,not(B),C,not(D)),
        and(A,B,not(C),not(D)),
        and(A,B,C,D)
      )
    );
  }
  
  throw new TypeError("not supported input length");
}

// 1bitM入力1bit出力MUX
function mux(S, ...rest){
  const [A,B,C,D] = rest;
  if(!(S instanceof Array)) S = [S];
  
  if(rest.length <= 2){
    return or(
      and(not(S[0]),A),
      and(S[0],B)
    );
  }
  if(rest.length === 3){
    // 3入力MUXは、4入力MUXとして処理する
    return mux(S, A, B, C, F);
  }
  if(rest.length === 4){
    return or(
      and(not(S[1]),not(S[0]),A), // S=0b00
      and(not(S[1]),S[0],B),      // S=0b01
      and(S[1],not(S[0]),C),      // S=0b10
      and(S[1],S[0],D)            // S=0b11
    );
  }
  
  throw new TypeError("not supported input length");
}

// NbitM入力Nbit出力MUX
function muxN(N, S, ...rest){
  const [A,B,C,D] = rest;
  const output = [];
  
  if(rest.length <= 2){
    for(let i=0;i<N;++i){
      output.push(mux(S, A&&A[i], B&&B[i]));
    }
  }
  else if(rest.length === 3){
    for(let i=0;i<N;++i){
      output.push(mux(S, A&&A[i], B&&B[i], C&&C[i]));
    }
  }
  else if(rest.length === 4){
    for(let i=0;i<N;++i){
      output.push(mux(S, A&&A[i], B&&B[i], C&&C[i], D&&D[i]));
    }
  }
  else{
    throw new TypeError("not supported input length");
  }
  
  return output;
}

function halfAdder(A, B){
  return [xor(A,B), and(A,B)];
}

function fullAdder(A, B, C){
  const [S0, C0] = halfAdder(A, B);
  const [S1, C1] = halfAdder(S0, C);
  
  return [S1, or(C0, C1)];
}

// Nbit桁上げ伝搬加算器
function rippleAdder(N, A, B){
  const C = [];
  const S = [];
  
  for(let i=0;i<N;++i){
    [S[i],C[i+1]] = fullAdder(A[i], B[i], C[i]);
  }
  
  return S;
}

// 4bit桁上げ先見回路
function lookAheadCarry(A, B, C0){
  const G = [];
  const P = [];
  const C = [];
  
  // G,Pの生成
  for(let i=0;i<4;++i){
    G.push(and(A[i],B[i]));
    P.push(xor(A[i],B[i]));
  }
  
  // Cの生成
  C[0] = or(G[0],and(P[0],C0));
  C[1] = or(G[1],and(G[0],P[1]),and(P[0],P[1],C0));
  C[2] = or(G[2],and(G[1],P[2]),and(G[0],P[1],P[2]),and(P[0],P[1],P[2],C0));
  C[3] = or(G[3],and(G[2],P[3]),and(G[1],P[2],P[3]),and(G[0],P[1],P[2],P[3]),and(P[0],P[1],P[2],P[3],C0));
  
  return C;
}

// 4bit加算器
function blockAdder(A, B, C){
  const S = [];
  
  // 先に計算したキャリーを使って4bit計算する
  for(let i=0;i<4;++i){
    [S[i]] = fullAdder(A[i], B[i], C[i]);
  }
  
  return S;
}

// Nbit桁上げ先見加算器(Nは4の倍数)
function lookAheadAdder(N, A, B){
  const S = [];
  let C0 = F;
  for(let i=0;i<N;i+=4){
    // 計算対象となるA,Bの部分を予め抽出しておく
    const A4bit = A.slice(i,i+4);
    const B4bit = B.slice(i,i+4);
    
    // キャリーは4bitずつ先に計算しておく
    const C = [C0, ...lookAheadCarry(A4bit, B4bit, C0)];
    C0 = C[4];
    
    // 4bit加算させる
    Array.prototype.push.apply(S,blockAdder(A4bit, B4bit, C));
  }
  
  return S;
}