float] 힙을 이용한 정밀합산 시뮬레이션..

1)
지난번에 만든 저농도(?) 부동소수점 시뮬레이터(?)로
여러개 데이터를 합산하는 시뮬레이션을 진행해봅니다.

..

2)

<style>
  div.out1_131227_2 { float:left;background-color:#ffffdd;text-align:right; }
  div.out2_131227_2 { float:left;background-color:#dddddd;text-align:left; }

  div.clear_131227_2 { clear:both; }

  div.out3_131227_2 { float:left;background-color:#ffffdd;text-align:right; }
  div.outG_131227_2 { float:left;background-color:#ddddff;text-align:center; }
  div.out4_131227_2 { float:left;background-color:#dddddd;text-align:left; }

</style>

limit <span id=limv ></span> <br><br>

<div class=out1_131227_2>
<span id=out1_131227_2></span><br>
= <span id=result1></span>
</div>

<div class=out2_131227_2 >
<span id=out2_131227_2></span><br>
= <span id=result2></span>
</div>

<div class=clear_131227_2 ></div><br>

<input type=button value="reSample" onclick=reSample(); >

<div class=clear_131227_2 ></div><br>

<div class=out3_131227_2 id=out3_131227_2 ></div>
<div class=outG_131227_2 id=outG_131227_2 ></div>
<div class=out4_131227_2 id=out4_131227_2 ></div>

<div class=clear_131227_2 ></div><br>


<script>
var
  reSample
  ;

(function(){

var

  limit=10, count=30, reCount=10, rV=10;

function $(v) { return document.getElementById(v)||document.all[v]; }

String.prototype.r=function(){
  var ar=arguments, arl=ar.length, i, ov=this;

  for (i=0; i<arl; i+=2) {
    ov=ov.replace(ar[i], ar[i+1]);
    }

  return ov;
  };

var
  eev,
  result1=$('result1'), result2=$('result2'), limv=$('limv')
  ;


limv.innerHTML=limit;

(function(){ // eev to edge & Limit value.. (epsilon)

var
  v, vv, nv, nnv, e, ee;

vv=1;

e=5000;

do {

v=1/2; ee=0;
while (nnv=vv*v) {
  nv=nnv; v*=v; if (!(--e)) break;

  ee++;
  }

if (!e) break;

vv=nv;

} while (ee>0);


v=nv;
while (v) {
  nv=v; v/=2; if (!(--e)) break;
  }

eev=nv*limit;

}());

 

function add(vv1, vv2) { // return by limit & Bigger abs's adding simulate (just sampling..)
  var va1, va2;

  va1=vv1*(vv1>0?1:-1);
  va2=vv2*(vv2>0?1:-1);

  va1=(va1<va2)?va2:va1;
 
  if (va1==0) vv1=0;
  else vv1=(vv1/va1*eev+vv2/va1*eev)*va1/eev;

  return vv1;
}

var
  out1=$('out1_131227_2'), out2=$('out2_131227_2')
  ;

function reSampleOne(){
  var
    a=[], i
    , b, bb, oo1, oox
    ;

// first : sequence add

  for (i=1; i<=count; i++) {
    a[i]=Math.random()*rV;
    }

  b=0; bb=0; oo1=''; for (i=1; i<=count; i++) {
    b=add(b, a[i]); oo1+=('{g}{v} [{p}] ( = {s} )<'+'br>').r(/{g}/, oo1?' + ':'', /{v}/, a[i], /{p}/, i, /{s}/, b);
    bb+=a[i];
    }

  out1.innerHTML=oo1;
  result1.innerHTML=bb+' ( = '+b+' )';


// second : heap add

  var swapc; function swap(a, x, y) { swapc=a[x]; a[x]=a[y]; a[y]=swapc; }

  var
    ba=[], bd=[], be=[], bc=count, bl, br, bp, biv, bpv, j, k, count2
    ;

oo1=''; count2=count;

  for (i=1; i<=count; i++) {
    ba[i]=a[i];

bd[i]=i; be[i]=a[i];
    }

  for (i=count>>1; i>0; i--) { // heap init

    j=i; while (j<<1<=count) {
      bl=j+j; br=bl+1;
      if (br>count) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(bd, bp, j); swap(be, bp, j);

        }
        else break;
      j=bp;
      }
    }

// third : heap adding

  for (i=count; i>1; i--) {

    j=1;

    bl=2; br=3;
    if (br>i) bp=bl;
      else if (ba[bl]<ba[br]) bp=bl; else bp=br;

oox='{v} [{p}] + {w} [{q}] '.r(/{v}/, ba[bp], /{p}/, bd[bp], /{w}/, ba[j], /{q}/, bd[j]);

    ba[bp]=add(ba[bp], ba[j]);
count2++; bd[bp]=count2;
be[bp]+=be[j];

oo1+=('( {v} [{p}] =) {oox}<'+'br>').r(/{v}/, ba[bp], /{p}/, bd[bp], /{oox}/, oox);

    j=bp; while (j<<1<=i) {
      bl=j+j; br=bl+1;
      if (br>i) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(bd, bp, j); swap(be, bp, j);

        }
        else break;
      j=bp;

      }


// move & cut by I

    j=1;
    ba[j]=ba[i];
bd[j]=bd[i]; be[j]=be[i];

    while (j<<1<i) {
      bl=j+j; br=bl+1;
      if (br>=i) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(bd, bp, j); swap(be, bp, j);

        }
        else break;
      j=bp;

      }

    }

  out2.innerHTML=oo1;
  result2.innerHTML='( {v} = ) {w}'.r(/{v}/, ba[1], /{w}/, be[1]);

};

var
  out3=$('out3_131227_2'), out4=$('out4_131227_2'), outG=$('outG_131227_2'), ooa=[], ool=[], oor=[]

  , gv='::::::::::::::::::::', ge=/:/g,  gl=gv.length
  , ggv='....................', gge=/\./g
  , lgv, lge, rgv, rge
  ;

function reSampleMore() {
  var
    i, abs=Math.abs, nn, mm, ll, cc, ln=Math.log, hl, hv
    , oo1, oovl, oovr
    ;

  ooa.length=0;
  for (i=0; i<reCount; i++) {
    reSample2(ooa);
    }

  for (i=0; i<ooa.length; i+=2) {
    cc=ooa[i]-ooa[i+1];
    if (!cc) continue;
    nn=mm=abs(cc);
    break;
    }

  for (;i<ooa.length; i+=2) {
    cc=ooa[i]-ooa[i+1];
    if (!cc) continue;

    cc=abs(cc);
    if (nn>cc) nn=cc;
    if (mm<cc) mm=cc;
    }

  nn=ln(nn); mm=ln(mm); ll=mm-nn;

  ool.length=0; oor.length=0; oo1=''; oovl=0; oovr=0;
  for (i=0; i<ooa.length; i+=4) {

    if (abs(ooa[i]-ooa[i+1])<=abs(ooa[i+2]-ooa[i+3]))
      { lgv=gv; lge=ge; rgv=ggv; rge=gge; oo1+='< &nbsp; &nbsp;<'+'br>'; oovl++; }
    else
      { lgv=ggv; lge=gge; rgv=gv; rge=ge; oo1+='&nbsp; &nbsp; ><'+'br>'; oovr++; }

    cc=ooa[i]-ooa[i+1]; if (!cc) hl=0;
      else hl=((ln(abs(cc))-nn)/ll*gl)<<0;
    hv=lgv.substr(0, gl-hl).replace(lge, '&nbsp;')+lgv.substr(0, hl);

    ool.push(ooa[i+1]+' : ( '+(((cc*10)<<0)/10)+' ) '+ooa[i]+' '+hv);

    cc=ooa[i+2]-ooa[i+3]; if (!cc) hl=0;
      else hl=((ln(abs(cc))-nn)/ll*gl)<<0;
    hv=rgv.substr(0, hl)+rgv.substr(0, gl-hl).replace(rge, '&nbsp;');

    oor.push(hv+' '+ooa[i+3]+' ( '+(((cc*10)<<0)/10)+' ) : '+ooa[i+2]);
    }

  out3.innerHTML=ool.join('<'+'br>');
  out4.innerHTML=oor.join('<'+'br>');
  outG.innerHTML=oo1+'{l} : {r}'.r(/{l}/, oovl, /{r}/, oovr);
  }

function reSample2(outa){
  var
    a=[], i
    , b, bb
    ;

// first : sequence add

  for (i=1; i<=count; i++) {
    a[i]=Math.random()*rV;
    }

  b=0; bb=0; for (i=1; i<=count; i++) {
    b=add(b, a[i]);
    bb+=a[i];
    }

outa.push(b);
outa.push(bb);


// second : heap add

  var swapc; function swap(a, x, y) { swapc=a[x]; a[x]=a[y]; a[y]=swapc; }

  var
    ba=[], be=[], bc=count, bl, br, bp, biv, bpv, j, k
    ;

  for (i=1; i<=count; i++) {
    ba[i]=a[i];

be[i]=a[i];
    }

  for (i=count>>1; i>0; i--) { // heap init

    j=i; while (j<<1<=count) {
      bl=j+j; br=bl+1;
      if (br>count) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(be, bp, j);
        }
        else break;
      j=bp;
      }
    }

// third : heap adding

  for (i=count; i>1; i--) {

    j=1;

    bl=2; br=3;
    if (br>i) bp=bl;
      else if (ba[bl]<ba[br]) bp=bl; else bp=br;

    ba[bp]=add(ba[bp], ba[j]);

be[bp]+=be[j];

    j=bp; while (j<<1<=i) {
      bl=j+j; br=bl+1;
      if (br>i) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(be, bp, j);
        }
        else break;
      j=bp;

      }


// move & cut by I

    j=1;
    ba[j]=ba[i];

be[j]=be[i];

    while (j<<1<i) {
      bl=j+j; br=bl+1;
      if (br>=i) bp=bl;
        else if (ba[bl]<ba[br]) bp=bl; else bp=br;

      if (ba[j]>ba[bp]) {
        swap(ba, bp, j);

swap(be, bp, j);
        }
        else break;
      j=bp;

      }

    }

outa.push(be[1]);
outa.push(ba[1]);

};

reSample=function(){
  reSampleOne(); reSampleMore();
  };

reSample();

}());
</script>

-- 새 창에 샘플 띄우기.. --

..

3)

limit

=

=

..

4)
실제 합산값과 가상 합산값을 비교한다는 내용입니다. 
결국은 힙을 이용해서 최저값을 더한다는 내용이긴 하죠.

물론, 그냥 합산한 값이 힙을 이용해 합산한 경우보다 오차가 적은 경우도 있습니다.
우연..처럼 거의 맞아떨어지는 경우도 있죠.

하지만, 이번 연산처럼 적은(?) 횟수가 아닌, 많은 횟수가 되는 경우라면 얘기가 달라집니다.
나중에 가면, 연산가능범위를 넘어가기 때문에, 힙이 아니면 덧셈이 안되요.

.. 물론, 힙의 경우,
합해야할 수가 많아질수록 두 값의 차가 적어질 확률이 높아지니 당연하긴 합니다만,
그만큼(?), 오차확률이 적어진다는 뜻도 되겠죠.

5)
힙을 이용한 합산의 경우, 오차확율이 적어지는(?) 만큼, cpu부하량(?)과 메모리 사용량이 증가하게 됩니다.
힙을 계속 유지하는 문제로, 더하는 데 걸리는 시간은 기존 n 에서 n log (n) 이 되겠죠.

.. 1만개 값을 더한다면, 1만개만큼 메모리가 필요하다는 뜻이죠. (참고 : 100x100 pixel 이미지..)

6)
.. 힙 합산을 만들기 전에도 생각해본 문제입니다만, 뺼셈에 대한 대비책이 없어요..

절대값을 기준으로 정렬해서 차이가 적은 거울형태의 값들을 우선 처리하면 좋을텐데요, 
아직 확실하게 정립된 방법은 못찾아서요..

.. 여기까지로만 마무리합니다.

wantHate killofki@.