0

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
1

3 Answers 3

5

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"
1
  • Didn't know that. Thanks for the answer!
    – arty
    Nov 23, 2019 at 17:10
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 
1
  • Even the floats used inside awk have limits, try ./sum_powered.awk 3 700, which outputs inf. In fact, the correct answer for 3706907995955475988644381 25 should be 3706907995955475988644381 but awk (failing after 16 digits, which should be expected for a 53 bit float) outputs 3706907995955475217645568.
    – user232326
    Nov 24, 2019 at 0:05
2

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .