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.

#### 398 lines 11 KiB Raw Permalink Blame History

 `#!/usr/local/bin/bc -l` `### Digits.BC - Treat numbers as strings of digits` `bijective=0` `# Returns x mod y, but sets 0 mod y to be y itself in bijective mode` `# . Old version: define bmod_(x,y) { if(bijective){return (x-1)%y+1}else{return x%y} }` `# . This version sets a global variable called bdiv_ containing the result` `# . . of the complementary division` `define bmod_(x,y) { return x-y*(bdiv_=(x-=bijective)/y); }` `# Workhorse function - use POSIX scope to check` `# . 'base' parameter of many functions here` `define base_check_() {` ` if(base<2-(bijective=!!bijective)){` ` if(base<=-2){` ` print "Negative bases not currently supported; "` ` } else if(base==-1||base==0||base==1) {` ` print "Nonsense base: ",base,"; "` ` }` ` print "Using ibase instead.\n"` ` base=ibase` ` }` `}` `# Number of digits in the base representation of x` `# (compare the int_log function in funcs.bc)` `define digits(base,x) { ` ` auto os,p,c;` ` os=scale;scale=0;base/=1;x/=1` ` if(x<0)x=-x` ` .=base_check_()` ` if(bijective&&base==1){scale=os;return x}` ` if(x==0){scale=os;return !bijective}` ` if(bijective)x=x*(base-1)+1` ` if(xA){c*=(digits(base,A)-1);if(base<4)c-=2}else{c=0}` ` }else{` ` c/=length(base)` ` }` ` p=base^c` ` while(p<=x){.=c++;p*=base}` ` scale=os;return(c-bijective)` `}` `# Sum of digits in a number: 1235 -> 11 in base ten` `define digit_sum(base,x) {` ` auto os,t;` ` os=scale;scale=0;base/=1;x/=1` ` .=base_check_()` ` t=0;while(x){t+=bmod_(x,base);x=bdiv_}` ` scale=os;return(t)` `}` `# Workhorse for the next two functions` `define digit_distance_(base,x,y,sh) {` ` auto os,sgn,dx,dy,d,t;` ` os=scale;scale=0;base/=1;x/=1;y/=1` ` if(x==y||x==-y){scale=os;return 0}` ` if(x==0||y==0){scale=os;return digit_sum(base,x+y)}` ` .=base_check_()` ` sign=1` ` if(x<0){x=-x;sign=-sign}` ` if(y<0){y=-y;sign=-sign}` ` t=0;` ` while(x||y){` ` dx=bmod_(x,base);x=bdiv_` ` dy=bmod_(y,base);y=bdiv_` ` d=dx-dy` ` if(d<0)d=-d;if(sh)if(d+d>base)d=base-d` ` t+=d` ` }` ` scale=os;return sign*t` `}` `# Digit distance between two numbers:` `# . e.g. 746(-)196 -> |7-1|+|4-9|+|6-6| = 6+5+0 = 11 in base ten` `# . Degenerates to digit_sum if either of x or y is zero` `# . Not equivalent to hamming distance` `# . + which merely counts the number of differences` `# . . See logic_otherbase.bc for hamming distance function` `define digit_distance(base,x,y) {` ` return digit_distance_(base,x,y,0)` `}` `# Digit distance between two numbers assuming shortest path modulo` `# the given base, e.g. shortest distance between 2 and 8 mod ten is 4` `# . e.g. 746((-))196 -> 4 + 5 + 0 = 9 base ten` `define digit_sdistance(base,x,y) {` ` return digit_distance_(base,x,y,1)` `}` `# Product of digits in number` `# e.g. 235 -> 2*3*5 = 30 in base ten` `# . see digits_misc.bc for two alternatives to this function` `define digit_product(base,x) { ` ` auto os,t;` ` if(x<0)return digit_product(base,-x);` ` os=scale;scale=0;base/=1;x/=1` ` .=base_check_()` ` t=1;while(x&&t){t*=bmod_(x,base);x=bdiv_}` ` scale=os;return(t)` `}` `# Reverse the digits in x using given base` `define reverse(base,x) {` ` auto os,y;` ` os=scale;scale=0;base/=1;x/=1` ` .=base_check_()` ` y=0;while(x){y=base*y+bmod_(x,base);x=bdiv_}` ` scale=os;return(y) ` `}` `## Palindromes` `# Determine if x is a palindrome in the given base` `define is_palindrome(base,x){` ` if(x<0)x=-x` ` return reverse(base,x)==x` `}` `# Determine if x is a pseudopalindrome in the given base` `# - a pseudopalindrome is a number that could be a palindrome` `# if a number of zeroes is prepended to the beginning;` `# e.g. 101 is a palindrome, but 1010 is not, however 01010,` `# which represents the same value, is palindromic` `# All palindromes are also pseudopalindromes since the prepending` `# of no zeroes at all is also an option` `define is_pseudopalindrome(base,x){` ` auto os` ` if(bijective)return is_palindrome(base,x);` ` os=scale;scale=0;base/=1;x/=1` ` .=base_check_()` ` if(x==0){scale=os;return 1}` ` if(x<0)x=-x` ` while(x%base==0)x/=base` ` scale=os;return reverse(base,x)==x` `}` `# returns an odd-lengthed palindrome in the given base, specified by x` `define make_odd_palindrome(base, x) {` ` auto s` ` .=base_check_()` ` s=1;if(x<0){s=-1;x=-x}` ` x+=bijective;.=bmod_(x,base)` ` x=x*base^(digits(base,x)-1) + reverse(base,bdiv_)` ` return s*x` `}` `# returns an even-lengthed palindrome in the given base, specified by x` `define make_even_palindrome(base, x) {` ` auto s` ` .=base_check_()` ` s=1;if(x<0){s=-1;x=-x}` ` x+=bijective;` ` x=x*base^digits(base,x) + reverse(base,x)` ` return s*x` `}` ` #base ten thoughts:` ` #output will have either 2n-1 or 2n digits` ` #x=19; => n=digits((19+1)/2)= digits(10)=2` ` #block for n=1 runs from 1 to 1 +9 +9 -1=18` ` #block for n=2 runs from 19 to 19 +90 +90 -1=198` ` #block for n=3 runs from 199 to 199+900+900-1=1998` ` #block for n runs from 2*10^(n-1)-1 to 2*10^n-2` ` # where is x within that block?` ` # last entry of first half of block is akin to 19+90-1=108 or 199+900-1=1098` ` # i.e. 10^n-10^(n-1)-2 = 11*10^(n-1)-2` ` # so if x < 11*10^(n-1)-1, x is in the first half` ` #` ` # if x is in first half, must subtract 9 or 99 etc. = 10^(n-1)-1` ` # if x is in second half, must subtract 99 or 999 etc. = 10^n - 1` ` # depending on half choose odd or even palindrome based on x` `# for each integer x, return a unique palindrome in the given base` `# i.e. map the integers into palindromes` `# n.b. map _is_ strictly increasing` `define map_palindrome(base, x) {` ` auto os,r,s` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;x/=1` ` s=1;if(x<0){s=-1;x=-x}` ` .=base_check_()` ` r=base^(digits(base,(x+1)/2)-1)` ` if(x<(base+1)*r-1){` ` x = make_odd_palindrome(base,x-r+1)` ` } else {` ` x = make_even_palindrome(base,x-r*base+1)` ` }` ` scale=os;return s*x` `}` `# from a palindrome in a given base, generate a unique integer` `# i.e. map the class of palindromes into the integers` `define unmap_palindrome(base, x) {` ` auto os,r,s` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0` ` s=1;if(x<0){s=-1;x=-x}` ` .=base_check_()` ` r=base^(digits(base,x)/2)` ` x=x/r+r-1` ` scale=os;return s*x` `}` `## Stringification` `# Determine if a small number is a substring of a larger number in the given base` `define is_substring(base,large,small) {` ` auto os,m;` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;base/=1;large/=1;small/=1;` ` .=base_check_()` ` if(large<0)large=-large` ` if(small<0)small=-small` ` m=base^digits(base,small)` ` while(large){if(large%m==small){m=0;break};large/=base}` ` scale=os;return(m==0) ` `}` `# Catenate (join lexically) two integers in the given base` `# e.g. in base ten, the catenation of 1412 and 4321 is 14124321` `define int_catenate(base, x,y){` ` auto os;` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;base/=1;x/=1;y/=1` ` .=base_check_()` ` if(x<0)x=-x` ` if(y<0)y=-y` ` scale=os;return x*base^digits(base,y)+y` `}` `# Return the specified number of leftmost digits of a number in the given base` `define int_left(base, x, count){` ` auto os;` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;base/=1;x/=1;count/=1` ` .=base_check_()` ` if(count<0)count=0;` ` count=base^count;while(x>=count)x/=base;` ` scale=os;return x` `}` `# Return the specified number of rightmost digits of a number in the given base` `define int_right(base, x, count){` ` auto os;` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;base/=1;x/=1;count/=1` ` .=base_check_()` ` if(count<0)count=0;` ` x%=base^count` ` scale=os;return x` `}` `# Return the specified digits of a number in the given base` `define int_mid(base, x, start, end){` ` auto os,lsz;` ` if(bijective){"unimplemented for bijective";return 1/0}` ` os=scale;scale=0;base/=1;x/=1;start/=1;end/=1` ` .=base_check_()` ` if(start<0)start=0;` ` if(end=lsz)x/=base;` ` x%=base^(end-start+1)` ` scale=os;return x` `}` `## Cantor reinterpretation` `# Set to zero to suppress warnings from cantor()` `cantorwarn_=1` `# 0 = don't perform baseto modulus on digit; 1 = modulus` `cantormod_=0` `# Error checker for below` `define cantor_trans_(d) {` ` d=d*mul+cons;` ` if(scale(d)){` ` if(os<5)scale=5 else scale=os;` ` d+=A^(2-scale)` ` scale=0;d/=1` ` }` ` if(cantormod_){` ` d-=bijective` ` d%=baseto;if(d<0)d+=baseto` ` d+=bijective` ` }` ` if(cantorwarn_)if((bijective>d||d>=abt+bijective)&&!warned){` ` warned=1;print "cantor warning: made ";` ` if(d==0){print "bad zero"` ` } else if(bijective>d){print "negative"}else{print "oversized"}` ` print " digit for destination base\n";` ` }` ` return d` `}` `# Workhorse for managing -ve basefroms` `define cantor_trans_negabase_(basefrom, baseto, mul, cons, x) {` ` auto os,i,bf2,bt2,d,a[],shft,y,p,abt` ` os=scale;scale=0;basefrom/=1;baseto/=1` ` if(basefrom>1)base=-base` ` if(basefrom>-2)base=-obase` ` bf2=basefrom*basefrom` ` bt2=baseto*baseto` ` abt=baseto;if(abt<0)abt=-abt` ` bijective=!!bijective` ` i=x/1;shft=0;if(x!=i)shft=1` ` if(bijective&&shft){` ` shft=0` ` if(cantorwarn_){` ` print "cantor warning: can't do fractional part in bijective mode\n"` ` }` ` }` ` p=bt2` ` if(shft){` ` d=A^scale(x)` ` shft=-1` ` p=1;for(i=1;i<=d;i*=bf2){.=shft++;p*=bt2}` ` shft+=shft` ` x*=i/bf2` ` }` ` for(i=1;x;i++){` ` d=((x-bijective)%basefrom)+bijective;if(d