#!/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 }