2

This certain while loop acknowledges it only works up to number 20. After that, it starts to give bad answers, but I can't figure out why.

#!/bin/bash

n=$1
[ "$n" == "" ] && echo Please give a number and try again && exit

factorial=1 ; j=1

while [ $j -le $n ]
do
    factorial=$(( $factorial * $j ))
    j=$(( $j + 1 ))
done
echo The factorial of $n, "$n"'!' = $factorial
exit 0

If you give 21 as an argument, you get: -4249290049419214848. Could it be a bash issue? I tried doing the factorial calculation below and I get the same bad answer. The answer should be: 51090942171709440000

echo $(( 2432902008176640000 * 21 ))
Jeff Schaller
  • 67,283
  • 35
  • 116
  • 255
whatIsLife
  • 39
  • Seems related: https://unix.stackexchange.com/questions/117280/what-is-the-rationale-for-the-bash-shell-not-warning-you-of-arithmetic-overflow – Jeff Schaller Sep 20 '19 at 19:46
  • 1
    Unrelated to the question: In (( expr )) you don't need the $ to get the value of a variable. Also, variables can be assigned directly. Example: Write (( j = j + 1 )) or even (( j++ )) instead of j=$(( $j + 1 )). – Socowi Sep 21 '19 at 12:27

3 Answers3

11

Bash uses signed 64-bit integers on most systems. You will need another tool like bc to go beyond that.

Meaning that with bash the maximum number you can have is 2^63-1, equals to 9,223,372,036,854,775,807 and you are exceeding this number:

awk 'BEGIN{print 2432902008176640000 * 21}'
51090942171709440000     #--> 51,090,942,171,709,440,000
George Vasiliou
  • 7,913
doneal24
  • 5,059
  • awk isn't a very good tool to calculate that either. It uses floating point numbers, and the factorials don't fit exactly into them after a couple of more steps. With gawk, awk 'BEGIN{print 2432902008176640000 * 21 * 22 * 23}' prints 25852016738884978212864, which is obviously wrong. With mawk, it prints 2.5852e+22 (but mawk also shows 20! as 2.4329e+18, even if it could fit exactly.) – ilkkachu Sep 21 '19 at 09:49
  • The wiki page on dc actually includes an example of a factorial program. Using dc -e '?[q]sQ[d1=Qd1-lFx*]dsFxp' will allow you calculate very large large factorials. – doneal24 Sep 21 '19 at 20:50
4

Like doneal24 said, you probably need to go bc.

Add the following to a file named fact.bc:

define f (x) {
  if (x <= 1) return (1);
  return (f(x-1) * x);
}

Now you can call it in bc by supplying the file: E.g. 

$>bc fact.bc <<< "scale=50;f(200)"
78865786736479050355236321393218506229513597768717326329474253324435\
94499634033429203042840119846239041772121389196388302576427902426371\
05061926624952829931113462857270763317237396988943922445621451664240\
25403329186413122742829485327752424240757390324032125740557956866022\
60319041703240623517008587961789222227896237038973747200000000000000\
00000000000000000000000000000000000
Adam D.
  • 462
4

This is what is called an integer overflow error. According to @doneal24's answer, Bash uses 64-bit integers, but I'll use an 8-bit integer in my explanation to make it easier to show what is going on.

An 8-bit integer stores a positive or negative number inside 8 bits, but not all of those bits store the value of the integer - the first bit of the number, the sign bit, denotes whether the number is positive or negative (with "0" meaning positive, and "1" meaning negative), with the next seven bits composing the value of the number in question using standard binary notation.

So, for instance, an integer with a value of one looks like this:

0000 0001

Then, we can begin running your program, and start increasing the value of that integer by multiplying it by the value needed to calculate the next factorial. So, if we multiply that by 2, and then begin repeating that process, we get the following:

0000 0001 x 0000 0010 = 0000 0010

0000 0010 x 0000 0011 = 0000 1010

0000 1010 x 0000 0100 = 0001 1000

0001 1000 x 0000 0101 = 0111 1000

Now we're getting close. The next iteration is where the error happens:

0111 1000 x 0000 0110 = 0010 1101 0000

You can notice that it's overflowed past the eight bits that were assigned to storing the value of the integer - that means that it's overwritten whatever happened to be stored in the memory location immediately before where the integer was stored, and that's bad news, since it can lead to corruption of the processes of the computer; indeed, there have been hackers who have used similar security holes to attack computers in the past.

However, you can also see that the eight bits stored in the location of the integer are "1101 0000". This means that, when your computer interprets its value, it will read the first bit as the sign bit, indicating a negative number, and then read the rest of the number as "101 0000", or 80, and thus it would display the value of this operation as "-80".

Community
  • 1
nick012000
  • 149
  • Integer overflows don't actually overflow the available storage space. Instead, everything above the top of the available space just gets dropped. – Mark Sep 21 '19 at 22:45
  • @Mark In a well designed program/OS, sure, but there have been cases where that wasn’t true and it created vulnerabilities that hackers exploited. For instance, in a relatively harmless example, IIRC the cause of a number of game glitches in the 1st Gen Pokémon games were the result of these sorts of errors, and they allowed for things like item duplication. – nick012000 Sep 21 '19 at 22:54
  • 1
    The game glitches you refer to are a two-stage process. First, something causes an integer overflow to produce a negative number, which in and of itself is harmless. Then, the game uses that negative number as an index into a list. Since list indices are only supposed to be positive, the game reads a non-list part of memory and interprets it as a list entry, and strange things happen. – Mark Sep 22 '19 at 00:03