Advertisement
hxrussia

Arbitrary-precision arithmetic in Bash

Dec 26th, 2014
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Bash 4.39 KB | None | 0 0
  1. #!/usr/bin/env bash
  2.  
  3. base=10
  4. (( half_base = base / 2 ))
  5. nan_value=NaN
  6.  
  7. function main {
  8.     action="$1"
  9.     if contains "$action" add sub mul div mod; then
  10.         check_decimal "$2" "$3"
  11.         to_decimal "$($action "$(from_decimal $2)" "$(from_decimal $3)")"
  12.     elif [[ "$action" == "sqrt" ]]; then
  13.         check_decimal "$2"
  14.         to_decimal "$($action "$(from_decimal $2)")"
  15.     else
  16.         show_help
  17.     fi
  18. }
  19.  
  20. function show_help {
  21.     cat <<end
  22. Usage: $0 add A B
  23.       $0 sub A B
  24.       $0 mul A B
  25.       $0 div A B
  26.       $0 mod A B
  27.       $0 sqrt NUMBER
  28. Calculate result of an operation using long arithmetic.
  29.  
  30. Only unsigned integer numbers are supported.
  31. Non-integer results will be rounded down.
  32. end
  33.     exit 1
  34. }
  35.  
  36. function contains {
  37.     local elem
  38.     for elem in "${@:2}"; do
  39.         if [[ "$elem" == "$1" ]]; then
  40.             return 0
  41.         fi
  42.     done
  43.     return 1
  44. }
  45.  
  46. function check_decimal {
  47.     local elem
  48.     for elem in "$@"; do
  49.         if [[ "$elem" == "" ]]; then
  50.             show_help
  51.         fi
  52.         if [[ ! "$elem" =~ ^[0-9]+$ ]]; then
  53.             echo "Error: Only unsigned integer numbers are supported"
  54.             exit 1
  55.         fi
  56.     done
  57. }
  58.  
  59. function from_decimal {
  60.     echo "$1" | sed -r 's/^0//g' | rev | sed -r 's/./& /g'
  61. }
  62.  
  63. function to_decimal {
  64.     echo "$1" | tr -d ' ' | rev | sed -r 's/^$/0/'
  65. }
  66.  
  67. function add {
  68.     local -a a=($1)
  69.     local -a b=($2)
  70.     local -a res
  71.     local -i carry=0
  72.     local -i i
  73.     local -i a_length=${#a[*]}
  74.     local -i b_length=${#b[*]}
  75.     for (( i = 0; i < a_length || i < b_length || carry; i++ )); do
  76.         local -i digit
  77.         (( digit = a[i] + b[i] + carry ))
  78.         if (( digit >= base )); then
  79.             (( digit -= base ))
  80.             carry=1
  81.         else
  82.             carry=0
  83.         fi
  84.         (( res[i] = digit ))   
  85.     done
  86.     echo "${res[*]}"
  87. }
  88.  
  89. function skip_zeros {
  90.     echo "$1" | sed -r 's/(0 ?)+$//'
  91. }
  92.  
  93. function sub {
  94.     local -a a=($1)
  95.     local -a b=($2)
  96.     local -a res
  97.     local -i carry=0
  98.     local -i i
  99.     local -i a_length=${#a[*]}
  100.     local -i b_length=${#b[*]}
  101.     for (( i = 0; i < a_length || i < b_length || carry; i++ )); do
  102.         if (( i >= a_length )); then
  103.             echo $nan_value
  104.             return
  105.         fi
  106.         local -i digit
  107.         (( digit = a[i] - b[i] - carry ))
  108.         if (( digit < 0 )); then
  109.             (( digit += base ))
  110.             carry=1
  111.         else
  112.             carry=0
  113.         fi
  114.         (( res[i] = digit ))
  115.     done
  116.     skip_zeros "${res[*]}"
  117. }
  118.  
  119. function mul {
  120.     local -a a=($1)
  121.     local -a b=($2)
  122.     local -a res
  123.     local -i carry=0
  124.     local i j
  125.     local -i a_length=${#a[*]}
  126.     local -i b_length=${#b[*]}
  127.     for (( i = 0; i < a_length; i++ )); do
  128.         for (( j = 0; j < b_length || carry; j++ )); do
  129.             local -i k
  130.             (( k = i + j ))
  131.             local -i digit
  132.             (( digit = res[k] + a[i] * b[j] + carry ))
  133.             (( carry = digit / base ))
  134.             (( res[k] = digit % base ))
  135.         done
  136.     done
  137.     echo "${res[*]}"
  138. }
  139.  
  140. function div2 {
  141.     local -a number=($(echo "$1" | rev))
  142.     local -a res
  143.     local -i carry=0
  144.     local -i length=${#number[*]}
  145.     for (( i = 0; i < length; i++ )); do
  146.         local -i digit next_carry
  147.         (( digit = number[i] ))
  148.         (( next_carry = digit & 1 ))
  149.         (( digit >>= 1 ))
  150.         if (( carry == 1 )); then
  151.             (( digit += half_base ))
  152.         fi
  153.         carry=$next_carry
  154.         (( res[i] = digit ))
  155.     done
  156.     skip_zeros "$(echo "${res[*]}" | rev)"
  157. }
  158.  
  159. function div {
  160.     local -a a=($1)
  161.     local -a b=($2)
  162.     if (( ${#b[*]} == 0 )); then
  163.         echo $nan_value
  164.         return
  165.     fi
  166.     local -a l=()
  167.     local -a r=($(add "${a[*]}" 1))
  168.     while true; do
  169.         local diff="$(sub "${l[*]}" "${r[*]}")"
  170.         if [[ "$diff" != "$nan_value" ]]; then
  171.             break
  172.         fi
  173.         local -a middle=($(div2 "$(add "${l[*]}" "${r[*]}")"))
  174.         local -a product=($(mul "${middle[*]}" "${b[*]}"))
  175.         diff="$(sub "${product[*]}" "${a[*]}")"
  176.         if [[ "$diff" == "$nan_value" || "$diff" =~ ^\ *$ ]]; then
  177.             l=($(add "${middle[*]}" 1))
  178.         else
  179.             r=(${middle[*]})
  180.         fi
  181.     done
  182.     sub "${l[*]}" 1
  183. }
  184.  
  185. function mod {
  186.     local -a a=($1)
  187.     local -a b=($2)
  188.     local divided="$(div "${a[*]}" "${b[*]}")"
  189.     if [[ "$divided" == "$nan_value" ]]; then
  190.         echo $nan_value
  191.         return
  192.     fi
  193.     sub "${a[*]}" "$(mul "$divided" "${b[*]}")"
  194. }
  195.  
  196. function sqrt {
  197.     local -a number=($1)
  198.     local -a l=()
  199.     local -a r=($(add "${number[*]}" 1))
  200.     while true; do
  201.         local diff="$(sub "${l[*]}" "${r[*]}")"
  202.         if [[ "$diff" != "$nan_value" ]]; then
  203.             break
  204.         fi
  205.         local -a middle=($(div2 "$(add "${l[*]}" "${r[*]}")"))
  206.         local -a product=($(mul "${middle[*]}" "${middle[*]}"))
  207.         diff="$(sub "${product[*]}" "${number[*]}")"
  208.         if [[ "$diff" == "$nan_value" || "$diff" =~ ^\ *$ ]]; then
  209.             l=($(add "${middle[*]}" 1))
  210.         else
  211.             r=(${middle[*]})
  212.         fi
  213.     done
  214.     sub "${l[*]}" 1
  215. }
  216.  
  217. main $@
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement