Mathematical operations - Bash script

Question

I am trying to write a script(script1.sh) that gives the sum of each digits in the first number, raised to the power of second number. So

./script1.sh 12345 2

should output 55

(because 1+4+9+16+25=55)

or ./script1.sh 3706907995955475988644381 25

should output 3706907995955475988644381.

I wrote a script but in some cases I get a negative output and I don't see how that can happen.

For example

./script1.sh 3706907995955475988644380 25

outputs

-2119144605827694052

My script:

#!/bin/bash sum=0 value=$1 arr=() for ((i = 0; i < ${#value}; i++)); do arr+=(${value:$i:1}) done for x in "${arr[@]}"; do sum=$(($sum+(x**$2))) done echo $sum 

Answer 1

shell arithmetic in bash uses the widest integer type supported by your C compiler. On most modern systems/C compilers, that's 64 bit integers, so "only" covering the range -9223372036854775808 to 9223372036854775807, and wrap for numbers out of that. In order to do this you will need to use another tool, such as bc:

#!/bin/bash num1=$1 num2=$2 sum=0 for (( i=0; i<${#num1}; i++ )); do n=${num1:$i:1} sum=$( bc <<<"$sum + $(bc <<<"${n}^$num2")" ) done echo "$sum" 

Answer 2

With short awk script:

sum_powered.awk script:

#!/bin/awk -f BEGIN{ split(ARGV[1], a, ""); pow = ARGV[2]; for (i in a) sum += a[i] ** pow; print sum; } 

Usage:

$ ./sum_powered.awk 12345 2 55 $ ./sum_powered.awk 3706907995955475988644381 25 3706907995955475217645568 

---

You might need to add execution permission to a new awk script before running:

$ chmod +x sum_powered.awk 

Answer 3

Doing math that have results of 25 digits (3706907995955475988644381) is certainly outside the capacity of most shell implementations. In fact, shell arithmetic is quite similar to C language arithmetic. In C language, a signed integer flips sign when there is overflow. The common longest system integer for a 64 bit system would use has a value limited to 63 binary digits (the other bit defines the sign of the integer), so, 63 1's in binary or 0efff ffff ffff ffff in hex represents the number $(( (1<<63) - 1 )) or 9223372036854775807 (19 digits). The negative limit is -9223372036854775808.

A 25 digit number can not fit inside a 19 digit integer, so it overflows, as C signed integers overflow: by changing sign (on most machines):

$ echo "$(( 9223372036854775807 + 1 ))" -9223372036854775808 

bc

The lowest level language that a (stand alone) utility could provide for "Arbitrary precision math" (numbers without a preset length limit) is bc. In bc, is not difficult to execute the whole requirement:

x=12345 y=2 scale=0; s=0; while (x>0) { b=x%10; x/=10; s+=b^y }; s quit 

Write that to a file (assume it is called digpower.bc) and execute with this:

$ bc -q digpower.bc 55 

Morphing the whole file to contain only a function that takes care of temporal variables and returning scale to its original value:

define d(x,y){ auto s,b,u; s=scale; while (x>0) { b=x%10; x/=10; u+=b^y } scale=s; return(u) }; 

In this case, call bc like this:

$ bc -q digpower.bc <<<"d(12345,2)" 55 $ echo "d(3706907995955475988644381,25)" | bc digpower.bc 3706907995955475988644381 

python

The next higher level language (skipping Common lisp) that has unlimited (only by computer memory) integers is Python:

$ python3 -c 'x=12345;y=2;s=0; while (x>0): b=x%10;x//=10;s+=b**y print(s)' 55 

Most other languages use some form of floats, including awk. Some languages allow the setting of how big the floats could be (more about this in awk latter).

awk

All the numbers inside awk are stored as floats. By default, awk use 53 bit mantissa. A 53 bit mantissa has a general limit of 16 digits. In some particular floats 17 or even 18 digits may be exact.

$ awk -vx=12345 -vy=2 'BEGIN{s=0;while(x>0){b=x%10;x=int(x/10);s+=b^y}; print(s)}' 55 

But (the same code with other values):

$ awk -vx=3706907995955475988644381 -vy=25 'BEGIN{s=0;while(x>0){b=x%10;x=int(x/10);s+=b^y}; print(s)}' 2989038141653481752100864 

Which is obviously wrong because the internal representation as float gets it quite wrong after the 16 digit. Just to show it:

$ awk -vx=3706907995955475988644381 'BEGIN{print(x);print(x+0)}' 3706907995955475988644381 3706907995955475754516480 

Those errors lead to bigger errors.

There is the alternative with GNU awk of increasing the number of bits of the float mantissa if awk has bignum compiled in (output of awk --version contains "GNU MPFR"):

$ awk -M -v PREC=100 -vx=3706907995955475988644381 -vy=25 'BEGIN{s=0;while(x>0){b=x%10;x=int(x/10);s+=b**y}; print(s)}' 3706907995955475988644381 

A 25 decimal digit require about 25*log(2)/log(10) binary digits or a 83 bit mantissa (the exact answer is quite longer to explain). Using 100 gives enough margin.