Libraries for bc and dc.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 229 lines 5.2 KiB Raw Permalink Blame History

 `#!/usr/local/bin/bc -l` `### Logic-OtherBase.BC - Attempt to extend bitwise functions into other bases` ` # see logic.bc for faster bitwise-only functions` `## XOR like` `# All of these degenerate to being identical` `# to bitwise exclusive-or in base 2` `# Workhorse function for the others` `define digitwise_xor_(which, base, x,y) {` ` auto os,n,a,b,c,p,t,z,oddbase,h` ` os=scale;scale=0` ` /* Nonsense to delete` ` # some algorithms are asymmetric. negative which swaps parameters` ` if(which<0){x+=y;y=x-y;x-=y;which=-which} #swap` ` # ^technically a bug since -0 fails, but that algorithm is symmetric anyway` ` # since some algos are asym, add the alternatives in a ratio` ` # . specified by the fractional part of which` ` if(which>(z=which/1)){` ` a=which-z` ` z=digitwise_xor_(z,base,x,y)*(1-a)+digitwise_xor_(z,base,y,x)*a` ` scale=os;return z` ` }` ` */` ` which/=1` ` base/=1;if(base<2)base=ibase` ` n=0;x/=1;y/=1` ` if(x<0){x=-1-x;n=!n}` ` if(y<0){y=-1-y;n=!n}` ` oddbase=base%2` ` z=0;t=1;p=0;while(x||y){` ` a=x-base*(h=x/base);x=h` ` b=y-base*(h=y/base);y=h` ` if(0){` ` } else if(which==-1){` ` c=a-b;if(c<0)c=-c` ` if(c+c>base)c=base-c` ` } else if(which==0){` ` c=a-b;if(c<0)c=-c` ` } else if(which==1){` ` c=a+base-b;c%=base` ` } else if(which==2){` ` c=a+b;c%=base` ` } else if(which==3){` ` c=a+b` ` if(oddbase||!c%2)c=a+base-b # odd base, or even base with odd parity` ` c%=base` ` } else if(which==4){` ` c=a;b=b%2` ` if((!oddbase&&b)||(oddbase&&p))c=base-1-a` ` if(oddbase&&b)p=1-p` ` } ` ` z+=t*c` ` t*=base` ` }` ` if(n)z=-1-z` ` scale=os;return z` `}` `# Digitwise shortest distance` `# each digit is the shortest path from digit` `# in x to digit in y modulo the base` `# e.g. shortest distance between 0 and 4 modulo 6 is 2 (not 4)` `define digitwise_sdist(base, x,y) {` ` return digitwise_xor_(-1,base,x,y)` `}` `# Digitwise logical difference` `define digitwise_diff(base, x,y) {` ` return digitwise_xor_(0,base,x,y)` `}` `# Digitwise modulo subtraction; no borrows` `# asymmetric since x-y != y-x` `define no_borrow_diff(base, x,y) {` ` return digitwise_xor_(1,base,x,y)` `}` `# Digitwise modulo sum / add ignoring carries` `define no_carry_add(base, x,y) {` ` return digitwise_xor_(2,base,x,y)` `}` `# A logical 'blend' of the previous two functions` `# also asymmetric` `define asym_mixor(base, x,y) {` ` return digitwise_xor_(3,base,x,y)` `}` `# Flip digits of x using parity of digits of y` `# necessarily asymmetric` `define asym_parity(base, x,y) {` ` return digitwise_xor_(4,base,x,y)` `}` `## AND-like` `# Positive values only for now` `define digitwise_modmult(base, x,y) {` ` auto os,a,b,c,t,z,h` ` os=scale;scale=0` ` base/=1;if(base<2)base=ibase` ` x/=1;y/=1` ` if(x<0||y<0){` ` print "digitwise_modmult: unimplemented for -ve numbers\n"` ` scale=os;return 0` ` }` ` z=0;t=1;while(x||y){` ` a=x-base*(h=x/base);x=h` ` b=y-base*(h=y/base);y=h` ` c=(a*b)%base` ` z+=t*c` ` t*=base` ` }` ` scale=os;return z` `}` `define digitwise_min(base, x,y) {` ` auto os,a,b,c,t,z,h` ` os=scale;scale=0` ` base/=1;if(base<2)base=ibase` ` x/=1;y/=1` ` if(x<0||y<0){` ` print "digitwise_min: unimplemented for -ve numbers\n"` ` scale=os;return 0` ` }` ` z=0;t=1;while(x||y){` ` a=x-base*(h=x/base);x=h` ` b=y-base*(h=y/base);y=h` ` c=a;if(a>b)c=b` ` z+=t*c` ` t*=base` ` }` ` scale=os;return z` `}` `## OR like` `define digitwise_max(base, x,y) {` ` auto os,a,b,c,t,z,h` ` os=scale;scale=0` ` base/=1;if(base<2)base=ibase` ` x/=1;y/=1` ` if(x<0||y<0){` ` print "digitwise_max: unimplemented for -ve numbers\n"` ` scale=os;return 0` ` }` ` z=0;t=1;while(x||y){` ` a=x-base*(h=x/base);x=h` ` b=y-base*(h=y/base);y=h` ` c=a;if(a(d=x-base*(h=x/base)))d=b_1-d` ` g+=p*d;p*=base;x=h` ` }` ` if(n)g=-1-g` ` scale=os;return g` `}` `define inverse_base_graycode(base,x) {` ` auto os,n,bp,b_1,a[],b,i,y,h;` ` os=scale;scale=0` ` base/=1;if(base<2)base=ibase` ` x/=1;n=0;if(x<0){n=1;x=-1-x}` ` for(i=0;x;i++){a[i]=x-base*(h=x/base);x=h}` ` bp=base%2;b_1=base-1` ` y=0;b=0;for(--i;i>=0;i--){` ` d=a[i];if(b)d=b_1-d` ` y=y*base+d` ` if(bp){b+=d}else{b=d}` ` b%=2` ` }` ` if(n)y=-1-y` ` scale=os;return y` `}` `## Hamming Distance` `# Count the number of differences between two numbers in the given base` `# . compare with digit_distance in digits.bc which` `# . takes the value of the difference into account` `define base_hamming(base,x,y) {` ` auto os,t,hx,hy;` ` os=scale;scale=0;base/=1;x/=1;y/=1` ` if(base<2)base=ibase` ` if(x<0&&y<0){x=-1-x;y=-1-y}` ` if(x<0||y<0){` ` print "base_hamming: infinite distance from mismatched signs\n";` ` scale=os;return A^os-1` ` }` ` t=0;while(x||y){hx=x/base;hy=y/base;if(x-y!=base*(hx-hy)).=t++;x=hx;y=hy}` ` scale=os;return t` ```} ``` ``` ```